蓝桥杯10天

雨点打透心脏的1/2处 2023-01-09 15:39 100阅读 0赞

# 一买卖股票的最佳时机 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]

*  我们要找到最大的差额就要记录从开始到现在获得最大的负收益min——然后将其减去
 *  这种方法只需要一次遍历，我们以局部和代整体和，整体最大和等于到目前为止的和减去目前为止的负收益和，倒退也成立，就可以找到局部max=整体和-局部负收益和
 *  这种方法在我那个最大子序和哪里讨论过，不懂的可以翻过去

class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            while not prices:
                return 0
            min_,max_=prices[0],0
            for i in prices:
                min_=min(min_,i)
                max_=max(max_,i-min_)
            return max_

# 二买卖股票的最佳时机2 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]

*  简而言之，这道题更简单，就是把所有大于零的差都加起来，没有什么水平的一道题

class Solution(object):
        def maxProfit(self, prices):
            """
            :type prices: List[int]
            :rtype: int
            """
            total=0
            
            for i in range(len(prices)-1):                
                k=prices[i+1]-prices[i]
                if k>0:
                    total+=k
            return total

# 三二叉树的最大路径和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]

*  递归的思想，之前我们做过一道最大深度的问题
 *  既然递归，其形势必然为如下形式：  
    *if nor root： return  
    l=maxroot（root.left)  
    r=maxroot(root.right)  
    return*\*\*
 *  但是我们如果要是递归下面一层的最大和，和由r+l+节点构成，那么我们返回的不是正确的路径，
 *  如果我们返回的是节点或max（l，r）
 *  那么返回到最后一层的时候返回的还要再加，因此，我们要在递归过程返回max（l，r）同时要确定一个全局变量，记录现节点对应的最大路径和左右节点对应最大的路径
 *  最终返回一个非return的记录量，即全局变量
 *  因此我们的结构俩个点：  
    1.全局变量ans，负责更迭最大路径  
    2.递归函数负责返回每次迭代的max（l，r，0）+val

class Solution:
        glb_max = -2147483648
        def maxPathSum(self, root: TreeNode) -> int:
            def maxPathSum2(root):
                if not root:
                    return 0
                left=maxPathSum2(root.left)
                right=maxPathSum2(root.right)
                t=root.val
                self.glb_max=max(self.glb_max,t+left+right,t,t+left,t+right)
                return max(left+t,right+t,t)
            maxPathSum2(root)
            return self.glb_max

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70]: /images/20221119/bc810c0571a442aa89927485b3e9eb48.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 1]: /images/20221119/df566568778546eda634bb5f3af0c685.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTU2ODg0OA_size_16_color_FFFFFF_t_70 2]: /images/20221119/7a279ae32323441abdaa12aaeddaa972.png