記錄了初步解題思路 以及本地實現代碼；并不一定為最優 也希望大家能一起探討 一起進步

---

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

---