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

---

3/31 2278. 字母在字符串中的百分比

遍歷 求出字母個數

def percentageLetter(s, letter):""":type s: str:type letter: str:rtype: int"""num = 0n=len(s)for c in s:if c==letter:num+=1return num*100//n

---

4/1 2140. 解決智力問題

一眼動歸
因為對于某個位置i是否可以解決取決于他前面的問題 所以從后往前遍歷更加方便
定義dp[i]為解決i~n之間的問題可以得到的最高分數
dp[i]=points[i]+dp[i+brainpower[i]+1]

def mostPoints(questions):""":type questions: List[List[int]]:rtype: int"""n=len(questions)dp=[0]*(n+1)for i in range(n-1,-1,-1):dp[i]=max(dp[i+1],questions[i][0]+dp[min(n,i+questions[i][1]+1)])return dp[0]

---

4/2 2873. 有序三元組中的最大值 I

1.遍歷 三重循環
2.為了使值最大 對于每個j 要找到它左邊的最大值nums[i] 和右邊的最大值nums[k]
lmax[j],rmax[j]分別記錄j左右的最大值

def maximumTripletValue(nums):""":type nums: List[int]:rtype: int"""cur = 0n=len(nums)for i in range(n-2):for j in range(i+1,n-1):for k in range(j+1,n):cur=max(cur,(nums[i]-nums[j])*nums[k])return curdef maximumTripletValue2(nums):""":type nums: List[int]:rtype: int"""n=len(nums)lmax=[0]*nrmax=[0]*nfor i in range(1,n):lmax[i]=max(lmax[i-1],nums[i-1])rmax[n-1-i]=max(rmax[n-i],nums[n-i])cur=0for j in range(1,n-1):cur=max(cur,(lmax[j]-nums[j])*rmax[j])return cur

---

4/3 2874. 有序三元組中的最大值 II

數組長度很大不能循環遍歷
為了使值最大 對于每個j 要找到它左邊的最大值nums[i] 和右邊的最大值nums[k]
lmax[j],rmax[j]分別記錄j左右的最大值

def maximumTripletValue(nums):""":type nums: List[int]:rtype: int"""n=len(nums)lmax=[0]*nrmax=[0]*nfor i in range(1,n):lmax[i]=max(lmax[i-1],nums[i-1])rmax[n-1-i]=max(rmax[n-i],nums[n-i])cur=0for j in range(1,n-1):cur=max(cur,(lmax[j]-nums[j])*rmax[j])return cur

---

4/4 1123. 最深葉節點的最近公共祖先

dfs

class TreeNode(object):def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef lcaDeepestLeaves(root):""":type root: Optional[TreeNode]:rtype: Optional[TreeNode]"""global ans,maxdans=Nonemaxd = -1def dfs(node,dep):global ans,maxdif not node:maxd = max(maxd,dep)return depleft = dfs(node.left,dep+1)right = dfs(node.right,dep+1)if left==right==maxd:ans = nodereturn max(left,right)dfs(root,0)return ans

---

4/5 1863. 找出所有子集的異或總和再求和

遍歷

def subsetXORSum(nums):""":type nums: List[int]:rtype: int"""ans=0n=len(nums)for i in range(1<<n):tmp=0for j in range(n):if i&(1<<j):tmp^=nums[j]ans+=tmpreturn ans

---

4/6 368. 最大整除子集

1. 遍歷
   ans內每個num結尾都一個備選答案
   每一個數 遍歷當前備選答案 保留長度最大的一個為當前Num的備選答案
   2.dp
   dp[i] nums[i]最大子集個數

def largestDivisibleSubset(nums):""":type nums: List[int]:rtype: List[int]"""n = len(nums)nums.sort()ans = [[nums[0]]]for i in range(1,n):c = nums[i]ret = []for j in range(len(ans)-1,-1,-1):tmp = ans[j][:]if c%tmp[-1]==0:tmp.append(c)if len(tmp)>len(ret):ret = tmp[:]if not ret:ret = [c]ans.append(ret)ans.sort(key=lambda x: len(x))return ans[-1]def largestDivisibleSubset2(nums):""":type nums: List[int]:rtype: List[int]"""n=len(nums)nums.sort()dp = [1]*nmsize,mval=1,1for i in range(n):for j in range(i):if nums[i]%nums[j]==0 and dp[j]+1>dp[i]:dp[i]=dp[j]+1if dp[i]>msize:msize=dp[i]mval = nums[i]if msize==1:return nums[:1]ret = []for i in range(n-1,-1,-1):if msize==0:return retif dp[i]==msize and mval%nums[i]==0:ret.append(nums[i])mval = nums[i]msize-=1return ret

---