5.3
題目鏈接
很喜歡的解法（DP）
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
maxSum=nums[0]
tmp=0
for i in nums:
tmp=max(tmp+i,i)
maxSum=max(maxSum,tmp)
return maxSum
官方解（分治）
參考題解：最大子序和
但是仔細(xì)觀(guān)察「方法二」，它不僅可以解決區(qū)間 [0,n?1]，還可以用于解決任意的子區(qū)間 [l,r] 的問(wèn)題。如果我們把 [0,n?1] 分治下去出現(xiàn)的所有子區(qū)間的信息都用堆式存儲(chǔ)的方式記憶化下來(lái)，即建成一顆真正的樹(shù)之后，我們就可以在 O(logn) 的時(shí)間內(nèi)求到任意區(qū)間內(nèi)的答案，我們甚至可以修改序列中的值，做一些簡(jiǎn)單的維護(hù)，之后仍然可以在 O(logn) 的時(shí)間內(nèi)求到任意區(qū)間內(nèi)的答案，對(duì)于大規(guī)模查詢(xún)的情況下，這種方法的優(yōu)勢(shì)便體現(xiàn)了出來(lái)。這棵樹(shù)就是上文提及的一種神奇的數(shù)據(jù)結(jié)構(gòu)——線(xiàn)段樹(shù)。
參考題解：【五種解法三種語(yǔ)言】（Java， JavaScript， Python）
import sys
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
return self.helper(nums, 0, len(nums) - 1)
def helper(self, nums, l, r):
if l > r:
return -sys.maxsize
mid = (l + r) // 2
left = self.helper(nums, l, mid - 1)
right = self.helper(nums, mid + 1, r)
left_suffix_max_sum = right_prefix_max_sum = 0
sum = 0
for i in reversed(range(l, mid)):
sum += nums[i]
left_suffix_max_sum = max(left_suffix_max_sum, sum)
sum = 0
for i in range(mid + 1, r + 1):
sum += nums[i]
right_prefix_max_sum = max(right_prefix_max_sum, sum)
cross_max_sum = left_suffix_max_sum + right_prefix_max_sum + nums[mid]
return max(cross_max_sum, left, right)
5.4
題目鏈接
官方解（貪心）
如果我們「貪心」地進(jìn)行正向查找，每次找到可到達(dá)的最遠(yuǎn)位置，就可以在線(xiàn)性時(shí)間內(nèi)得到最少的跳躍次數(shù)。
例如，對(duì)于數(shù)組 [2,3,1,2,4,2,3]，初始位置是下標(biāo) 0，從下標(biāo) 0 出發(fā)，最遠(yuǎn)可到達(dá)下標(biāo) 2。下標(biāo) 0 可到達(dá)的位置中，下標(biāo) 1 的值是 3，從下標(biāo) 1 出發(fā)可以達(dá)到更遠(yuǎn)的位置，因此第一步到達(dá)下標(biāo) 1。
class Solution:
def jump(self, nums: List[int]) -> int:
n = len(nums)
maxPos, end, step = 0, 0, 0
for i in range(n - 1):
if maxPos >= i:
maxPos = max(maxPos, i + nums[i])
if i == end:
end = maxPos
step += 1
return step
自己有參考的解法
# 之前看評(píng)論，說(shuō)用if比用max好像要快些……
class Solution:
def jump(self, nums: List[int]) -> int:
count=0
begin,end=0,0
while end<len(nums)-1:
nowmax=end
for i in range(begin,end+1):
if i+nums[i]>nowmax:
nowmax=i+nums[i]
begin,end=end+1,nowmax
count+=1
return count
5.6
題目鏈接
很喜歡的解法（DP，從前向后）
參考題解：【熊貓刷題Python3】一維動(dòng)態(tài)規(guī)劃，易懂(附視頻題解)
對(duì)于一年中的任意一天：
首先考慮當(dāng)前天數(shù)是否在 days 中，如果不在，那我們可以貪心地選擇不買(mǎi)。這是因?yàn)槿绻裉觳挥贸鲂校敲匆膊槐刭?gòu)買(mǎi)通行證，并且通行證越晚買(mǎi)越好。
如果在的話(huà)，我們就要從三種購(gòu)買(mǎi)方式中選擇一種花費(fèi)費(fèi)用最少的，即如果想到達(dá)第 i 天，就需要從 i 的前1或7或30天的后一位置花費(fèi)對(duì)應(yīng)cost[0]、cost[1]、cost[2]的錢(qián)才能到第 i 天。
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
dp=[0 for i in range(days[-1]+1)]
index=0
for i in range(days[0],len(dp)):
if i!=days[index]:
dp[i]=dp[i-1]
else:
dp[i]=min(dp[max(0,i-1)]+costs[0],dp[max(0,i-7)]+costs[1],dp[max(0,i-30)]+costs[2])
index+=1
return dp[-1]
官方解（DP，從后向前）
我們用 dp(i) 來(lái)表示從第 i 天開(kāi)始到一年的結(jié)束，我們需要花的錢(qián)?？紤]到一張通行證可以讓我們?cè)凇附酉聛?lái)」的若干天進(jìn)行旅行，所以我們「從后往前」倒著進(jìn)行動(dòng)態(tài)規(guī)劃。
但是觀(guān)察方法一的遞推式，我們可以看到，如果我們查詢(xún) dp(i)，而第 i 天我們又不需要出行的話(huà)，那么 dp 函數(shù)會(huì)一直向后計(jì)算 dp(i+1)=dp(i+2)=dp(i+3) 一直到一年結(jié)束或者有一天我們需要出行為止。那么我們其實(shí)可以直接跳過(guò)這些不需要出行的日期，直接找到下一個(gè)需要出行的日期。
class Solution:
def mincostTickets(self, days: List[int], costs: List[int]) -> int:
N = len(days)
durations = [1, 7, 30]
@lru_cache(None)
def dp(i):
if i >= N:
return 0
ans = 10**9
j = i
for c, d in zip(costs, durations):
while j < N and days[j] < days[i] + d:
j += 1
ans = min(ans, dp(j) + c)
return ans
return dp(0)
5.7
題目鏈接
很喜歡的解法（遞歸判斷子樹(shù)）
具體操作=官方題解1，即DFS暴力匹配，但是邏輯很清楚所以很喜歡。
參考題解：對(duì)稱(chēng)美！判斷子樹(shù) vs 判斷相等！
判斷兩個(gè)樹(shù)是否相等的三個(gè)條件是與的關(guān)系，即：
1.當(dāng)前兩個(gè)樹(shù)的根節(jié)點(diǎn)值相等；
2.并且，s 的左子樹(shù)和 t 的左子樹(shù)相等；
3.并且，s 的右子樹(shù)和 t 的右子樹(shù)相等。
而判斷 t 是否為 s 的子樹(shù)的三個(gè)條件是或的關(guān)系，即：
1.當(dāng)前兩棵樹(shù)相等；
2.或者，t 是 s 的左子樹(shù)；
3.或者，t 是 s 的右子樹(shù)。
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
def isSame(node1,node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
return isSame(node1.left,node2.left) and isSame(node1.right,node2.right) and node1.val==node2.val
def isSub(node1,node2):
if not node1 and not node2:
return True
if not node1 or not node2:
return False
return isSub(node1,node2.left) or isSub(node1,node2.right) or isSame(node1,node2)
return isSub(t,s)
自己的解法（前序遍歷比較結(jié)果）
前序遍歷對(duì)單子樹(shù)而言，得出的序列是真正的子樹(shù)序列
具體思路基本上=官方題解2，即DFS序列上的串匹配。不過(guò)我不會(huì)寫(xiě)KMP……這個(gè)算法我就只能腦內(nèi)跑結(jié)果（。以后有空試著寫(xiě)下……
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
def helper(node,r):
if not node:
r.append('null')
return
r.append(str(node.val))
helper(node.left,r)
helper(node.right,r)
ans1,ans2=[''],['']
helper(t,ans1)
helper(s,ans2)
ans1=' '.join(ans1)
ans2=' '.join(ans2)
return True if ans1 in ans2 else False
官方解（樹(shù)哈希）
考慮把每個(gè)子樹(shù)都映射成一個(gè)唯一的數(shù)，如果 t 對(duì)應(yīng)的數(shù)字和 s 中任意一個(gè)子樹(shù)映射的數(shù)字相等，則 t 是 s 的某一棵子樹(shù)。
……我有點(diǎn)兒不懂……先馬住，慢慢學(xué)習(xí)（
5.8
題目鏈接
很喜歡的解法（DP）
參考題解：理解 三者取最小+1
上面詳解了 三者取最小 的含義：
圖1：受限于左上的0
圖2：受限于上邊的0
圖3：受限于左邊的0
數(shù)字表示：以此為正方形右下角的最大邊長(zhǎng)
黃色表示：格子 ? 作為右下角的正方形區(qū)域
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if matrix==[]:
return 0
matrix=[[0]*(len(matrix[0])+1)]+[[0]+list(map(int,i)) for i in matrix]
s=0
for i in range(1,len(matrix)):
for j in range(1,len(matrix[0])):
if matrix[i][j]==1:
matrix[i][j]=min(matrix[i-1][j-1],matrix[i-1][j],matrix[i][j-1])+1
s=max(s,matrix[i][j])
return s**2
5.15
題目鏈接
很喜歡的解法（前綴和+哈希表）
參考題解：【熊貓刷題Python3】前綴和+字典，易懂 (附視頻題解)
比如我們到某一個(gè)位置 i 得到前綴和為 9，也就說(shuō)從 0 位置到 i 位置的所有數(shù)字的和為 9， 如果目標(biāo) k 為 3，那么我們只需要找到當(dāng)前狀態(tài)下，前面出現(xiàn)了幾次 6，就知道以 nums[i] 結(jié)尾的和為 3 的連續(xù)子數(shù)組的個(gè)數(shù)有多少個(gè)。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
tmp=defaultdict(int)
tmp[0]=1
cur_sum = 0
res = 0
for i in nums:
cur_sum += i
if cur_sum - k in tmp:
res += tmp[cur_sum - k]
tmp[cur_sum] += 1
return res
5.18
題目鏈接
官方解（DP）
參考題解：乘積最大子數(shù)組
class Solution:
def maxProduct(self, nums: List[int]) -> int:
maxf=nums[0]
minf=nums[0]
ans=nums[0]
for i in range(1,len(nums)):
tmp1,tmp2=maxf,minf
maxf=max(tmp1*nums[i],max(nums[i],tmp2*nums[i]))
minf=min(tmp2*nums[i],min(nums[i],tmp1*nums[i]))
ans=max(ans,maxf)
return ans
