阿泳在快乐星球
0%

LeetCode热题100

发表于 更新于

LeetCode热题100

其实有听说这种按照不同技巧分类来做题会导致人很容易丧失遇到陌生题时的解题能力。但公司面试的算法考核基本就是原题或原题的变体，我觉得不如直接把题目特点和技巧总结一下从而快速达到应试水准比较有效率。

哈希

哈希就是映射，要考虑如何构建映射。

python中常用的构建映射的方法是字典：dict(), collections.defaultdict(List)

比如第一个题目双数之和通过target-num和其他的num值来构建映射。

第二个题目将排序后的字母组和排序前的字母组构建映射

第三个题目有点变态，他将给的数组看作是一个哈希表，因为直接找某个数是否在哈希表中的时间复杂度是$O(1)$，并且通过寻找num-1是否在nums中来减少不必要的运算从而将$O(n^2)$的时间复杂度变为了$O(n)$。

双指针

双指针就是使用两个标记来记录数组的位置

python中需要注意的是range（i，j）包括i但不到j

第一题通过j来记录非零的数目和需要替换的位置

第二题用ij记录两端位置，需要知道一点就是面积的宽由短边决定，因此只能移动短板

第三题需要注意排序后如何找，暴力枚举是三重循环，但很容易发现当固定$a+b+c$中的$a$时，当第二重循环$b’>b$，第三重循环找到的数值$c’<c$是一定的，因此第二重循环和第三重循环可以优化成双指针。

第四题可以用动态规划做，但是使用双指针会节省空间。需要想到当前接水量为$min(leftmax,rightmax)-height[当前]$，双指针$left,right$分别在两边，要知道在谁小谁移动的条件下，$left>right$时，$leftmax>rightmax$是一定的。通过反证法可以证明，如果$rightmax>leftmax$，当$left$到达$leftmax$且$right$在$rightmax$时，除非$leftmax>=rightmax$，否则他只能向右移动，并且最终得到$right>left$这与实际相反。

滑动窗口

就是用队列来进行插入删除

子串

第一题：和为k的子数组，用前缀和作差计算

第二题：求滑动窗口的最大值，优先队列，复合最小堆

第三题：最小的覆盖子串，利用双端指针，需要注意的是collections.Counter类的使用。

普通数组

第一题：最小前缀和

第二题：排序

第三题：连续反转数组

第四题：双数组前缀乘法（自己想的）；第二种不需要空间的方法是将一个数组作为输出另外一个数组用遍历去替代。

第五题：通过将数组转换成哈希，用正负和下标位置来表示标记。

矩阵

第一题：原文需要一种减少空间消耗的算法，因此使用标记来记录第一行和第一列是否需要置零，之后将第一行和第一列作为记录的空间。

第二题：使用模拟去解决问题，重要的是知道终止条件是m*n

第三题：原地旋转，需要注意终止条件是n//2

第四题：用Z字搜索，因为矩阵的行列按照升序排列，因此有一个特别好的性质，第一行的最后一列的数是第一行最大的，最后一列最小的，因此以此为起点，如果目标数比这个数大就往下找，如果目标数比这个数小就往左找。

链表

第一题：长度对齐+遍历

第二题：使用迭代，记录上次的指针

第三题：记录长度，折半，反转前面的列表，然后顺序遍历val

第四题：利用哈希表进行存储

第五题：与第四题相同，使用哈希存储

第六题：迭代

第七题：迭代

第八题：迭代

第九题：迭代，理清地址空间的交换

第十题：模拟，最好将翻转列表单独写一个函数

第十一题：递归+哈希

第十二题：递归+两个有序排列

第十三题：将十二题融合进来

第十四题：本来是用两个字典做，但是发现时间复杂度得要6*10的8次方，必须得要n或者常数，因此使用哈希和双向链表做。

二叉树

第一题：递归

第二题：遍历+函数列表（自己的做法），官方题解：深度优先搜索/广度优先搜索

第三题：广度优先搜索，需要知道python中list通常用于栈操作，而deque则为队列。

第四题：递归，对称=左子树镜像对称右子树=节点值相同+节点的左子树镜像对称另一节点的右子树，节点的右子树镜像对称另一节点的左子树。

第五题：递归，官方题解：深度优先搜索

第六题：递归

第七题：中序遍历（递归）+升序检验

第八题：中序遍历

第九题：递归，官方题解（深度优先+广度优先）

第十题：

