119 Yanghui triangle 2
Push down line by line
class Solution: def getRow(self, rowIndex: int) -> List[int]: if rowIndex == 0: return [1] if rowIndex == 1: return [1,1] rel = [1,1] for i in range(rowIndex-1): currel = [1] for index,_ in enumerate(rel[:-1]): currel.append(rel[index]+ rel[index+1]) currel.append(1) rel=currel return rel Author: yizhu-jia Link: https://leetcode-cn.com/problems/pascals-triangle-ii/solution/wang-shi-wu-xu-zai-ti-qian-xing-zhi-shen-7p8c/ Source: force buckle( LeetCode) The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.
120: Triangle minimum path sum
Tracing back hurts me thousands of times. I wait to trace back like my first love
n = len(triangle) dp = [10**4+1]*(n) dp[0] = triangle[0][0] for i in range(1,n): #Look at line i for j in range(i,-1,-1): #Look at column j if j == 0: dp[j] = triangle[i][j]+dp[0] else: dp[j] = triangle[i][j] + min(dp[j],dp[j-1]) return min(dp) Author: yizhu-jia Link: https://leetcode-cn.com/problems/triangle/solution/hui-su-shang-wo-qian-mo-bian-wo-dai-hui-f493p/ Source: force buckle( LeetCode) The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.
121. The best time to sell stocks
Maintain a current maximum profit and previous minimum.
If the current value is smaller than the minimum value, update the minimum value
If it is not small, subtract the minimum value to see the profit.
Note that else allows us to cover the situation that the stock has been falling.
class Solution: def maxProfit(self, prices: List[int]) -> int: minpri = prices[0] maxpro = 0 n = len(prices) for i in range(n): if prices[i] < minpri: minpri = prices[i] elif prices[i] - minpri > maxpro: maxpro = prices[i] - minpri return maxpro Author: yizhu-jia Link: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/solution/wo-zhe-ge-elsejia-de-jian-zhi-jiu-shi-ti-fs2r/ Source: force buckle( LeetCode) The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.
122. The best time to sell shares 2
Go through it
First find a stock lower than the day after him and buy it! Because if he is lower than him the next day, he must buy the lower one
Find another stock higher than the day after him and sell it! Because if he's taller than him the next day, he won't sell it
Repeat the above steps after selling
Get the maximum profit
class Solution:
def maxProfit(self, prices: List[int]) -> int:
n = len(prices)
def findnextpri(index):
for i in range(index,n-1):
if prices[i] < prices[i+1]:
return i
return -1
index = 0
pri = 0
while True:
index = findnextpri(index)
if index < 0:
return pri
for j in range(index,n):
if j == n-1:
pri += prices[j] - prices[index]
elif prices[j]>prices[j+1]:
pri += prices[j] - prices[index]
break
index = j
Author: yizhu-jia
Link: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-ii/solution/mei-xiang-dao-jie-guo-zhe-yao-hao-mo-mo-xji48/
Source: force buckle( LeetCode)
The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.
123: maximum path sum of binary tree
Time is defeated by 94 people and space is defeated by 95 people
But at least I figured it out myself.
My dfs will return two values. One is the maximum value that can be reached by the subtree connected to the current node
The other is the maximum value that can be reached on the connected subtree or not.
Sumdeft is that the left subtree can be connected to the current node
, the left subtree of leftmax may not be connected to the current node. This part is tantamount to giving up the hope of moving forward in life and waiting to see if it surpasses him
How?
rootmax is the maximum in three cases:
1 left + root
2 right + root
3 left + right
These three cases can continue to expand upward
maxsum is the maximum in all cases
In addition to the above three, it also includes:
1 left and right middle
2 left
3 right
4 any case of left subtree is the largest
5 any maximum on the right subtree
Recursion to root node
Then we get the maximum value that can be obtained with the root node
Returning - 10000 when empty means giving up the hope of life directly
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxPathSum(self, root: Optional[TreeNode]) -> int: def dfs(root): if root == None: return -10000,-10000 sumleft,leftmax = dfs(root.left) sumright,rightmax = dfs(root.right) rootmax = max(sumleft+root.val,sumright+root.val,root.val) maxsum = max(sumleft+root.val,sumright+root.val,sumright+sumleft+root.val,root.val,sumleft,sumright,leftmax,rightmax) return rootmax,maxsum a,b = dfs(root) return b Author: yizhu-jia Link: https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/solution/hahahahhahahbei-94de-ren-ji-bai-liao-shi-hn7h/ Source: force buckle( LeetCode) The copyright belongs to the author. For commercial reprint, please contact the author for authorization, and for non-commercial reprint, please indicate the source.