记录了初步解题思路 以及本地实现代码；并不一定为最优 也希望大家能一起探讨 一起进步

---

8/4 904. 水果成篮

滑动窗口l,r 记录当前水果
如果超过两种则滑动l 减少至两种

def totalFruit(fruits):""":type fruits: List[int]:rtype: int"""m = {}ans = 0l = 0for r,v in enumerate(fruits):m[v] = m.get(v,0)+1if len(m)>2:m[fruits[l]]-=1if m[fruits[l]] == 0:m.pop(fruits[l])l+=1ans = max(ans,r-l+1)return ans

---

8/5 3477. 水果成篮 II

遍历每一个水果

def numOfUnplacedFruits(fruits, baskets):""":type fruits: List[int]:type baskets: List[int]:rtype: int"""ans=0n=len(baskets)for f in fruits:cur=1for i in range(n):if f<=baskets[i]:baskets[i]=0cur=0breakans+=curreturn ans

---

8/6 3479. 水果成篮 III

线段树二分
对于水果i 在线段树上二分找到第一个容量大于等于它的篮子

def numOfUnplacedFruits(fruits, baskets):""":type fruits: List[int]:type baskets: List[int]:rtype: int"""class Tree:def __init__(self,a):n=len(a)self.max=[0]*(2<<(n-1).bit_length())self.build(a,1,0,n-1)def maintain(self,o):self.max[o]=max(self.max[o*2],self.max[o*2+1])def build(self,a,o,l,r):if l==r:self.max[o]=a[l]return mid=(l+r)//2self.build(a, o*2, l, mid)self.build(a, o*2+1, mid+1, r)self.maintain(o)def find(self,o,l,r,x):if self.max[o]<x:return -1if l==r:self.max[o]=-1return lmid=(l+r)//2i = self.find(o*2,l,mid,x)if i<0:i=self.find(o*2+1, mid+1, r, x)self.maintain(o)return itr=Tree(baskets)n=len(baskets)ans=0for x in fruits:if tr.find(1, 0, n-1, x)<0:ans+=1return ans

---

8/7 3363. 最多可收集的水果数目

左上角的小朋友只能走对角线到达
为了使得收集水果最多 不走重复路线
右上角小朋友不穿过对角线 只在右上走
同理 左下小朋友只在左下走
dfs 只需要一个小朋友走好了 另一个反转后一样

def maxCollectedFruits(fruits):""":type fruits: List[List[int]]:rtype: int"""n=len(fruits)mem={}ans = sum(fruits[i][i] for i in range(n))def dfs(i,j):if (i,j) in mem:return mem[(i,j)]if not(n-1-i<=j<n):return float("-inf")if i==0:return fruits[i][j]ans = max(dfs(i-1,j-1),dfs(i-1,j),dfs(i-1,j+1))+fruits[i][j]mem[(i,j)]=ansreturn ansans+=dfs(n-2,n-1)mem={}fruits=list(zip(*fruits))ans+=dfs(n-2,n-1)return ans

---

8/8 808. 分汤

可以将25ml看作1份 四种情况分别为
A 4 B 0
A 3 B 1
A 2 B 2
A 1 B 3
开始时 A,B拥有的份数一样
当n过大时 A被取完的概率接近于1 误差小于10^-5
假设dp[i][j] 为A剩余i份 B剩余j份时 需要求的概率
dp[i][j] = (dp[i-4][j]+dp[i-3][j-1]+dp[i-2][j-2]+dp[i-1][j-3])/4
当j=0,i>0时 dp[i][j] = 0
当i=0,j>0时 dp[i][j] = 1
当i=0,j=0时 dp[i][j] = 0.5

def soupServings(n):""":type n: int:rtype: float"""n = (n+24)//25if n>=179:return 1dp = [[0]*(n+1) for _ in range(n+1)]dp[0] = [0.5]+[1.0]*nfor i in range(1,n+1):for j in range(1,n+1):dp[i][j] = (dp[max(0, i - 4)][j] + dp[max(0, i - 3)][max(0, j - 1)] +dp[max(0, i - 2)][max(0, j - 2)] + dp[max(0, i - 1)][max(0, j - 3)])/4return dp[n][n]

---

8/9 231. 2 的幂

排除负数
转换为二进制 如果是2的幂 必定只有第一位为1 其它为0
2.
去除最低位1的方法 n与n-1相与
如果只有1个1 那么n&(n-1)==0
不为零说明不止一个1

def isPowerOfTwo(n):""":type n: int:rtype: bool"""if n<=0:return Falses = bin(n)[2:]return True if s.count('1')==1 else Falsedef isPowerOfTwo2(n):""":type n: int:rtype: bool"""if n<=0:return Falsereturn n&(n-1)==0

---

8/10 869. 重新排序得到 2 的幂

n<109 所以2的幂最多229
找到所有2的幂的数字组合
匹配

def reorderedPowerOf2(n):""":type n: int:rtype: bool"""base = 1s = set()l = list(str(base))l.sort()s.add("".join(l))for i in range(29):base *=2l = list(str(base))l.sort()s.add("".join(l))check = list(str(n))check.sort()return "".join(check) in s

---