python递归解法：认为当前节点的左子树和右子树都已经是先序顺序的链表了，因此将左子树放到右边，左子树的尾部接上右子树。可以发现我们需要两个返回值，一个是当前树的头，一个是当前树的尾。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def flatten(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        def digui(root):
            if root==None:
                return root,root
            
            root_left,tail_left = digui(root.left)
            root_right,tail_right = digui(root.right)
            if root_left==None and root_right==None:
                return root,root
            if root_left==None:
                return root,tail_right
            if root_right==None:
                root.left = None
                root.right = root_left
                return root,tail_left
            root.left = None
            root.right = root_left
            tail_left.right = root_right
            return root,tail_right
        digui(root)

第十一题：递归 ，这道题很难，很有意思

第十二题：双重递归（递归套递归）

((root->val == p->val || root->val == q->val) && (lson || rson))

第十三题：最大单向（简化递归）。

图论

第一题：深度优先算法，但值得注意的是他在外面用了迭代，并且传进去的数值会将原本图上的值设置为0

第二题：深度优先，为什么要用深度优先？因为橘子腐烂是一个最短路径问题，而BFS可以看作是层序遍历，依次到达距离为1，2，3的节点。

第三题：广度优先，如何记录节点的入度。

第四题：使用字典树，重点在于使用类嵌套类来制作一个类似于链表的结构，因为树基本都是用链表来做的。

回溯

回溯类型的题有个特征就是在有限集中不断生成解，解题思路通常是递归中有循环，添加——递归——删除。(记得标注局部变量。)

第一题-46. 全排列：利用递归进行操作（递归变体技巧，不返回，直接操作原数组），输入是不断向后的，找到的是前面固定，后面的数组。

第二题-78. 子集：直接暴力求解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        temp = []
        res = []
        def backtrack(first):
            res.append(copy.deepcopy(temp))
            for i in range(first,n):
                temp.append(nums[i])
                backtrack(i+1)
                temp.remove(nums[i])
        backtrack(0)
        return res

第三题-17. 电话号码的字母组合：回溯，利用hash，之后添加一个——递归下一个数——删除刚刚添加的那个，终止条件是全部输入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        hashtable = ["abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"]
        n = len(digits)
        if n==0:return []
        res = []
        self.temp = ""
        def backdraw(first):
            if first==n:   
                res.append(copy.deepcopy(self.temp))
                return
            for ch in hashtable[int(digits[first])-2]:
                self.temp = self.temp + ch
                backdraw(first+1)
                self.temp = self.temp[:len(self.temp)-1]
        backdraw(0)
        return res

第四题-39. 组合总和：一样是回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
        def backdraw(first):
            nonlocal temp_sum,temp_list
            for i in range(first,n):
                if temp_sum+candidates[i]==target:
                    temp_list.append(candidates[i])
                    res.append(copy.deepcopy(temp_list))
                    temp_list.pop()
                    return
                if temp_sum+candidates[i]>target:
                    continue
                if temp_sum+candidates[i]<target:
                    temp_list.append(candidates[i])
                    temp_sum+=candidates[i]
                    backdraw(i)
                    temp_list.pop()
                    temp_sum-=candidates[i]
        candidates.sort()
        res = []
        temp_list = []
        temp_sum = 0
        n = len(candidates)
        backdraw(0)
        return res

第五题-22. 括号生成：统计左右两边括号数量+回溯

第六题-79. 单词搜索：图论的知识+回溯，用回溯的原因主要是一个单词不能重复访问。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        n = len(word)
        r,c = len(board),len(board[0])
        visited = [[False]*c for _ in range(r)]
        def backdraw(i,j,position):
            if position == n:return True
            for temp_i,temp_j in [[i-1,j],[i+1,j],[i,j-1],[i,j+1]]:
                if 0<=temp_i<r and 0<=temp_j<c and visited[temp_i][temp_j]==False:
                    if board[temp_i][temp_j]==word[position]:
                        visited[temp_i][temp_j]=True
                        if backdraw(temp_i,temp_j,position+1):
                            return True
                        visited[temp_i][temp_j]=False
            return False
        res = False
        for i in range(r):
            for j in range(c):
                if board[i][j]==word[0]:
                    visited[i][j]=True
                    res = backdraw(i,j,1)
                    if res:return res
                    visited[i][j]=False
        return res

第七题-131. 分割回文串：我使用动态+暴力的解法，但将判断回文串用动态规划替代能节省大量时间空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution:
    def partition(self, s: str) -> List[List[str]]:
        def ishuiwen(zhan):
            n = len(zhan)
            if n==1:return True
            temp = []
            for i in range(n//2):
                temp.append(zhan[i])
            if n%2==1:
                midposition = n//2+1
            else:
                midposition = n//2
            for i in range(midposition,n):
                temp_node = temp.pop()
                if temp_node != zhan[i]:
                    return False
            return True
            
        def backdraw(last,first):
            nonlocal temp_res,res
            if first==length:
                res.append(copy.deepcopy(temp_res))
            for i in range(first,length):
                print(ishuiwen(s[last:i+1]),s[last:i+1])
                if ishuiwen(s[last:i+1]):
                    temp_res.append(copy.deepcopy(s[last:i+1]))
                    backdraw(i+1,i+1)
                    temp_res.pop()
     
        # temp_word = ""
        length = len(s)
        temp_res = []
        res = []
        backdraw(0,0)
        return res

第八题-51. N 皇后：重点在于如何表示斜线，用行-列和行+列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        def backtrack(r):
            if r == n:
                temp = []
                for i in range(n):
                    row[queens[i]]="Q"
                    temp.append("".join(row))
                    row[queens[i]]="."
                solution.append(temp)
            else:
                for i in range(n):
                    if i not in columns and r-i not in diagnal1 and r+i not in diagnal2:
                        queens[r]=i
                        columns.add(i)
                        diagnal1.add(r-i)
                        diagnal2.add(r+i)
                        backtrack(r+1)
                        diagnal2.remove(r+i)
                        diagnal1.remove(r-i)
                        columns.remove(i)
                        queens[r]=-1
        
        solution = []
        queens = [-1]*n
        columns = set()
        diagnal1 = set()
        diagnal2 = set()
        row = ["."]*n
        backtrack(0)
        return solution

二分查找

问题特点：题目数据通常为升序正序

二分查找通常使用三个指针，left，right和ans，分别为0，n-

，n。ans返回的是大于等于target的第一个位置（当判别等式是target<=mid，如果判别等式是target<mid，则求的是大于target的第一个位置）。迭代循环的截至条件通常是while left<=right.

第一题-35. 搜索插入位置：二分查找，但要注意的是要保留最右边的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1
        ans = len(nums)
        while left<=right:
            mid = (left+right)//2
            if target<=nums[mid]:
                ans = mid
                right = mid-1
            else:
                left = mid+1
        return  ans

第二题-74. 搜索二维矩阵：将二维矩阵转换为一维矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        r,c = len(matrix),len(matrix[0])
        left,right= 0,r*c-1
        while left<=right:
            mid = (left+right)//2
            i,j = mid//c,mid%c
            if target==matrix[i][j]:
                return True
            if target<matrix[i][j]:
                right = mid-1
            else:
                left = mid+1
        return False

第三题-34. 在排序数组中查找元素的第一个和最后一个位置：二分查找+向左向右搜索,但这个方法在最坏的情况下是$O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        left,right,mid = 0,len(nums)-1,len(nums)
        res = -1
        while left<=right:
            mid = (left+right)//2
            if target==nums[mid]:
                res = mid
                break
            if target<nums[mid]:
                right = mid-1
            else:
                left = mid+1
        if res!=-1:
            left = mid
            while left>0 and nums[left-1]==target:
                left-=1
            right = mid
            while right<len(nums)-1 and nums[right+1]==target:
                right+=1
        else:
            left = right = res
        return [left,right]

第四题-33. 搜索旋转排序数组：先找到旋转的位置的二分查找，再根据最后一个数值与target的关系来进行选择left，right的值，之后就是正常的二分查找。还是官方题解的思路清晰一点，只要明确一点，就是当前一半无序另外一半一定是有序的，这道题就很好想出官方的题解来。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left,right,ans = 0, len(nums)-1,len(nums)-1
        end = nums[right]
        while left<=right:
            mid = (left+right)//2
            if end<=nums[mid]:
                left = mid+1
            else:
                ans = mid
                right = mid-1
        # print(ans,end,target)
        if len(nums)==1:
            left,right,ans = 0, len(nums)-1,len(nums)
        else:
            if end==target:
                return len(nums)-1
            if end<target:
                left,right,ans = 0, ans,len(nums)
            else:
                left,right,ans = ans,len(nums)-1,len(nums)
        print(left,right,ans)
        while left<=right:
            mid = (left+right)//2
            if target<=nums[mid]:
                ans = mid
                right = mid-1
            else:
                left = mid+1
        if 0<=ans<len(nums) and nums[ans]==target:
            return ans
        return -1

第五题-153. 寻找旋转排序数组中的最小值：遇上一题类似，思考了半天为什么ans要放在这里，发现初始化的时候就是ans = right+1，所以在处理的时候也最好要这样（直觉）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findMin(self, nums: List[int]) -> int:
        left,right,ans = 0,len(nums)-1,len(nums)-1
        end = nums[right]
        if nums[left]<=nums[right]:return nums[left]
        while left<=right:
            mid = (left+right)//2
            if end>=nums[mid]:
                ans = mid
                right = mid-1
            else:
                left = mid+1
                
                
        return nums[ans]

第六题-4. 寻找两个正序数组的中位数：先将问题转化成寻找两个升序数组中的第k个元素，再考虑将k对半找，并删除小的那部分的前面元素，并更新k。需要注意的点有终止条件（k=1或者有任意数组访问完），将k对半找时触碰上界问题（更新k值策略）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        def search(k):
            index1,index2=0,0
            while True:
                if index1==m:
                    return nums2[index2+k-1]
                if index2==n:
                    return nums1[index1+k-1]
                if k==1:
                    return min(nums1[index1],nums2[index2])
                newindex1 = min(index1 + k//2 - 1,m-1)
                newindex2 = min(index2 + k//2 - 1,n-1)
                if nums1[newindex1]<=nums2[newindex2]:
                    k = k - (newindex1 - index1 + 1)
                    index1 = newindex1+1
                else:
                    k = k - (newindex2 - index2 +1)
                    index2 = newindex2+1
                    
        m,n = len(nums1),len(nums2)
        if (m+n)%2==1:
            return search((m+n+1)//2)
        else :
            return (search((m+n)//2)+search((m+n)//2+1))/2

栈

问题特点：找左右括号，记录某些特定数据（最大最小符号中记录数字）

第一题-20. 有效的括号：使用栈和哈希进行处理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def isValid(self, s: str) -> bool:
        left = ['(','{','[']
        right = [')','}',']']
        hashtable = {'(':')','{':'}','[':']'}
        zhan = []
        for ch in s:
            if ch in left:
                zhan.append(ch)
            else:
                if len(zhan)==0:
                    return False
                temp = zhan.pop()
                if hashtable[temp]!=ch:
                    return False
        if len(zhan)!=0:
            return False
        return True

第二题-155. 最小栈：维护两个栈，一个普通栈，一个降序栈。官方的解法比我想的解法优化许多，尤其是降序栈的操作，他直接维护了一个辅助栈，统计当前元素及下面的最小值，这是因为只要a没被弹出，a下面的元素也不会被弹出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MinStack:

    def __init__(self):
        self.stack = []
        self.minstack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        temp = []
        while len(self.minstack)!=0 and val>self.minstack[-1]:
            temp.append(self.minstack.pop())
        self.minstack.append(val)
        while len(temp)!=0:
            self.minstack.append(temp.pop())

    def pop(self) -> None:
        temp_val = self.stack.pop()
        temp = []
        while temp_val!=self.minstack[-1]:
            temp.append(self.minstack.pop())
        self.minstack.pop()
        while len(temp)!=0:
            self.minstack.append(temp.pop())
        # print(self.stack)

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.minstack[-1]



# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

第三题-394. 字符串解码：只要不是右括号就一直入栈，找到右括号的话往前找左括号，并将中间的内容加入临时栈，记录重复次数，将重复后的数据加入栈。这种情况也考虑了括号套括号的情况，因为在找到第二个括号时，第一个括号的内容已经重复过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution:
    def decodeString(self, s: str) -> str:
        res = []
        for ch in s:
            #只要不是右括号就一直入栈
            if ch!="]":
                res.append(ch)
            else:
                #将左括号前的加入临时栈
                temp = []
                while res[-1]!="[":
                    top = res.pop()
                    temp.append(top)
                res.pop()
                #统计左括号前的数字
                temp_c = 1
                num = 0
                while len(res)!=0 and ord("0")<=ord(res[-1])<=ord("9"):
                    num += int(res.pop())*temp_c
                    temp_c *=10
                #将括号内容循环num边
                for _ in range(num):
                    temp_n = len(temp)
                    for _1 in range(temp_n-1,-1,-1):
                        res.append(temp[_1])
        return "".join(res)

第四题-739. 每日温度：用一个单调栈（记录的数据的位置，大小是按照数字判断）来进行辅助，先将第一个数的位置压入栈，从第二个数开始，只要数比栈顶数大就弹出栈顶元素，并记录位置差距作为结果，直到栈为空或者不在大于栈顶元素。之后将当前数的位置压入栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        n = len(temperatures)
        res = [0]*n
        temp = []
        temp.append(0)
        for i in range(1,n):
            while len(temp)!=0 and temperatures[i]>temperatures[temp[-1]]:
                if temperatures[i]>temperatures[temp[-1]]:
                    res[temp[-1]]=i - temp[-1]
                    temp.pop()
            temp.append(i)
        return res

第五题-84. 柱状图中最大的矩形：

  • 对数组中的每个元素，若假定以它为高，能够展开的宽度越宽，那么以它为高的矩形面积就越大。
  • 因此，思路就是找到每个元素左边第一个比它矮的矩形和右边第一个比它矮的矩形，在这中间的就是最大宽度
  • 最后对每个元素遍历一遍找到最大值即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        left,right = [0]*n,[0]*n
        left_stack = []
        for i in range(n):
            while left_stack and heights[i]<=heights[left_stack[-1]]:
                left_stack.pop()
            if left_stack:
                left[i] = left_stack[-1]
            else:
                left[i] = -1
            left_stack.append(i)
        right_stack = []
        for i in range(n-1,-1,-1):
            while right_stack and heights[i]<=heights[right_stack[-1]]:
                right_stack.pop()
            if right_stack:
                right[i] = right_stack[-1]
            else:
                right[i] = n
            right_stack.append(i)
        max_num = max((right[i]-left[i]-1)*heights[i] for i in range(n)) if n>0 else 0
        return max_num

堆

具体实现原理

堆必须是一个完全二叉树（除最后一行外必须全满，并且最后一行也是顺序填满），分为最大堆和最小堆。

堆通常使用数组存储，节点下标为i，左子节点为2i+1，右子节点为2i+2.

下滤为只有根节点不满足堆序性。上滤为叶子节点不满足堆序性（通常为插入新节点）。

自顶向下建堆使用上滤，自下而上建堆为使用下滤。

第一题-215. 数组中的第K个最大元素：堆排序

1
2
3
4
5
6
7
8
9
class Solution:
    def findKthLargest(self, nums: List[int], k: int) -> int:
        vsited = []
        for num in nums:
            heapq.heappush(vsited,-num)
        while k!=0:
            res = -heapq.heappop(vsited)
            k-=1
        return res

第二题-347. 前 K 个高频元素：哈希+最小堆

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        dicttemp = {}
        for num in nums:
            if num in dicttemp:
                dicttemp[num]+=1
            else:
                dicttemp[num]=1
        temp = []
        for key in dicttemp:
            # print(temp)
            value = dicttemp[key]
            if len(temp)<k:
                heapq.heappush(temp,(value,key))
            else:
                if value>temp[0][0]:
                    heapq.heappop(temp)
                    heapq.heappush(temp,(value,key))
        res = [val for key,val in temp]
        return res

第三题-295. 数据流的中位数：记录中位数，实际的中位数和左右两边的堆。通过插入时平衡两边的堆来进行操作。官解没有记录中位数，而只是使两边的堆平衡。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class MedianFinder:

    def __init__(self):
        self.leftheap = []
        self.rightheap = []
        self.midnum = 0
        self.flag = False
        self.leftnum = 0
        self.rightnum = 0
        self.Median = 0

    def addNum(self, num: int) -> None:
        if self.flag:
            if num>=self.midnum:
                heapq.heappush(self.rightheap,num)
                self.rightnum+=1
            else:
                heapq.heappush(self.leftheap,-num)
                self.leftnum+=1
            chayi = abs(self.rightnum-self.leftnum)
            if chayi == 0: self.Median = self.midnum
            if chayi==1:
                if self.rightnum>self.leftnum:
                    self.Median = (self.midnum+self.rightheap[0])/2
                else:
                    self.Median = (self.midnum-self.leftheap[0])/2
            if chayi == 2:
                if self.rightnum>self.leftnum:
                    heapq.heappush(self.leftheap,-self.midnum)
                    self.midnum = heapq.heappop(self.rightheap)
                    self.Median = self.midnum
                    self.rightnum-=1
                    self.leftnum+=1
                else:
                    heapq.heappush(self.rightheap,self.midnum)
                    self.midnum = -heapq.heappop(self.leftheap)
                    self.Median = self.midnum
                    self.leftnum-=1
                    self.rightnum+=1
        else:
            self.midnum = num
            self.Median = num
            self.flag = True

    def findMedian(self) -> float:
        # print(self.leftheap)
        return self.Median


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

贪心算法

第一题-121. 买卖股票的最佳时机：因为买入和卖出都是按照时间顺序进行的，因此在进行到时间t时想超过之前的最优策略（t之前最低点买入，最高点卖出）只有在出现比最低点买入更低的时候才会出现，因为只要比之前的买入点高，哪怕后续最高点更新也是t之前的那个低点更优。因此用单调栈来存储数据，只要比栈顶元素小就加入，否则的话计算收益比较历史最佳收益。

1
2
3
4
5
6
7
8
9
10
class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_stack  = []
        res = 0
        for price in prices:
            if not min_stack or price<=min_stack[-1]:
                min_stack.append(price)
            else:
                res= max(res,price-min_stack[-1])
        return res

第二题-55. 跳跃游戏：记录最远的可达距离，但在遍历数组的时候需要注意当前的位置是否可达，才能继续记录最远可达的距离。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n = len(nums)
        history_max = 0
        for i,num in enumerate(nums):
            if history_max>=i:
                history_max = max(history_max,i+num)
        if history_max>=n-1:
            return True
        else:
            return False

第三题-45. 跳跃游戏 II：与上一题的区别在于记录最近的步数，因此使用一个数组来存储到达此节点的最近。最近指的是第一个节点到达此节点，以及数组初始节点到达这个第一个节点的次数+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        corder = [0]*n
        corder[0]=1
        history_max = 0
        for i,num in enumerate(nums):
            if corder[i]==0:
                continue
            for j in range(history_max+1,min(num+i+1,n)):
                corder[j] = corder[i]+1
            history_max = max(history_max,num+i)
        return corder[-1]-1

第四题-763. 划分字母区间：哈希+贪心

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        hashtable = collections.defaultdict(list)
        for i,ch in enumerate(s):
            hashtable[ch].append(i)
        start_position = hashtable[s[0]][0]
        end_position = hashtable[s[0]][-1]
        res = []
        for i,ch in enumerate(s):
            if start_position<=i<=end_position:
                end_position = max(end_position,hashtable[ch][-1])
            else:
                res.append(end_position-start_position+1)
                start_position = hashtable[ch][0]
                end_position = hashtable[ch][-1]
        res.append(end_position-start_position+1)
        return res

动态规划

问题特点：记录之前状态信息。通过避免重复运算来优化算法。先考虑暴力搜索的解法，发现有重复运算就是用“记忆化搜索”（又称动态规划）

第一题-70. 爬楼梯：有点像斐波那契数列

1
2
3
4
5
6
7
8
class Solution:
    def climbStairs(self, n: int) -> int:
        table = [0]*(n+1)
        table[0]=1
        table[1]=1
        for i in range(2,n+1):
            table[i] = table[i-1]+table[i-2]
        return table[n]

第二题-118. 杨辉三角：简单题，没啥好说的。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        res = []
        for i in range(1,numRows+1):
            res.append([1]*i)
        if numRows<=2:return res

        for i in range(2,numRows):
            for j in range(1,i):
                res[i][j] = res[i-1][j-1]+res[i-1][j]
        return res

第三题-198. 打家劫舍：动态规划，使用一个数组记录到当前房间能拿的最多的钱，对于k>2的房间，如果拿，那么不能拿k-1的房间，因此金额为k-2的最高金额+k房间的钱。如果不拿，那么金额为k-1的最高金额。比较他俩的大小决定拿或者不拿。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def rob(self, nums: List[int]) -> int:
        if not nums:return 0

        n = len(nums)
        if n ==1:
            return nums[0]
        
        dp = [0]*n
        dp[0] = nums[0]
        dp[1] = max(nums[0],nums[1])
        for i in range(2,n):
            dp[i] = max(dp[i-2]+nums[i],dp[i-1])
        return dp[n-1]

第四题-279. 完全平方数：如果使用dp来记录每个数的完全平方数，然后减去该值，再找剩下的重新来一遍，我猜会超时。因此如何重复利用dp信息来避免重复计算是解题重点，一个思路是快速寻找到这个值在那两个最小平方数之间。

官解构建的状态转移等式是使用记录当前数最少的完全平方数，然后统计每个数i中j*j到剩余的值所需的最少完全平方数，这个数+1来跟最小值对比。

1
2
3
4
5
6
7
8
9
class Solution:
    def numSquares(self, n: int) -> int:
        dq = [0]*(n+1)
        for i in range(1,n+1):
            minn = n
            for j in range(1,int(i**0.5)+1):
                minn = min(minn,dq[i-j*j])
            dq[i] = minn+1
        return dq[n]

第五题-322. 零钱兑换：和上一题很像，不过需要判定有没有这种类型的硬币已经判定某金额能不能达到。但是题解是直接将inf作为没找到的条件，我是直接在每次判别的时候需要查看该金额能否达到。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dq = [-1]*(amount+1)
        dq[0]=0
        for i in range(1,amount+1):
            if i in coins:
                dq[i]=1
            else:
                flag = 0
                minn = float(inf)
                for coin in coins:
                    if coin<i and dq[i-coin]>-1:
                        flag = 1
                        minn = min(minn,dq[i-coin])
                if flag == 1:
                    dq[i] = minn+1
        return dq[amount]

第六题-139. 单词拆分：统计最后一个成单词的位置，将他添加到列表。对于每个字母，统计列表中的位置到当前的位置是否成单词，成单词就添加进列表。最后看最后一个位置是否添加进列表。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def wordBreak(self, s: str, wordDict: List[str]) -> bool:
        n = len(s)
        last_set = [0]
        for i in range(0,n):
            for last in last_set:
                # print(s[last:i+1])
                if s[last:i+1] in wordDict:
                    last_set.append(i+1)
                    break 
        # print(last_set)
        if n in last_set:return True
        else:return False

第七题-300. 最长递增子序列：经典题目，我发现做动态规划很多题目都是1到n中循环套1到i，i是1到n之间的位置。

1
2
3
4
5
6
7
8
9
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n= len(nums)
        dp = [1]*n
        for i in range(n):
            for j in range(0,i):
                if nums[i]>nums[j]:
                    dp[i] = max(dp[i],dp[j]+1)
        return max(dp)

第八题-152. 乘积最大子数组：因为负负的正，因此一个dp考虑最大一个dp考虑最小。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def maxProduct(self, nums: List[int]) -> int:
        n = len(nums)
        dpmin = [0]*n
        dpmin[0] = nums[0]
        dpmax = [0]*n
        dpmax[0] = nums[0]
        for i in range(1,n):
            dpmax[i] = max(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])
            dpmin[i] = min(dpmax[i-1]*nums[i],dpmin[i-1]*nums[i],nums[i])
        # print(dpmax,dpmin)
        return max(dpmax)

第九题-416. 分割等和子集：如何使用二维的动态规划进行设计。每个位置i，j表示在第i个数的位置前能否找到达到target的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        n = len(nums)

        if n<2:return False

        total = sum(nums)

        if total%2 ==1:
            return False

        target = total//2
        maxnum = max(nums)

        if maxnum>target:return False

        dp = [[False] * (target+1) for _ in range(n)]
        for i in range(n):
            dp[i][0] = True

        dp[i][nums[0]] = True
        for i in range(1,n):
            num = nums[i]
            for j in range(1,target+1):
                if j>=num:
                    dp[i][j] = dp[i-1][j] | dp[i-1][j-num]
                else:
                    dp[i][j] = dp[i-1][j]
        
        return dp[n-1][target]

第十题-32. 最长有效括号：难点在于如何判定是有效括号并且怎么从之前的最多括号转移到当前的括号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)
        if n==0:return 0
        dp = [0]*n
        for i in range(n):
            if s[i] == ")" and i>0 and s[i-1]=="(":
                if i>1:
                    dp[i] = dp[i-2]+2
                else:
                    dp[i] = 2
            if s[i] == ")" and i>0 and s[i-1]==")":
                if i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=="(":
                    if i-dp[i-1]-2>=0:
                        dp[i] = dp[i-1] + dp[i-dp[i-1]-2]+2
                    else:
                        dp[i] = dp[i-1]+2
        return max(dp)

多维动态规划

第一题-62. 不同路径：太经典的二位动态数组了，以至于看一眼就知道做法。先构建第一行第一列，然后dp保存的是来到该位置的路径，它由上左的dp构成。

1
2
3
4
5
6
7
8
9
10
11
class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [[0]*n for _ in range(m)]
        for i in range(m):
            dp[i][0] = 1
        for i in range(n):
            dp[0][i] = 1
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = dp[i-1][j]+dp[i][j-1]
        return (dp[m-1][n-1])

第二题-64. 最小路径和：和第一题不能说毫不相关，只能说是完全一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m,n = len(grid),len(grid[0])
        dp = [[0]*n for _ in range(m)]
        dp[0][0] = grid[0][0]
        for i in range(1,m):
            dp[i][0] = dp[i-1][0]+grid[i][0]
        for i in range(1,n):
            dp[0][i] = dp[0][i-1]+grid[0][i]
        for i in range(1,m):
            for j in range(1,n):
                dp[i][j] = min(dp[i-1][j],dp[i][j-1])+grid[i][j]
        # print(dp)
        return dp[m-1][n-1]

第三题-5. 最长回文子串：可以看到最长回文串的判定是有重复计算的，因此考虑使用动态规划来进行，主要是通过长回文串两端如果相等，那中间的段落如果是回文串的话那这就是个回文串，例如 ababa，如果a=a，那么中间的bab如果相等话就是回文串。因此使用一个二维数组来记录回文串状态，ap[i][j]表示从i到j的字符串是回文串。只有一个字母的是回文串，两个字母的需要进行判断，循环从三个字母开始，i表示回文串的长度，从2（0，1，2其实第三个数了），j表示起点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def longestPalindrome(self, s: str) -> str:
        n = len(s)
        if n==0:return ""
        dp = [[0]*n for _ in range(n)]
        maxx = 0
        max_ij = [0,0]
        for i in range(n):
            dp[i][i] = 1
        for i in range(1,n):
            if s[i-1]==s[i]:
                dp[i-1][i]=1
                maxx = 2
                max_ij = [i-1,i]
        for i in range(2,n):
            for j in range(n):
                if j+i<n and s[j]==s[j+i] and dp[j+1][j+i-1]==1:
                    dp[j][j+i] = 1
                    maxx = i+1
                    max_ij = [j,j+i]
        return s[max_ij[0]:max_ij[1]+1]

第四题-1143. 最长公共子序列：典型动态规划，dp【i】【j】表示text1【：i】和text2【：j】的最长公共子序列。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def longestCommonSubsequence(self, text1: str, text2: str) -> int:
        n1 = len(text1)
        n2 = len(text2)
        dp = [[0]*(n2+1) for i in range(n1+1)]
        for i in range(1,n1+1):
            for j in range(1,n2+1):
                if text1[i-1]==text2[j-1]:
                    dp[i][j] = dp[i-1][j-1]+1
                else:
                    dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        return dp[n1][n2]

第五题-72. 编辑距离：动态规划，dp【i】【j】表示word1【：i】和word2【：j】的最短距离，并且明确一点，对1删除一个元素和对2添加一个元素是等价的，因此dp【i-1】【j】到dp【i】【j】为+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m,n = len(word1), len(word2)
        if m==0:return n
        if n==0:return m
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(m+1):
            dp[i][0] = i
        for j in range(n+1):
            dp[0][j] = j
        for i in range(1,m+1):
            for j in range(1,n+1):
                left = dp[i-1][j]+1
                right = dp[i][j-1]+1
                left_right = dp[i-1][j-1]
                if word1[i-1]!=word2[j-1]:
                    left_right+=1
                dp[i][j] = min(left,right,left_right)
        return dp[m][n]

技巧

第一题-136. 只出现一次的数字：利用哈希表解决，但这样空间不是常数。题解是使用异或来做的。

1
2
3
4
5
6
7
8
9
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hashtable = []
        for num in nums:
            if num not in hashtable:
                hashtable.append(num)
            else:
                hashtable.remove(num)
        return hashtable[0]

第二题-169. 多数元素：用哈希表解决，但要知道max如何通过lambda匿名函数来进行求解，lambda后面的对象指的是每次max迭代中前面对象需要拿出来对比大小的对象，比如在字典中，拿出来的就是key，在二维数组中，拿出来的就是每一行。

1
2
3
4
5
6
7
8
9
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        counts = {}
        for num in nums:
            if num not in counts:
                counts[num] = 1
            else:
                counts[num]+=1
        return max(counts,key = lambda k:counts[k])

第三题-75. 颜色分类：使用快排解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        def quick_sort(nums,left,right):
            if left>=right:
                return
            shaobing = switch(nums,left,right)
            quick_sort(nums,left,shaobing-1)
            quick_sort(nums,shaobing+1,right)
        def switch(nums,left,right):
            i,j = left,right
            while i<j:
                while i<j and nums[j]>=nums[left]:
                    j-=1
                while i<j and nums[i]<=nums[left]:
                    i+=1
                nums[i],nums[j] = nums[j],nums[i]
            nums[left],nums[i] = nums[i],nums[left]
            return i
        quick_sort(nums,0,len(nums)-1)
        return

第四题-31. 下一个排列：两边搜索，将从后到前找到一个数比这个数大，并且这个大的数是较小的大的数。第一遍搜索，找到【i】<【i+1】的数，然后第二遍从后往前搜索（此时这个搜索是一个降序）找到一个数比这个数大。并且将这两个数交换后，【i+1】之后的数要改成升序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)-2
        while n>=0 and nums[n]>=nums[n+1]:
            n-=1
        if n>=0:
            switch = len(nums)-1
            while nums[n]>=nums[switch]:
                switch-=1
            nums[n],nums[switch] = nums[switch],nums[n]
        left,right = n+1,len(nums)-1
        while left<right:
            nums[left],nums[right] = nums[right],nums[left]
            left+=1
            right-=1
        return

第五题-287. 寻找重复数：修改nums空间

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        i = 0
        while True:
            temp = nums[i]
            if temp == i+1:
                i +=1
            else:
                if nums[temp-1]==temp:
                    return temp
                else:
                    nums[temp-1],nums[i] = nums[i],nums[temp-1]

题解-二分查找，二分查找的是1到n的这个数组而不是原本的数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        left,right = 1,n-1
        while left<right:
            mid = (left+right)//2
            count = 0
            for num in nums:
                if num<=mid:
                    count+=1
            if count>mid:
                right = mid
            else:
                left = mid+1
        return left