目录

三个月算法进阶--day86

2020-11-17 约 462 字预计阅读 1 分钟次阅读

目录

回顾

85天的算法学习与练习改变了我的认知，只要肯下功夫去理解，就能真正有收获。整个过程的体验也是由难入易的，开始的不顺利、不舒适、坐在屏幕前大半小时无法动手的经历难以忘怀，但是逐渐就变得轻松，变得很好接受。具体在什么时候产生的变化我不知道，但是前后的感受都尤为真实明显。

算法学习除了改变了我的认知，还神奇地改变了我的生活，教我平静，教我思考，教我坚持。世上无难事，只要肯登攀，认准的事情坚持下去收获自然而来。

离三个月算法进阶的期限还有五天，接下来这几天我将整理之前的文档，提取重难点，二刷关键题，加快记忆的步伐。这就类似经历了一学期的学习，又即将面临考试的复习那样，不可或缺。

全排列

class Solution:
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        def backtrack(first = 0):
            # 所有数都填完了
            if first == n:  
                res.append(nums[:])
            for i in range(first, n):
                # 动态维护数组
                nums[first], nums[i] = nums[i], nums[first]
                # 继续递归填下一个数
                backtrack(first + 1)
                # 撤销操作
                nums[first], nums[i] = nums[i], nums[first]
        
        n = len(nums)
        res = []
        backtrack()
        return res

最大子序和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        res = nums[0]
        for i in range(1, len(nums)):
            nums[i] = max(nums[i-1] + nums[i], nums[i])
            res = max(nums[i], res)
        return res

盛最多水的容器

class Solution:
    def maxArea(self, height: List[int]) -> int:
        start = 0
        end = len(height) - 1
        area = 0
        while start < end:
            tmp = min(height[start], height[end]) * (end - start)
            area = tmp if tmp >= area else area
            if height[start] >= height[end]:
                end -= 1
            else:
                start += 1
        return area