Skip to content

Latest commit

 

History

History
4405 lines (3261 loc) · 137 KB

合集-热门&经典&易错.md

File metadata and controls

4405 lines (3261 loc) · 137 KB
Raw

热门&经典&易错

Problems

LeetCode 0072 编辑距离 (困难, 2022-01)

动态规划 经典 LeetCode

问题简述 
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。
详细描述 
给你两个单词 word1 和 word2，请你计算出将 word1 转换成 word2 所使用的最少操作数。

你可以对一个单词进行如下三种操作：
    插入一个字符
    删除一个字符
    替换一个字符

示例 1：
    输入：word1 = "horse", word2 = "ros"
    输出：3
    解释：
    horse -> rorse (将 'h' 替换为 'r')
    rorse -> rose (删除 'r')
    rose -> ros (删除 'e')
示例 2：
    输入：word1 = "intention", word2 = "execution"
    输出：5
    解释：
    intention -> inention (删除 't')
    inention -> enention (将 'i' 替换为 'e')
    enention -> exention (将 'n' 替换为 'x')
    exention -> exection (将 'n' 替换为 'c')
    exection -> execution (插入 'u')

提示：
    0 <= word1.length, word2.length <= 500
    word1 和 word2 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/edit-distance
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路

  • 动态规划经典问题 > 编辑距离 - 力扣官方题解

  • Tips：“插入”和“删除”操作可以认为是同一种操作，因为编辑距离具有对称性，在一方中插入，等价于在另一方删除，这有助于理解代码；

Python 
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        m = len(word1)
        n = len(word2)

        if m * n == 0:  # 其中一个是空串
            return m + n
        
        dp = [[0] * (n + 1) for _ in range(m + 1)]  # m * n
        
        for i in range(1, m + 1):
            dp[i][0] = i
        for i in range(1, n + 1):
            dp[0][i] = i
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                r1 = dp[i - 1][j] + 1
                r2 = dp[i][j - 1] + 1
                r3 = dp[i - 1][j - 1]
                if word1[i - 1] != word2[j - 1]:
                    r3 += 1
                dp[i][j] = min(r1, r2, r3)
        
        return dp[m][n]

优化：利用滚动数组将空间复杂度从 O(MN) 优化到 min(O(N), O(M))

Python 
class Solution:
    def minDistance(self, word1: str, word2: str) -> int:

        m = len(word1)
        n = len(word2)

        if m * n == 0:  # 其中一个是空串
            return m + n

        if m < n:
            m, n = n, m
            word1, word2 = word2, word1
        
        dp_pre = [0] * (n + 1)
        for i in range(1, n + 1):
            dp_pre[i] = i
        
        for i in range(1, m + 1):
            dp_cur = [i] + [0] * n
            for j in range(1, n + 1):
                r1 = dp_cur[j - 1] + 1
                r2 = dp_pre[j] + 1
                r3 = dp_pre[j - 1]
                if word1[i - 1] != word2[j - 1]:
                    r3 += 1
                dp_cur[j] = min(r1, r2, r3)
            dp_pre = dp_cur
        
        return dp_cur[n]

LeetCode 0300 最长递增子序列 (中等, 2022-01)

动态规划 贪心 经典 LeetCode

问题简述 
给定整数数组 nums，返回最长严格递增子序列的长度；
进阶：
    你可以设计时间复杂度为 O(N^2) 的解决方案吗？
    你能把时间复杂度降到 O(NlogN) 吗?
详细描述 
给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

子序列是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1：
    输入：nums = [10,9,2,5,3,7,101,18]
    输出：4
    解释：最长递增子序列是 [2,3,7,101]，因此长度为 4 。
示例 2：
    输入：nums = [0,1,0,3,2,3]
    输出：4
示例 3：
    输入：nums = [7,7,7,7,7,7,7]
    输出：1

提示：
    1 <= nums.length <= 2500
    -104 <= nums[i] <= 104

进阶：
    你可以设计时间复杂度为 O(n2) 的解决方案吗？
    你能将算法的时间复杂度降低到 O(n log(n)) 吗?

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-increasing-subsequence
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：动态规划

状态定义：dp[i] 表示以 nums[i] 结尾的最长递增子序列长度；

不能将 dp[i] 定义 nums[:i] 子数组中的最长递增子序列长度，虽然这样定义很直观，但它不满足最优子结构的条件，简单来说，就是你无法通过 dp[i-1] 得到 dp[i]。

Python 
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        
        ret = 1
        dp = [1] * len(nums)
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:  # 如果要求非严格递增，将 '>' 改为 '>=' 即可
                    dp[i] = max(dp[i], dp[j] + 1)
            
            ret = max(ret, dp[i])
        
        return ret
思路2：优化 DP 的状态定义
  • 考虑新的状态定义：dp[i] 表示长度为 i + 1 的最长递增子序列末尾的最小值；

    dp 序列一定时单调递增的，可用反证法证明，详见：最长递增子序列（动态规划 + 二分查找，清晰图解） - Krahets

    该怎么想出这个定义？——多看多做

  • 是否满足最优子结构？
    • 即已知 dp[i - 1] 能否递推得到 dp[i] ；显然是可以的，当nums[i] > dp[i - 1]时，长度 +1，否则，长度不变；
  • 如何更新dp？
    • 当 nums[i] > dp[i - 1] 时，直接添加到末尾；
    • 否则，要看是否需要更新 dp。根据 dp 递增的性质，找到 nums[i] 在 dp 中应该插入的位置，记 idx；比较 dp[idx] 与 nums[i] 的大小，如果 dp[idx] > nums[i] 根据定义，更新 dp[idx] = nums[i]；

从“贪心”角度来解释以上过程：如果我们要使上升子序列尽可能的长，则应该让序列上升得尽可能慢，即每次在上升子序列最后加上的那个数尽可能的小。

最长上升子序列 - 力扣官方题解

Python 
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        if not nums: return 0

        # from bisect import bisect_left

        # 手写二分查找
        def bisect_left(ls, x):
            l, r = 0, len(ls)
            while l < r:
                m = (l + r) // 2
                if ls[m] < x:  # 注意这里要 <，如果是 <= 就是 bisect_right 了，不满足题意
                    l = m + 1
                else:
                    r = m
            return l

        dp = [nums[0]]  # dp[i] 表示长度为 (i+1) 的 LIS 的最后一个元素的最小值
        for x in nums[1:]:
            if x > dp[-1]:
                dp.append(x)
            else:
                idx = bisect_left(dp, x)  # 不能使用 bisect/bisect_right
                # if dp[idx] > x:
                #     dp[idx] = x
                dp[idx] = x  # 因为 bisect_left 返回的定义就是 dp[idx] <= x，所以可以直接赋值

        return len(dp)

LeetCode 0958 二叉树的完全性检验 (中等, 2022-03)

二叉树 经典 LeetCode

问题简述 
给定一个二叉树的 root ，确定它是否是一个 完全二叉树 。

958. 二叉树的完全性检验 - 力扣（LeetCode）

思路1：利用完全二叉树定义
  • 判断完全二叉树的条件：
    • 左右子树都是满二叉树，且高度相同（满二叉树）；
    • 左右子树都是满二叉树，且左子树的高度+1；
    • 左子树是满二叉树，右子树是完全二叉树，且高度相同；
    • 左子树是完全二叉树，右子树是满二叉树，且左子树的高度+1；
  • 综上：
    • 我们需要存储信息有：高度、是否满二叉树、是否完全二叉树；
    • 对空节点，初始化为：0、是、是；
Python：后序遍历 
# 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 isCompleteTree(self, root: TreeNode) -> bool:

        from dataclasses import dataclass

        @dataclass
        class Info:
            height: int     # 树的高度
            is_full: bool   # 是否满二叉树
            is_cbt: bool    # 是否完全二叉树
        
        def dfs(x):
            if not x: return Info(0, True, True)

            l, r = dfs(x.left), dfs(x.right)

            # 利用左右子树的info 构建当前节点的info
            height = max(l.height, r.height) + 1
            is_full = l.is_full and r.is_full and l.height == r.height
            is_cbt = is_full \
                or l.is_full and r.is_full and l.height - 1 == r.height \
                or l.is_full and r.is_cbt and l.height == r.height \
                or l.is_cbt and r.is_full and l.height - 1 == r.height
            
            return Info(height, is_full, is_cbt)
        
        return dfs(root).is_cbt
思路2：利用完全二叉树的节点数性质
  • 给每个节点标号，如果是完全二叉树，存在以下性质：
    • 记根节点 id 为 1；
    • 若父节点的 id 为 i，则其左右子节点分别为 2*i 和 2*i + 1；
    • 如果是完全二叉树则有最大的 id == n，其中 n 为总节点数；
Python 写法1：DFS：前序+后序遍历 
class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:

        from dataclasses import dataclass

        @dataclass
        class Info:
            n: int        # 总节点数
            mx_id: int    # 最大 id
            is_cbt: bool  # 是否完全二叉树
        
        def dfs(x, i):
            if not x: return Info(0, float('-inf'), True)

            # 前序遍历向下传递 id
            l, r = dfs(x.left, i * 2), dfs(x.right, i * 2 + 1)

            # 后序遍历计算是否完全二叉树
            n = l.n + r.n + 1
            mx_id = max(i, l.mx_id, r.mx_id)
            is_cbt = n == mx_id  # and l.is_cbt and r.is_cbt
            return Info(n, mx_id, is_cbt)
        
        return dfs(root, 1).is_cbt
Python 写法2：BFS 
class Solution:
    def isCompleteTree(self, root: TreeNode) -> bool:
        # if not root: return True

        from collections import deque

        q = deque()
        q.append([root, 1])
        n = 1       # 记录节点数
        mx_id = 1   # 记录最大 id
        while q:
            node, id_ = q.popleft()
            if node.left:
                n += 1
                q.append([node.left, id_ * 2])
            if node.right:
                n += 1
                q.append([node.right, id_ * 2 + 1])
            mx_id = id_  # max(mx_id, id_)
        return n == mx_id

剑指Offer 0700 重建二叉树 (中等, 2021-11)

二叉树 分治 经典 剑指Offer

问题简述 
给出二叉树前序遍历和中序遍历的结果，重建该二叉树并返回其根节点。
详细描述 
输入某二叉树的前序遍历和中序遍历的结果，请构建该二叉树并返回其根节点。
假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

示例 1:
    Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
    Output: [3,9,20,null,null,15,7]
示例 2:
    Input: preorder = [-1], inorder = [-1]
    Output: [-1]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
  • 前序遍历，节点按照 [ 根节点 | 左子树 | 右子树 ] 的顺序输出。
  • 中序遍历，节点按照 [ 左子树 | 根节点 | 右子树 ] 的顺序输出。
  • 可知：
    • 前序遍历的首元素为根节点 node 的值。
    • 在中序遍历的结果中搜索根节点的索引 ，可将中序遍历划分为 [ 左子树 | 根节点 | 右子树 ] 。
    • 根据中序遍历中的左（右）子树的节点数量，可将前序遍历划分为 [ 根节点 | 左子树 | 右子树 ] 。
Python 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        if len(preorder) < 1 or len(inorder) < 1:  # 两个都判断一下
            return None

        # 建立根节点
        root_val = preorder[0]
        root = TreeNode(root_val)
        root_idx = inorder.index(root_val)  # 找到根节点在中序遍历的位置

        # 截取左子树的 preorder 和 inorder，递归建立左子树
        inorder_left = inorder[:root_idx]
        preorder_left = preorder[1: len(inorder_left) + 1]
        root.left = self.buildTree(preorder_left, inorder_left)
        # 截取右子树的 preorder 和 inorder，递归建立右子树
        inorder_right = inorder[root_idx + 1:]
        preorder_right = preorder[-len(inorder_right):]
        root.right = self.buildTree(preorder_right, inorder_right)
        return root
  • 更常见的写法会使用一个字典来保存每个节点在中序遍历中的位置，取代root_idx = inorder.index(root_val) 这一步，
  • 但是这样做就必须每次从最初的 preorder 和 inorder 中截取左右子树的片段，代码会变得比较复杂，传递的参数比较多，故没有采用这种写法；

剑指Offer 1600 数值的整数次方（快速幂） (中等, 2021-11)

递归 二分法 经典 剑指Offer

问题简述 
实现快速幂算法，即 pow(x, n)，不使用库函数；
详细描述 
实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。不得使用库函数，同时不需要考虑大数问题。

示例 1：
    输入：x = 2.00000, n = 10
    输出：1024.00000
示例 2：
    输入：x = 2.10000, n = 3
    输出：9.26100
示例 3：
    输入：x = 2.00000, n = -2
    输出：0.25000
    解释：2-2 = 1/22 = 1/4 = 0.25

提示：
    -100.0 < x < 100.0
    -2^31 <= n <= 2^31-1
    -10^4 <= x^n <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路

  • 直接连乘 n 次会报超时；

  • 从二分角度理解快速幂

    3^20      
= (3^2)^10       # 当指数为偶数时，对指数除2取整，底数平方
= (9^2)^5   
= (81^2)^2 * 81  # 当指数为奇数时，对指数除2取整，底数平方，同时再乘一个当前的底数（这里是 81）
= (6561^2)^1 * 81
= 43046721^0 * 81 * 43046721
= 1 * 81 * 43046721

    数值的整数次方（快速幂，清晰图解）

Python 
class Solution:
    def myPow(self, x: float, n: int) -> float:
        if x == 0: 
            return 0
        
        if n == 0:
            return 1

        if n < 0: 
            x = 1 / x
            n = -n

        ret = 1
        while n:
            if n & 1: 
                ret *= x
            x *= x
            n >>= 1
        return ret

剑指Offer 2400 反转链表 (简单, 2021-11)

链表 递归 迭代 经典 剑指Offer

问题简述 
输入一个链表的头节点，反转该链表。
详细描述 
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。

示例:
    输入: 1->2->3->4->5->NULL
    输出: 5->4->3->2->1->NULL

限制：
    0 <= 节点个数 <= 5000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
Python：递归（写法1） 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:

    def reverseList(self, head: ListNode) -> ListNode:
        if not head:  # 单独处理空链表
            return head
        
        self.ret = None

        def dfs(cur):
            # nonlocal ret  # 如果不使用 self.ret，而是 ret，就需要加上这句
            
            if cur.next is None:
                if self.ret is None:
                    self.ret = cur  # 尾节点，即新链表的头节点
                return cur
            
            nxt = dfs(cur.next)
            nxt.next = cur
            return cur
        
        
        head = dfs(head)
        head.next = None  # 断开最后一个节点，容易忽略的一步
        return self.ret
Python：递归（写法2） 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:

    def reverseList(self, head: ListNode) -> ListNode:

        def dfs(cur, pre):  # 当前节点，上一个节点
            if cur is None:  # 达到尾结点
                return pre  # 返回尾结点的上一个节点
            
            ret = dfs(cur.next, cur)
            cur.next = pre  # 把当前节点的 next 指向上一个节点
            return ret
        
        return dfs(head, None)
Python：迭代 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        cur, pre = head, None
        while cur:
            # 注意顺序
            nxt = cur.next # 暂存后继节点 cur.next
            cur.next = pre # 修改 next 引用指向
            pre = cur      # pre 暂存 cur
            cur = nxt      # cur 访问下一节点
        return pre

剑指Offer 2900 顺时针打印矩阵（3种思路4个写法） (中等, 2021-11)

数组 模拟 经典 剑指Offer

问题简述 
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。
详细描述 
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

示例 1：
    输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
    输出：[1,2,3,6,9,8,7,4,5]
示例 2：
    输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
    输出：[1,2,3,4,8,12,11,10,9,5,6,7]

限制：
    0 <= matrix.length <= 100
    0 <= matrix[i].length <= 100

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：螺旋遍历
  • 循环遍历 4 个方向的路线，中间做好边界判断（虽然思路简单，但是写起来很容易出错）；
Python：写法1（更朴素） 
class Solution:
    def spiralOrder(self, matrix: [[int]]) -> [int]:
        """"""        
        ret = []
        if not matrix or not matrix[0]:
            return ret

        m, n = len(matrix), len(matrix[0])  # m行n列
        # 设置左、右、上、下边界
        l, r, t, b, = 0, n - 1, 0, m - 1

        while True:
            # 依次遍历 4 个方向
            # 因为最后一趟遍历哪个方向都有可能，所以需要 4 个 break

            # left to right, top+=1
            for i in range(l, r + 1):
                ret.append(matrix[t][i])
            t += 1
            if t > b:
                break

            # top to bottom, right-=1
            for i in range(t, b + 1):
                ret.append(matrix[i][r])
            r -= 1
            if l > r:
                break

            # right to left, bottom-=1
            for i in range(r, l - 1, -1):  # 逆序
                ret.append(matrix[b][i])
            b -= 1
            if t > b:
                break

            # bottom to top, left+=1
            for i in range(b, t - 1, -1):  # 逆序
                ret.append(matrix[i][l])
            l += 1
            if l > r:
                break

        return ret
  • 写法 1 的逻辑足够清晰，但不够通用（优雅），比如要遍历 8 个方向时；
  • 另一种写法会预先定义各方向的 step，详见代码；
Python：写法2（更优雅） 
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix or not matrix[0]:
            return []

        # 4 个方向的 step
        steps = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        m, n = len(matrix), len(matrix[0])

        # 法1）使用一个 set 或矩阵记录已经访问过的位置
        # visited = set()
        # visited = [[False] * n for _ in range(m)]  # m行n列
        # 法2）直接在 matrix 上修改访问过的位置
        visited = 10001

        ret = []
        i, j = 0, 0  # 记录当前访问的位置
        k = 0  # 已经访问过的位置数量
        d = 0  # 方向标记
        while k < m * n:
            ret.append(matrix[i][j])
            matrix[i][j] = visited
            # visited.add((i, j))
            # visited[i][j] = True
            k += 1

            # 下一个位置
            nxt_i, nxt_j = i + steps[d][0], j + steps[d][1]
            # 判断下一个位置是否合法，或是否访问过
            if not 0 <= nxt_i < m or not 0 <= nxt_j < n or matrix[nxt_i][nxt_j] == visited:
                # 如果不合法或已经访问过，进入下一个方向
                d = (d + 1) % 4
                nxt_i, nxt_j = i + steps[d][0], j + steps[d][1]
            i, j = nxt_i, nxt_j

        return ret
思路2：层层递归
  • 每次遍历完最外圈后，递归遍历下一圈；
Python 
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        """"""
        def dfs(M):
            # 注意：这里除了要判断 M，还要判断 M[0]，因为之后代码中的切片操作可能会使行数据为空列表 []
            if not M or not M[0]: return []

            m, n = len(M), len(M[0])

            # 如果最内圈是一行或一列，那么该行/列的遍历方向一定是 左→右 或 上→下
            if m == 1:
                return M[0]
            if n == 1:
                return [row[0] for row in M]

            # 最外一圈的数据
            ret = M[0] \
                + [row[-1] for row in M[1:]] \
                + M[-1][-2::-1] \
                + [row[0] for row in M[-2:0:-1]]

            return ret + dfs([row[1:-1] for row in M[1:-1]])

        return dfs(matrix)
思路3：“削苹果”
  • 每次“削去”矩阵的第一层，然后将矩阵逆时针旋转 90 度，循环削去第一层；
  • 而逆时针旋转的操作在 python 中可以用一行代码完成！
Python 
class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ret = []
        while matrix:
            ret += list(matrix.pop(0))  # zip 后的结果是一个元组，这里转成 list，不过实际上不转换也可以；

            # 核心操作，逆时针旋转 90 度
            matrix = list(zip(*matrix))[::-1]
        
        return ret
# 图解 `list(zip(*matrix))[::-1]` 这一步做了什么：

# 假设已经 pop 了第一行，此时矩阵剩余的部分是：
[4 5 6]  # 记为 l1
[7 8 9]  # 记为 l2，如果有 n 行，则记为 ln

# zip(*matrix) 包含了两个知识点：一个是 zip() 函数，一个是 * 号的作用；
# zip(*matrix) 实际上等价于 zip(l1, l2, ..., ln)
# 经过这一步 matrix 将转化为（相当于做了一次转置）
[4 7]
[5 8]
[6 9]

# 这时再将 matrix 做一次逆序，就得到了逆时针旋转 90 度的结果
[6 9]
[5 8]
[4 7]

剑指Offer 3100 栈的压入、弹出序列 (中等, 2021-11)

栈 数组 经典 剑指Offer

问题简述 
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。
假设压入栈的所有数字均不相等。
详细描述 
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。

示例 1：
    输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
    输出：true
    解释：我们可以按以下顺序执行：
    push(1), push(2), push(3), push(4), pop() -> 4,
    push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
    输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
    输出：false
    解释：1 不能在 2 之前弹出。

提示：
    0 <= pushed.length == popped.length <= 1000
    0 <= pushed[i], popped[i] < 1000
    pushed 是 popped 的排列。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zhan-de-ya-ru-dan-chu-xu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
  • 设置一个模拟栈 s，将 pushed 中的元素顺序入栈；
  • 期间，如果 popped 中的元素与 s 栈顶元素相同，则弹出栈顶元素，直到不再相同或 s 为空；
  • 当结束循环时，如果 s 不为空，则返回 False，反之 True；
Python 
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:

        s = []  # 模拟栈

        # pop(0) 的操作很浪费时间，其实是不需要修改 pushed 和 popped 的，详见优化后的代码
        while pushed:
            s.append(pushed.pop(0))

            while s and s[-1] == popped[0]:
                s.pop()
                popped.pop(0)
        
        return True if not popped else False
Python：优化后 
class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:

        s = []  # 模拟栈

        idx = 0  # popped 索引
        for x in pushed:
            s.append(x)

            while s and s[-1] == popped[idx]:
                s.pop()
                idx += 1
        
        return True if not s else False

剑指Offer 3500 复杂链表的复制（深拷贝） (中等, 2021-12)

链表 哈希表 经典 剑指Offer

问题简述 
复制带随机指针的链表，返回复制后链表的头结点；
详细描述

注意：本题的输入输出带有迷惑性，它们并不是实际的输入和输出，而是链表的数组展现；

给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 深拷贝。深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

返回复制链表的头节点。

用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

val：一个表示 Node.val 的整数。
random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为  null 。
你的代码 只 接受原链表的头节点 head 作为传入参数。

示例 1：
    输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]
示例 2：
    输入：head = [[1,1],[2,1]]
    输出：[[1,1],[2,1]]
示例 3：
    输入：head = [[3,null],[3,0],[3,null]]
    输出：[[3,null],[3,0],[3,null]]
示例 4：
    输入：head = []
    输出：[]
    解释：给定的链表为空（空指针），因此返回 null。

提示：
    -10000 <= Node.val <= 10000
    Node.random 为空（null）或指向链表中的节点。
    节点数目不超过 1000 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fu-za-lian-biao-de-fu-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：哈希表

  • 先看下普通链表的复制：

    普通链表的复制 
        class Solution:
        def copyList(self, head: 'Node') -> 'Node':
            cur = head
            ret = pre = Node(0)  # 伪头结点
            while cur:
                node = Node(cur.val) # 复制节点 cur
                pre.next = node      # 新链表的 前驱节点 -> 当前节点
                # pre.random = '???' # 新链表的 「 前驱节点 -> 当前节点 」 无法确定
                cur = cur.next       # 遍历下一节点
                pre = node           # 保存当前新节点
            return ret.next

  • 首先要理解本题的难点：

    • 复制当前节点的时候，随机指针指向的节点可能还没有创建；
    • 即使你先按普通链表先把节点都创建出来，由于链表无法随机访问的性质，你也不知道随机节点在哪个位置；

  • 解决方法是利用哈希表（写法1）：

    • 第一次遍历时，记录每个节点对应的复制节点；
    • 第二次遍历时，根据原链表的指向从哈希表中提取对应的节点，建立指向关系；

  • 本题还有一种递归的写法（写法2）：

    • 同样用一个哈希表保存
Python：迭代（写法1） 
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None  # 使用伪头结点，可以省去这行

        dp = dict()

        # 第一次遍历，生成复制节点，并记录到哈希表
        p = head
        while p:
            dp[p] = Node(p.val)
            p = p.next
        
        # 写法1：使用伪头结点，可以省去对 head 为 None 的判断
        cur = head
        ret = pre = Node(0)  # 伪头结点
        while cur:
            pre.next = dp[cur]  # 这里可以不用 get，因为一定存在
            pre.next.random = dp.get(cur.random)  # get 方法在 key 不存在时，默认返回 None
            cur = cur.next
            pre = pre.next

        return ret.next

        # 写法2：相比使用伪头结点
        # cur = head
        # while cur:
        #     dp[cur].next = dp.get(cur.next)
        #     dp[cur].random = dp.get(cur.random)
        #     cur = cur.next
        
        # return dp[head]
Python：递归（写法2）
  • 【不推荐】虽然代码量会少一点，但是不好理解；
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None

        dp = dict()
        
        def dfs(p):
            if not p: return None

            if p not in dp:
                dp[p] = Node(p.val)
                dp[p].next = dfs(p.next)
                dp[p].random = dfs(p.random)
        
            return dp[p]
        
        return dfs(head)
思路2：复制+拆分

详见：复杂链表的复制（哈希表 / 拼接与拆分，清晰图解）

  • 注意这个方法需要遍历三次：
    • 第一次复制节点
    • 第二次设置随机节点
    • 第三次拆分
  • 因为随机节点指向任意，所以必须先设置完所有随机节点后才能拆分；
Python 
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head: return None

        # 复制节点
        cur = head
        while cur:
            nod = Node(cur.val)  # 创建节点
            cur.next, nod.next = nod, cur.next  # 接入新节点
            cur = nod.next  # 遍历下一个节点

        # 设置随机节点，因为随机节点指向任意，所以必须先设置随机节点后才能断开
        cur = head
        while cur:
            if cur.random:
                cur.next.random = cur.random.next
            cur = cur.next.next

        # 拆分节点
        cur = head
        ret = nxt = head.next
        while nxt.next:
            # 开始拆分
            cur.next = cur.next.next
            nxt.next = nxt.next.next

            # 下一组
            cur = cur.next
            nxt = nxt.next
        
        return ret

剑指Offer 3600 二叉搜索树与双向链表 (中等, 2021-12)

二叉树 递归 经典 剑指Offer

问题简述 
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。
详细描述 
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

为了让您更好地理解问题，以下面的二叉搜索树为例：

     4
    / \
   2   5
  / \
 1   3

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。

 head -> 1 <-> 2 <-> 3 <-> 4 <-> 5 (1 和 5 也互连)
         ↑-----------------------↑

特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
  • 根据二叉搜索树的性质，其中序遍历结果就是一个有序的单向链表；
  • 因此本题要做的就是在中序遍历的过程中，修改指针的指向，得到双向链表；
  • 考虑使用中序遍历访问树的各节点，记 cur，初始化前驱节点 pre=None；
    1. 在访问每个节点时构建 cur 和前驱节点 pre 的引用指向；
    2. 当 pre=None 时，说明该节点是最左叶子节点（中序遍历访问的第一个节点），即头结点 ret；否则修改双向节点引用，即 pre.right = cur， cur.left = pre；
    3. 在访问右子树前，将 pre 指向 cur；
    4. 中序遍历完成后，最后构建头节点和尾节点的引用指向。
Python 
"""
# Definition for a Node.
class Node:
    def __init__(self, val, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
"""
class Solution:
    def treeToDoublyList(self, root: 'Node') -> 'Node':
        if not root: return None

        self.ret = self.pre = None

        def dfs(cur):
            if not cur:
                return

            dfs(cur.left)
            if self.pre:
                self.pre.right = cur
                cur.left = self.pre
            else:  # 达到最左叶子节点（只执行一次）
                self.ret = cur  # 双向链表的头结点
            
            self.pre = cur  # 在遍历右子树前，将 pre 指向 cur
            dfs(cur.right)

        dfs(root)
        # 遍历结束时，pre 指向最右叶子节点
        self.ret.left = self.pre 
        self.pre.right = self.ret
        return self.ret

剑指Offer 3800 字符串的排列（全排列） (中等, 2021-12)

DFS+剪枝 经典 剑指Offer

问题简述 
输入一个字符串，打印出该字符串中字符的所有排列。
详细描述 
输入一个字符串，打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。

示例:
    输入：s = "abc"
    输出：["abc","acb","bac","bca","cab","cba"]

限制：
    1 <= s 的长度 <= 8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：DFS树状遍历+剪枝

  • 深度优先求全排列的过程实际上相当于是一个多叉树的先序遍历过程；

    • 假设共有 n 种状态都不重复，则：
    • 第一层有 n 种选择；
    • 第二层有 n - 1 种选择；
    • ...
    • 共有 n! 种可能；
    图示

本题的难点是如何过滤重复的状态

  • 写法1） 遍历所有状态，直接用 set 保存结果（不剪枝）：

    Python 
    class Solution:
    def permutation(self, s: str) -> List[str]:

        N = len(s)
        buf = []
        ret = set()
        visited = [False] * N
        def dfs(deep):
            if deep == N:
                ret.add(''.join(buf))
                return

            for i in range(N):
                if not visited[i]:
                    # 标记
                    buf.append(s[i])
                    visited[i] = True
                    # 进入下一层
                    dfs(deep + 1)
                    # 回溯（撤销标记）
                    buf.pop()  
                    visited[i] = False
        
        dfs(0)
        return list(ret)

  • 写法2） 跳过重复字符（需排序）：

    Python 
    class Solution:
    def permutation(self, s: str) -> List[str]:

        s = sorted(s)  # 排序，使相同字符在一起
        N = len(s)
        ret = []  # 保存结果
        buf = []  # 临时结果
        visited = [False] * N  # 记录是否访问
        def dfs(deep):  # 传入递归深度
            if deep == N:
                ret.append(''.join(buf))
                return

            for i in range(N):
                # 剪枝
                if visited[i - 1] is False and i > 0 and s[i] == s[i - 1]:
                    continue

                # 下面的代码居然可以（区别仅在于 visited[i - 1] 的状态），
                # 但是效率不如上面的，具体解析可参考：[「代码随想录」剑指 Offer 38. 字符串的排列](https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/dai-ma-sui-xiang-lu-jian-zhi-offer-38-zi-gwt6/)
                # if visited[i - 1] is True and i > 0 and s[i] == s[i - 1]:
                #     continue

                if not visited[i]:  # 如果当前位置还没访问过
                    # 标记当前位置
                    visited[i] = True
                    buf.append(s[i])
                    # 下一个位置
                    dfs(deep + 1)
                    # 回溯
                    buf.pop()
                    visited[i] = False

        dfs(0)
        return ret

  • 写法3） 在每一层用一个 set 保存已经用过的字符（不排序）：

    Python 
    class Solution:
    def permutation(self, s: str) -> List[str]:

        N = len(s)
        buf = []
        ret = set()
        visited = [False] * N
        def dfs(deep):
            if deep == N:
                ret.add(''.join(buf))
                return

            used = set()  # 记录用过的字符
            for i in range(N):
                if s[i] in used:  # 如果是已经用过的
                    continue

                if not visited[i]:
                    # 标记
                    used.add(s[i])
                    buf.append(s[i])
                    visited[i] = True
                    # 进入下一层
                    dfs(deep + 1)
                    # 回溯（撤销标记）
                    buf.pop()  
                    visited[i] = False
        
        dfs(0)
        return list(ret)

  • 写法2） 原地交换

    剑指 Offer 38. 字符串的排列（回溯法，清晰图解）

    • 这个写法有点像“下一个排列”，只是没有使用字典序；
    Python 
    class Solution:
    def permutation(self, s: str) -> List[str]:
        N = len(s)
        buf = list(s)
        ret = []

        def dfs(deep):
            if deep == N - 1:
                ret.append(''.join(buf))   # 添加排列方案
                return

            used = set()
            for i in range(deep, N):  # 注意遍历范围，类似选择排序
                if buf[i] in used:  # 已经用过的状态
                    continue

                used.add(buf[i])
                buf[deep], buf[i] = buf[i], buf[deep]  # 交换，将 buf[i] 固定在第 deep 位
                dfs(deep + 1)               # 开启固定第 x + 1 位字符
                buf[deep], buf[i] = buf[i], buf[deep]  # 恢复交换

        dfs(0)
        return ret
思路2：下一个排列

字符串的排列

  • 先排序得到最小的字典序结果；
  • 循环直到不存在下一个更大的排列；
Python 
class Solution:
    def permutation(self, s: str) -> List[str]:
        
        def nextPermutation(nums: List[str]) -> bool:
            i = len(nums) - 2
            while i >= 0 and nums[i] >= nums[i + 1]:
                i -= 1

            if i < 0:
                return False
            else:
                j = len(nums) - 1
                while j >= 0 and nums[i] >= nums[j]:
                    j -= 1
                nums[i], nums[j] = nums[j], nums[i]

            left, right = i + 1, len(nums) - 1
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

            return True

        buf = sorted(s)
        ret = [''.join(buf)]
        while nextPermutation(buf):
            ret.append(''.join(buf))

        return ret

剑指Offer 3900 数组中出现次数超过一半的数字（摩尔投票） (简单, 2021-12)

排序 模拟 分治 经典 剑指Offer

问题简述 
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
详细描述 
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1:
    输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
    输出: 2
限制：
    1 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：排序
  • 排序后，数组中间位置的数一定满足题意；
  • 时间复杂度 O(NlogN)；
Python 
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        return sorted(nums)[len(nums) // 2]
思路2：计数
  • 一次遍历，记录每个数出现的次数；
  • 空间复杂度 O(N)；
Python 
class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        from collections import defaultdict

        cnt = defaultdict(int)

        for x in nums:
            cnt[x] += 1
            if cnt[x] > len(nums) // 2:
                return x
        
        # return -1
思路3：“摩尔投票法”

数组中出现次数超过一半的数字（摩尔投票法，清晰图解）

  • “摩尔投票法”的核心思想是一一抵消；
  • 假设已知目标数为 x，遍历时若出现一次 x 记 +1 票，否则为 -1 票；
    • 推论1：最终票数和必大于 0；
    • 推论2：若前 n 个数的票数和为 0，那么剩余部分依然满足推论1，即目标数字依然为 x；
Python 
class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        cnt = 0
        for x in nums:
            if cnt == 0:  # 当票数和为 0 时，假设当前值为目标值
                ret = x   # 如果这个数不是目标值，那么它迟早会因为不断 -1，被替换掉
                
            if x == ret:
                cnt += 1
            else:
                cnt -= 1
        
        return ret
思路4：分治

数组中出现次数超过一半的数字

  • 本题使用分治在时间和空间上都不是最优，仅用于理解分治的思想；
Python 
class Solution:
    def majorityElement(self, nums: List[int]) -> int:

        def recur(lo, hi):  # [lo, hi] 闭区间
            if lo == hi:  # 当数组中只有一个元素时，这个数就是目标值
                return nums[lo]

            # 分治
            mid = (hi - lo) // 2 + lo
            l = recur(lo, mid)
            r = recur(mid + 1, hi)

            # 如果左右返回值相同时，显然这个值就是目标值
            if l == r:
                return l

            # 否则需要判断哪个出现的次数更多
            lc = sum(1 for i in range(lo, hi + 1) if nums[i] == l)
            rc = sum(1 for i in range(lo, hi + 1) if nums[i] == r)
            return l if lc > rc else r

        return recur(0, len(nums) - 1)

剑指Offer 4000 最小的k个数（partition操作） (简单, 2021-12)

优先队列 快排 经典 剑指Offer

问题简述 
输入整数数组 arr ，找出其中最小的 k 个数

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）

详细描述 
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

示例 1：
    输入：arr = [3,2,1], k = 2
    输出：[1,2] 或者 [2,1]
示例 2：
    输入：arr = [0,1,2,1], k = 1
    输出：[0]
 
限制：
    0 <= k <= arr.length <= 10000
    0 <= arr[i] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：快排中的 partition 过程
  • 快排的过程：
    • partition 过程：以数组某个元素（一般取首元素）为基准数，将所有小于基准数的元素移动至其左边，大于基准数的元素移动至其右边。
    • 递归地对左右部分执行 partition 过程，直至区域内的元素数量为 1；
  • 基于以上思想，当某次划分后基准数正好是第 k+1 小的数字，那么此时基准数左边的所有数字便是题目要求的最小的 k 个数。
Python 
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:

        def partition(lo, hi):  # [lo, hi]
            if lo >= hi: return

            p = arr[lo]  # 选取第一个位置为基准点
            l, r = lo, hi  # l 的初始位置应该在 lo，而不是 lo + 1
            # 假设初始化为 lo + 1，当 a[lo] 为最小值时，此时训处循环后 l == r == lo + 1，再交换 a[lo] 和 a[l] 就会出错

            while l < r:  # 退出循环时 l == r
                # 先移动 r，在移动 l，此时退出循环后 l 和 r 同时指向一个小于 p 的值；反之，如果用 a[hi] 初始化 p，就要先移动 l，在移动 r；

                # 从 r 开始，从右往左找到第一个 < p 的值，所以循环条件是 >=
                while l < r and arr[r] >= p: r -= 1
                # 从 l 开始，从左往右找到第一个 > p 的值，所以循环条件是 <=
                while l < r and arr[l] <= p: l += 1
                arr[l], arr[r] = arr[r], arr[l]
                
            arr[lo], arr[l] = arr[l], arr[lo]  # 将基准点移动到分界点

            if l < k: partition(l + 1, hi)
            if l > k: partition(lo, l - 1)

        partition(0, len(arr) - 1)
        return arr[:k]
思路2：堆（优先队列）
  • 写法1） 维护一个长度为 k 的大顶堆（第一个数最大），当下一个元素小于堆顶值，就更新堆（弹出堆顶，插入新值）；
  • 写法2） 直接对整个数组构建一个小顶堆，然后循环弹出前 k 个值；
  • 注意写法1 的时间复杂度是 O(NlogK)，而写法2 是 O(NlogN)；
Python：写法1（使用库函数） 
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k < 1 or not arr:  # 使用堆，要添加非空断言
            return []

        import heapq

        # python 默认是小顶堆，且不支持自定义比较函数，所以要添加负号转成取前 k 大的数
        ret = [-x for x in arr[:k]]
        heapq.heapify(ret)

        for i in range(k, len(arr)):
            if -arr[i] > ret[0]:
                heapq.heappop(ret)
                heapq.heappush(ret, -arr[i])

        return [-x for x in ret]
Python：写法2（使用库函数） 
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k < 1 or not arr:  # 使用堆，要添加非空断言
            return []

        import heapq

        # python 默认是小顶堆
        heapq.heapify(arr)

        ret = []
        for _ in range(k):
            ret.append(heapq.heappop(arr))

        return ret
思路3：计数排序
  • 因为题目限制了 arr[i] 的范围，所以还可以使用计数排序，时间复杂度 O(N)；
Python 
class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        if k >= len(arr):  # 使用计数排序要加长度判断
            return arr

        dp = [0] * 10001

        for x in arr:
            dp[x] += 1
        
        ret = []
        cnt = 0
        for i in range(len(dp)):
            while dp[i] and cnt < k:
                ret.append(i)
                cnt += 1
                dp[i] -= 1
            if cnt == k:
                return ret

剑指Offer 4900 丑数 (中等, 2021-12)

动态规划 经典 剑指Offer

问题简述 
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。
求按从小到大的顺序的第 n 个丑数。
详细描述 
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:
    输入: n = 10
    输出: 12
    解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
    1 是丑数。
    n 不超过1690。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：暴力解
  • 根据丑数的定义，有如下推论：
    • 一个丑数乘以 2、3、5 之后，还是丑数；
    • 从 1 开始，对每个丑数都乘以 2、3、5，再加入丑数序列（移除重复），那么不会产生遗漏；
  • 对已有的丑数乘以 2、3、5，取其中大于已知最大丑数的最小值；
Python 
class Solution:
    def nthUglyNumber(self, n: int) -> int:

        dp = [1]
        for i in range(1, n):
            M = dp[-1]  # 当前最大丑数

            tmp = []
            for x in dp[::-1]:  # 逆序遍历
                if x * 5 < M:
                    break
                    
                if x * 2 > M:
                    tmp.append(x * 2)
                if x * 3 > M:
                    tmp.append(x * 3)
                if x * 5 > M:
                    tmp.append(x * 5)

            dp.append(min(tmp))

        return dp[-1]
思路：动态规划
  • 暴力解中存在大量重复计算，可以考虑动态规划；
Python 
class Solution:
    def nthUglyNumber(self, n: int) -> int:

        dp = [1] * n
        p1, p2, p3 = 0, 0, 0  # 三指针归并

        for i in range(1, n):
            n2, n3, n5 = dp[p1] * 2, dp[p2] * 3, dp[p3] * 5
            dp[i] = min(n2, n3, n5)

            # 去重：使用 if 而不是 elif
            if dp[i] == n2:
                p1 += 1
            if dp[i] == n3:
                p2 += 1
            if dp[i] == n5:
                p3 += 1

        return dp[-1]

剑指Offer 5100 数组中的逆序对 (困难, 2022-01)

分治 树状数组 经典 剑指Offer

问题简述 
在数组中的两个数字，如果前一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组，求该数组中的逆序对的总数。
详细描述 
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:
    输入: [7,5,6,4]
    输出: 5

限制：
    0 <= 数组长度 <= 50000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：利用归并排序

  • 归并排序

    数组中的逆序对（归并排序，清晰图解）

  • 在合并过程中统计逆序对的数量

    • 归并排序的合并过程：依次比较两个子数组的首元素，将其中较小的放置到一个新的数组中；
    • 每当遇到左子数组当前元素 > 右子数组当前元素时，意味着「左子数组当前元素 至 末尾元素」与「右子数组当前元素」构成了若干「逆序对」

  • 归并排序需要用到辅助数组，因此其空间复杂度为 O(N)；

    • 辅助数组一般有两种用法，分别见写法1 和 写法2；
Python：写法1 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        
        # 临时数组 for 归并排序：空间复杂度 O(N)
        tmp = [0] * len(nums)

        def merge(lo, hi):  # 闭区间 [lo, hi]
            if lo >= hi: return 0

            m = (lo + hi) // 2
            ret = merge(lo, m) + merge(m + 1, hi)  # 分治

            # 辅助数组
            tmp[lo: hi + 1] = nums[lo: hi + 1]  # 先复制，再赋值

            l, r = lo, m + 1  # 左右指针
            for i in range(lo, hi + 1):
                # 必须先判断是否越界
                if l == m + 1:  # 左子数组遍历完毕
                    nums[i] = tmp[r]
                    r += 1
                elif r == hi + 1 or tmp[l] <= tmp[r]:  # 右子数组遍历完毕，或 tmp[l] <= tmp[r] 时，即左指针位置小于右指针位置
                    nums[i] = tmp[l]
                    l += 1
                else:  # tmp[l] > tmp[r] 时
                    nums[i] = tmp[r]
                    r += 1
                    ret += m - l + 1  # 累计逆序对数

            return ret

        return merge(0, len(nums) - 1)
Python：写法2 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        
        # 临时数组 for 归并排序：空间复杂度 O(N)
        tmp = [0] * len(nums)

        def merge(lo, hi):  # 闭区间 [lo, hi]
            if lo >= hi: return 0

            m = (lo + hi) // 2
            ret = merge(lo, m) + merge(m + 1, hi)  # 分治

            l, r = lo, m + 1  # 左右指针
            for i in range(lo, hi + 1):
                # 必须先判断是否越界
                if l == m + 1:  # 左子数组遍历完毕
                    tmp[i] = nums[r]
                    r += 1
                elif r == hi + 1 or nums[l] <= nums[r]:  # 右子数组遍历完毕，或 nums[l] <= nums[r]
                    tmp[i] = nums[l]
                    l += 1
                else:  # nums[l] > nums[r]
                    tmp[i] = nums[r]
                    r += 1
                    ret += m - l + 1  # 累计逆序对数

            # 辅助数组
            nums[lo: hi + 1] = tmp[lo: hi + 1]  # 先赋值，再覆盖
            return ret

        return merge(0, len(nums) - 1)
思路2：树状数组

数组中的逆序对

Python 
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)

    @staticmethod
    def lowbit(x):
        return x & (-x)
    
    def query(self, x):
        ret = 0
        while x > 0:
            ret += self.tree[x]
            x -= BIT.lowbit(x)
        return ret

    def update(self, x):
        while x <= self.n:
            self.tree[x] += 1
            x += BIT.lowbit(x)

class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        n = len(nums)

        # 离散化
        tmp = sorted(nums)
        for i in range(n):
            nums[i] = bisect.bisect_left(tmp, nums[i]) + 1

        # 树状数组统计逆序对
        bit = BIT(n)
        ans = 0
        for i in range(n - 1, -1, -1):
            ans += bit.query(nums[i] - 1)
            bit.update(nums[i])
        return ans
更快的代码
Python：快排？ 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        if len(nums) <= 1: return 0

        more, less = [], []
        count = 0
        center_count = 0
        center = random.choice(nums)
        for i in nums:
            if i > center:
                more.append(i)
            elif i == center:
                center_count += 1
                count += len(more)
            else:
                count += center_count
                count += len(more)
                less.append(i)
        count += self.reversePairs(more) + self.reversePairs(less)
        return count
Python：二分？ 
class Solution:
    def reversePairs(self, nums: List[int]) -> int:
        tmp = []
        ret = 0
        for num in nums[::-1]:
            cur = bisect_left(tmp, num)
            ret += cur

            tmp[cur:cur] = [num]  # 用这句是 732ms
            # tmp.insert(cur, num)  # 用这句是 1624ms

        return ret

剑指Offer 6200 圆圈中最后剩下的数字（约瑟夫环问题） (中等, 2022-01)

模拟 递推 经典 剑指Offer

问题简述 
0 ~ n-1 这 n 个数字围成一个圆圈，从数字0开始，每次从这个圆圈里删除第 m 个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
详细描述 
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

示例 1：
    输入: n = 5, m = 3
    输出: 3
示例 2：
    输入: n = 10, m = 17
    输出: 2

限制：
    1 <= n <= 10^5
    1 <= m <= 10^6

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：暴力解（超时）
Python 
class Solution:
    def lastRemaining(self, n: int, m: int) -> int:

        nums = list(range(n))
        idx = 0
        while len(nums) > 1:
            idx = (idx + m - 1) % len(nums)
            nums.pop(idx)
        
        return nums[0]
思路2：递推
  • 虽然我们不知道这个最终的值是哪个，但是可以确定的是在最后一轮删除后，这个值在数组中的索引一定是 0（此时数组中只有一个值了）；
  • 递推的目的就是每次还原这个值在上一轮所在的索引，直到第一轮，然后就可以根据索引从数组中找到这个值了；
  • 记 f(i) 表示倒数第 i 轮时目标值所在的索引（i>=1），显然有 f(1) = 0；
  • 递推公式：f(i) = (f(i-1) + m) % i（倒数第 i 轮，数组的长度也为 i，所以是对 i 取余）
    • (f(i-1) + m) % i
  • 关于递推公式的具体解析可以参`考「换个角度举例解决约瑟夫环」
Python 
class Solution:
    def lastRemaining(self, n: int, m: int) -> int:

        # nums = list(range(n))  # 因为 nums = [0..n-1]

        idx = 0  # 因为最后一轮数组中只有一个值了，所以此时目标的索引一定是 0
        for i in range(2, n + 1):
            idx = (idx + m) % i  # 倒数第 i 轮时目标的索引
        
        # return nums[idx]
        return idx  # 因为 nums = [0..n-1]，所以 nums[idx] == idx

剑指Offer 6700 把字符串转换成整数（atoi） (中等, 2022-01)

字符串 模拟 经典 剑指Offer

问题简述 
写一个函数 strToInt(string s)，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。
详细描述 
写一个函数 strToInt(string s)，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：
    假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231,  231 − 1]。如果数值超过这个范围，请返回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例 1:
    输入: "42"
    输出: 42
示例 2:
    输入: "   -42"
    输出: -42
    解释: 第一个非空白字符为 '-', 它是一个负号。
         我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3:
    输入: "4193 with words"
    输出: 4193
    解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4:
    输入: "words and 987"
    输出: 0
    解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
        因此无法执行有效的转换。
示例 5:
    输入: "-91283472332"
    输出: -2147483648
    解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
         因此返回 INT_MIN (−231) 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路
  • 把字符串当做数组，依次遍历每个字符，根据题目要求执行每一步操作；
  • 注意一些细节：如正负号、char 与 int 的互转、越界判断等，详见下方代码；
  • PS：不同编程语言中字符串的实现细节；
C++ 
class Solution {
public:
    int strToInt(string str) {
        int n = str.length();
        if (n < 1) return 0;
        
        int ret = 0;
        int p = 0;      // 模拟指针
        int sign = 1;   // 正负
        int s_max = INT_MAX / 10;
        
        while (isspace(str[p])) 
            p++;  // 跳过前置空格

        // c++ 的字符串末尾有一个特殊字符，因此不需要做越界判断
        // if (p == n) return 0;
        
        if (str[p] == '-') sign = -1;
        if (str[p] == '-' || str[p] == '+') p++;
        
        while (str[p] >= '0' && str[p] <= '9') {
            if (ret > s_max || (ret == s_max && str[p] > '7')) {  // 越界判断
                return sign > 0 ? INT_MAX : INT_MIN;
            }
            ret = ret * 10 + (str[p] - '0');  // str[p] - '0' 必须括起来，否则顺序计算时会溢出
            p++;
        }
        
        return sign * ret;
    }
};
Python 
class Solution:
    def strToInt(self, str: str) -> int:

        n = len(str)
        if n < 1: return 0

        INT_MAX = 2 ** 31 - 1
        INT_MIN = -2 ** 31

        ret = 0  # 保存结果
        sign = 1  # 记录符号
        p = 0  # 模拟指针

        # Python 字符串与 C++ 不同，时刻需要进行越界判断
        while p < n and str[p] == ' ':
            p += 1
        
        if p == n:  # 越界判断
            return ret
        
        if str[p] == '-':
            sign = -1
        if str[p] in ('-', '+'):
            p += 1
        
        while p < n and '0' <= str[p] <= '9':  # 注意越界判断
            ret = ret * 10 + int(str[p])
            p += 1
            if ret > INT_MAX:  # python 中不存在越界，因此直接跟 INT_MAX 比较即可
                return INT_MAX if sign == 1 else INT_MIN
        
        return ret * sign
Java

把字符串转换成整数（数字越界处理，清晰图解）

class Solution {
    public int strToInt(String str) {
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 0, sign = 1, length = str.length();
        if(length == 0) return 0;
        while(str.charAt(i) == ' ')
            if(++i == length) return 0;
        if(str.charAt(i) == '-') sign = -1;
        if(str.charAt(i) == '-' || str.charAt(i) == '+') i++;
        for(int j = i; j < length; j++) {
            if(str.charAt(j) < '0' || str.charAt(j) > '9') break;
            if(res > bndry || res == bndry && str.charAt(j) > '7')
                return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + (str.charAt(j) - '0');
        }
        return sign * res;
    }
}

剑指Offer 6801 二叉搜索树的最近公共祖先 (简单, 2022-01)

二叉搜索树 经典 剑指Offer

问题简述

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

如果是普通二叉树呢？
详细描述 
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树

            6
          /   \
         2     8
        / \   / \
       0   4 7   9
          / \
         3   5

示例 1:
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
    输出: 6 
    解释: 节点 2 和节点 8 的最近公共祖先是 6。
示例 2:
    输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
    输出: 2
    解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:
    所有节点的值都是唯一的。
    p、q 为不同节点且均存在于给定的二叉搜索树中。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：基于二叉搜索树
  • 根据二叉搜索树的性质：左子树都小于父节点，右子树都大于父节点，快速找出指定节点的父节点路径；
  • 然后找出最近的公共祖先；
Python 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        def foo(node, p):
            ret = []
            while p and p.val != node.val:
                ret.append(p)
                if p.val > node.val:
                    p = p.left
                else:
                    p = p.right
            ret.append(p)
            return ret
        
        P = foo(p, root)
        Q = foo(q, root)

        ret = None
        for l, r in zip(P, Q):
            if l.val == r.val:
                ret = l
            else:
                break
        
        return ret

优化1：根据二叉搜索树的定义，如果一个节点 node 是 p 和 q 的祖先，则有 node 同时 >= 或 <= p 和 q；因此可以优化为一次遍历；

Python 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':

        node = root
        while node:
            if node.val > p.val and node.val > q.val:
                node = node.left
            elif node.val < p.val and node.val < q.val:
                node = node.right
            else:
                break
        
        return node

优化2：若可保证 p.val < q.val，则在循环中可减少判断条件。

二叉搜索树的最近公共祖先（迭代 / 递归，清晰图解）

Python 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        if q.val > p.val: 
            p, q = q, p

        node = root
        while node:
            if node.val > p.val:
                node = node.left
            elif node.val < q.val:
                node = node.right
            else:
                break
        
        return node
思路2：普通二叉树

剑指 Offer 68 - II. 二叉树的最近公共祖先 - 力扣（LeetCode）

  • 思路1 利用了二叉搜索树的性质快速获取祖先路径；
  • 可以不利用二叉搜索树的性质来获取祖先路径（对非二叉搜索树也适用）；
  • 因为必须先找到目标节点才能确定路线，所以可以考虑后序遍历；当找到目标节点时，返回 flag，指示上级节点是否为祖先节点；
Python 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:

        # 后序遍历搜索历史祖先，因为是后序遍历，所以 trace 是倒序的
        def dfs(node, target, trace):
            if node is None:
                return False
            if node.val == target.val:
                trace.append(node)  # 根据定义，自己也是自己的祖先节点
                return True
            
            if dfs(node.left, target, trace) or dfs(node.right, target, trace):
                trace.append(node)
                return True
            else:
                return False
        
        # 分别找出 p 和 q 的祖先路径
        trace_p = []
        dfs(root, p, trace_p)
        # print(trace_p)
        trace_q = []
        dfs(root, q, trace_q)
        # print(trace_q)

        # 遍历找出最后一个相同的祖先
        ret = None
        for l, r in zip(trace_p[::-1], trace_q[::-1]):
            if l.val == r.val:
                ret = l
            else:
                break
        
        return ret

优化：不使用额外空间存储祖先路径，即在遍历过程中判断；

二叉树的最近公共祖先（DFS ，清晰图解） - Krahets

  • 如果 node 仅是 p 和 q 的公共祖先（但不是最近公共祖先），那么 node 的左右子树之一必也是 p 和 q 的公共祖先；
  • 如果 node 是 p 和 q 的最近公共祖先，那么 node 的左右子树都不是 p 和 q 的公共祖先；
  • 根据以上两条性质，可知，如果 node 是 p、q 的最近公共祖先，有：
    • node 是 p、q 的公共祖先，且 p 和 q 分别在 node 的两侧；
    • node 是 p 或 q 之一，且是另一个节点的祖先；
Python 
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def lowestCommonAncestor(self, root: TreeNode, p: TreeNode, q: TreeNode) -> TreeNode:
        
        def dfs(node):
            # 下面两个判断条件可以写在一起，为了使逻辑更清晰，故分开写
            if node is None:  # 说明当前路径上没有 p 或 q
                return None
            if node == p or node == q:  # 说明当前路径上存在 p 或 q
                return node
            
            l = dfs(node.left)
            r = dfs(node.right)

            # 返回的非 None 节点都是 p 和 q 的公共祖先
            if l is None and r is not None:  # r 是 p 和 q 之一，且是另一个节点的祖先
                return r
            elif r is None and l is not None:  # l 是 p 和 q 之一，且是另一个节点的祖先
                return l
            elif l and r:  # p 和 q 分别在 node 的两侧
                return node
            else:
                return None

        return dfs(root)

剑指Offer2 001 整数除法 (中等, 2022-02)

二分 经典 剑指Offer2

问题简述 
给定两个整数 a 和 b ，求它们的除法的商 a/b。
要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'。
详细描述 
给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 '*'、除号 '/' 以及求余符号 '%'。

注意：
    整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
    假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−2^31, 2^31−1]。本题中，如果除法结果溢出，则返回 2^31 − 1

示例 1：
    输入：a = 15, b = 2
    输出：7
    解释：15/2 = truncate(7.5) = 7
示例 2：
    输入：a = 7, b = -3
    输出：-2
    解释：7/-3 = truncate(-2.33333..) = -2
示例 3：
    输入：a = 0, b = 1
    输出：0
示例 4：
    输入：a = 1, b = 1
    输出：1
提示:
    -2^31 <= a, b <= 2^31 - 1
    b != 0

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/xoh6Oh
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路1：减法（超时）
  • 用 a 循环减 b，直到为负；
  • 越界讨论：因为是整数除法，实际的越界情况就一种，就是 a=-2^31,b=-1
  • 极端情况：a=2^31-1, b=1 要循坏 2^31-1 次；
Python 
class Solution:
    def divide(self, a: int, b: int) -> int:
        assert b != 0
        
        MAX = 2 ** 31 - 1
        if a == 0: return 0
        if a == -2 ** 31 and b == -1: return MAX  # 越界
        
        # 转为两个整数操作
        sign = 1
        if a < 0:
            sign *= -1
            a = -a
        
        if b < 0:
            sign *= -1
            b = -b

        # 循坏减去 b
        ret = -1
        while a > 0:
            a -= b
            ret += 1

        if a == 0:  # 整除的情况
            ret += 1 
        
        return sign * ret
思路2：二分思想
  1. 初始化返回值 ret = 0
  2. a > b 时，不断将 b 翻倍（乘 2），直到再翻倍一次就大于 a，记翻倍后的数为 tmp_b，翻的倍数为 tmp，然后将 ret 加上 tmp、a 减去 tmp_b；
  3. a 减去 tmp_b 后循环以上过程，直到 a 小于 b；
以 a = 32, b = 3 为例，模拟过程如下：

初始化 ret = 0
第一轮：
    32 / (3*2*2*2) = t1 / (1*2*2*2)  # 再乘一个 2 会大于 32
    32 / 24 = 1 = t1 / 8 -> t1 = 8
    (32 - 24) / 3 = 8 / 3
    ret += t1 -> 8
第二轮：
    8 / (3*2) = t2 / (1*2)
    8 / 6 = 1 = t2 / 2 -> t2 = 2
    (8 - 6) / 3 = 0
    ret += t2 -> 10
因为 2 < 3 退出循环
Python 
class Solution:
    def divide(self, a: int, b: int) -> int:
        assert b != 0
        if a == 0: return 0
        if a == -2**31 and b == -1: return 2 ** 31 - 1
        sign = 1 if (a > 0 and b > 0) or (a < 0 and b < 0) else -1
        a = a if a > 0 else -a
        b = b if b > 0 else -b
        
        # if a < b: return 0

        ret = 0
        while a >= b:
            tmp, tmp_b = 1, b
            while tmp_b * 2 < a:
                tmp_b *= 2
                tmp *= 2
            
            ret += tmp
            a -= tmp_b

        return ret * sign

牛客 0032 求平方根 (简单, 2022-02)

二分 经典 牛客

问题简述 
实现函数 int sqrt(int x).
计算并返回 x 的平方根（向下取整）

求平方根_牛客题霸_牛客网

思路1：二分查找
Python 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
# 
# @param x int整型 
# @return int整型
#
class Solution:
    def sqrt(self , x: int) -> int:
        # write code here
        assert x >= 0
        if x == 0: return 0
        
        l, r = 1, x
        while l < r:
            mid = (l + r) // 2
            if mid <= x / mid:
                if mid + 1 > x / (mid + 1):
                    return mid
                l = mid + 1
            else:
                r = mid - 1
        
        return 1
思路2：牛顿迭代法
  • 牛顿迭代法求根公式：$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)}$；
  • 本题中（为避免歧义，将问题修改为求 $a$ 的根），则 $f(x) = x^2 - a$，带入上式，得 $x_{n+1} = x_n - \frac{x_n^2-a}{2x_n}=(x_n+a/x_n)/2$，初始化 $x_0=a$，迭代计算 $x_n$，直到 $|x_{n+1}-x_n|$ 满足误差要求；
Python 
class Solution:
    def sqrt(self, a: int) -> int:
        # write code here
        assert x >= 0
        if a == 0: return 0

        eps = 1e-1  # 精度要求

        r = a
        while True:
            t = (r + a / r) / 2
            if abs(r - t) < eps:
                break
            r = t

        return int(r)

牛客 0048 在旋转过的有序数组中寻找目标值 (简单, 2022-03)

二分 热门 牛客

问题简述 
有一个长度为 n 的按严格升序排列的整数数组 nums ，在实行 search 函数之前，在某个下标 k 上进行旋转；
给定旋转后的数组 nums 和一个整型 target ，请你查找 target 是否存在于 nums 数组中并返回其下标（从0开始计数），如果不存在请返回-1。

在旋转过的有序数组中寻找目标值_牛客题霸_牛客网

思路
  • 通过比较 nums[m] 和 nums[0] 可以得到知道当前那部分是有序的；
    • 比如当 nums[m] > nums[0] 时，[l, m] 是有序的，反之 [m, r] 是有序的；
  • 然后看 target 是否在有序部分内，然后确定下一步的搜索区间；
写法1：[l, r] 闭区间 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        
        l, r = 0, len(nums) - 1  # 闭区间
        
        # 中止条件：区间内没有元素，对闭区间来说，就是 l > r
        while l <= r:
            m = (l + r) // 2

            if nums[m] == target:
                return m
            
            # 因为 nums 严格递增，可以不考虑等于的情况
            if nums[m] > nums[0]:
                # [l, m] 有序
                if nums[l] <= target < nums[m]:  # 注意 target 可能 == nums[l]
                    r = m - 1
                else:
                    l = m + 1
            else:
                # [m, r] 有序
                if nums[m] < target <= nums[r]:  # 同理 target 是可能 == nums[r]
                    l = m + 1
                else:
                    r = m - 1
            # 因为是闭区间，所以当端点明确不可能是 target 时，可以置信的 +1 或 -1
        
        return -1
写法2：[l, r) 左闭右开 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        
        l, r = 0, len(nums)  # [l, r) 左闭右开
        
        # 中止条件：区间内没有元素，对半开区间来说，就是 l >= r
        while l < r:  # !
            m = (l + r) // 2

            if nums[m] == target:
                return m
            
            if nums[m] > nums[0]:
                if nums[l] <= target < nums[m]:
                    r = m  # !
                else:
                    l = m + 1
            else:
                if nums[m] < target <= nums[r - 1]:  # 防止越界
                    l = m + 1
                else:
                    r = m  # !
        
        return -1
写法3：(l, r] 左开右闭 
class Solution:
    def search(self , nums: List[int], target: int) -> int:
        
        l, r = -1, len(nums) - 1  # (l, r] 左开右闭
        
        # 中止条件：区间内没有元素，对半开区间来说，就是 l >= r
        while l < r:  # !
            m = (l + r + 1) // 2  # +1 保证取到中间值

            if nums[m] == target:
                return m
            
            if nums[m] > nums[0]:
                if nums[l + 1] <= target < nums[m]:  # 防止越界
                    r = m - 1
                else:
                    l = m  # !
            else:
                if nums[m] < target <= nums[r]:
                    l = m  # !
                else:
                    r = m - 1
        
        return -1

牛客 0050 链表中的节点每k个一组翻转 (中等, 2022-03)

链表 热门 牛客

问题简述 
将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

链表中的节点每k个一组翻转_牛客题霸_牛客网

思路（不使用栈）
  • 每次取 k 个节点，反转后接入原链表；
  • 细节很多，不容易写对，详见代码；
Python 
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:

        dummy = ListNode(0)
        dummy.next = head
        
        def reverse(h):
            """标准的反转链表"""
            pre, cur = None, h
            while cur:
                nxt = cur.next
                cur.next = pre
                pre = cur
                cur = nxt
            return pre, h  # 反转后的首尾节点
        
        # [l, r] 分别指向子链表的首尾节点，
        # 小技巧，把 r 初始化为 l 的前一个节点，那么移动 k 次后，就刚好是第 k 个节点
        pre = dummy 
        l, r = head, pre
        while l:
            for _ in range(k):
                r = r.next
                if not r:  # 不足 k 个节点，提前返回
                    return dummy.next
            
            # 断开 r 和 r.next 就是一个标准的链表反转；否则需要调整尾结点的判断，不推荐
            nxt, r.next = r.next, None
            l, r = reverse(l)  # 得到反转后的首尾节点
            pre.next, r.next = l, nxt  # 接入原链表
            pre, l = r, nxt   # 更新下一组 pre, l, r；
            # 因为反转后 r 刚好就是下一组 l 的前一个节点，所以不用再更新
        
        return dummy.next

牛客 0054 三数之和 (中等, 2022-03)

对向双指针 热门 牛客

问题简述 
给出一个有n个元素的数组S，S中是否有元素a,b,c满足a+b+c=0？找出数组S中所有满足条件的三元组。

三数之和_牛客题霸_牛客网

思路
  • 排序；
  • 先确定第一个数；
  • 剩下两个数通过一组双指针分别从两端对向遍历；
  • 难点：去重
    • 首先第一个数需要去重；
    • 双指针遍历的时候也要去重；
  • 详见代码；
Python 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param num int整型一维数组 
# @return int整型二维数组
#
class Solution:
    def threeSum(self , arr: List[int]) -> List[List[int]]:
        
        arr.sort()
        N = len(arr)
        
        ret = []
        
        for i in range(N):
            # 去重1
            if i > 0 and arr[i] == arr[i - 1]:
                continue
            
            # 下面相当于求“两数之和”
            target = -arr[i]
            # 初始化双指针：闭区间
            l, r = i + 1, N - 1
            # 退出循环时 l == r
            while l < r:
                v = arr[l] + arr[r]
                if v < target:
                    l += 1
                elif v > target:
                    r -= 1
                else:
                    ret.append([arr[i], arr[l], arr[r]])
                    # 去重2
                    while l < r and arr[l] == arr[l + 1]: l += 1
                    while l < r and arr[r] == arr[r - 1]: r -= 1
                    # 退出循环时，l,r 停在最后一个相同的数字上，所以还要走一步
                    l += 1
                    r -= 1
        
        return ret

牛客 0066 两个链表的第一个公共结点 (简单, 2022-03)

链表 热门 牛客

问题简述 
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。

两个链表的第一个公共结点_牛客题霸_牛客网

思路1：计算长度差
  • 计算两个链表的长度差 d；让长的链表先走 d 步；
Python 
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        
        def get_len(cur):
            cnt = 0
            while cur:
                cnt += 1
                cur = cur.next
            return cnt
        
        l1 = get_len(pHead1)
        l2 = get_len(pHead2)
        
        if l1 < l2:
            return self.FindFirstCommonNode(pHead2, pHead1)
        
        cur1, cur2 = pHead1, pHead2
        
        d = l1 - l2
        while d:
            cur1 = cur1.next
            d -= 1
        
        while cur1 != cur2:
            cur1 = cur1.next
            cur2 = cur2.next
        
        return cur1
思路2：拼接两个链表
Python 
class Solution:
    def FindFirstCommonNode(self , pHead1 , pHead2 ):
        
        c1, c2 = pHead1, pHead2
        while c1 != c2:
            c1 = c1.next if c1 else pHead2
            c2 = c2.next if c2 else pHead1
        
        return c1

牛客 0067 汉诺塔问题 (中等, 2022-03)

递归 经典 牛客

问题简述 
请实现一个函数打印汉诺塔问题的最优移动轨迹。
输入：
    2
返回值：
    ["move from left to mid","move from left to right","move from mid to right"]

汉诺塔问题_牛客题霸_牛客网

思路
  • 定义 move(i, left, right, mid) 表示把 i 个圆盘从 left 移动到 right，通过 mid；
  • 移动过程：
    • move(i - 1, left, mid, right)：先把上面 i-1 个圆盘从 left 移动到 mid，通过 right；
    • f'move from {left} to {right}'：把最底下的圆盘从 left 移动到 right
    • move(i - 1, mid, right, left)：再把这 i-1 个圆盘从 mid 移动到 right，通过 left
Python 
class Solution:
    def getSolution(self, n: int) -> List[str]:
        ret = []

        def move(i, left, right, mid):
            """把 i 个圆盘从 left 移动到 right，通过 mid"""
            if i == 0: return

            move(i - 1, left, mid, right)  # 先把上面 i-1 个圆盘从 left 移动到 mid，通过 right
            ret.append(f'move from {left} to {right}')  # 把最底下的圆盘从 left 移动到 right
            move(i - 1, mid, right, left)  # 再把这 i-1 个圆盘从 mid 移动到 right，通过 left

        move(n, 'left', 'right', 'mid')
        return ret

牛客 0070 单链表的排序 (简单, 2022-03)

链表 经典 牛客

问题简述 
给定一个节点数为n的无序单链表，对其按升序排序。

单链表的排序_牛客题霸_牛客网

思路1：归并排序
  • 细节：
    • 找中点的时候，定位到中点的前一个位置，保存中点位置后切断，否则会无限循环；
    • 递归的 base case：最好判断为空节点或只有一个节点时就返回；
Python 
class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        
        def merge(h):
            if not h or not h.next: return h
            
            # 找中点
            f, s = h.next, h
            while f and f.next:
                f = f.next.next
                s = s.next
            
            # 切断
            m, s.next = s.next, None
            l, r = merge(h), merge(m)
            
            # 合并
            cur = dummy = ListNode(0)
            while l and r:
                if l.val < r.val:
                    cur.next = l
                    l = l.next
                else:
                    cur.next = r
                    r = r.next
                cur = cur.next
            
            cur.next = l if l else r
            return dummy.next
        
        return merge(head)
思路2：快排（超时）
  • 链表的快排比数组好写一点，因为链表可以方便的移动节点，而不需要要交换；
  • 默认使用头结点作为 pivot，因此部分用例无法通过（超过最大递归）；
  • 对链表来说似乎没有很好的办法来确定 pivot；
Python 
class Solution:
    def sortInList(self , head: ListNode) -> ListNode:
        
        import sys
        sys.setrecursionlimit(1000000)
        
        def qsort(h):
            if not h or not h.next: return h
            
            s = small = ListNode(0)
            l = large = ListNode(0)
            cur = h.next
            while cur:
                if cur.val <= h.val:
                    s.next = cur
                    s = s.next
                else:
                    l.next = cur
                    l = l.next
                cur = cur.next
            
            s.next = h
            h.next = l.next = None
            
            small = qsort(small.next)
            large = qsort(large.next)
            h.next = large
            
            return small
        
        ret = qsort(head)
        return ret

牛客 0080 把二叉树打印成多行 (中等, 2022-03)

二叉树 热门 牛客

问题简述 
给定一个节点数为 n 二叉树，要求从上到下按层打印二叉树的 val 值，同一层结点从左至右输出，每一层输出一行，将输出的结果存放到一个二维数组中返回。

把二叉树打印成多行_牛客题霸_牛客网

思路1：队列
Python 写法1：一个队列，通过节点数判断层次 
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        if not pRoot: return []
        
        from collections import deque
        
        q = deque()
        q.append(pRoot)
        cnt = 1  # 当前层的节点数
        nxt = 0  # 下一层的节点数
        tmp = []  # 当前层的节点
        ret = []
        
        while q:
            x = q.popleft()
            tmp.append(x.val)
            cnt -= 1
            
            if x.left:
                q.append(x.left)
                nxt += 1
            if x.right:
                q.append(x.right)
                nxt += 1
            
            if not cnt:  # 如果当前层的节点输出完了，打印下一层的节点
                ret.append(tmp[:])
                tmp = []
                cnt = nxt
                nxt = 0
            
        return ret
Python 写法2：两个队列，当前层和下一层 
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        if not pRoot: return []
        
        cur, nxt = [], []
        cur.append(pRoot)
        ret, tmp = [], []
        
        while cur:
            for x in cur:
                tmp.append(x.val)
                if x.left: nxt.append(x.left)
                if x.right: nxt.append(x.right)
            ret.append(tmp[:])
            cur, nxt, tmp = nxt, [], []
            
        return ret
思路2：递归+字典（推荐）
Python 
class Solution:
    def Print(self , pRoot: TreeNode) -> List[List[int]]:
        from collections import defaultdict
        
        book = defaultdict(list)
        
        def dfs(x, depth):
            if not x: return
            book[depth].append(x.val)
            dfs(x.left, depth + 1)
            dfs(x.right, depth + 1)
        
        dfs(pRoot, 0)
        # Python 3.6 之后，字典默认是有序的，因此直接打印即可
        return list(book.values())

牛客 0145 01背包 (中等, 2022-03)

DP DFS2DP 经典 牛客

问题简述 
给定最多能容纳 V 体积的背包，和 n 个物品，每个物品有重量(w)和体积(v)两个属性；
求背包能放的最大重量；
每个物品的重量(w)和体积(v)保存在数组 vw 中；

示例1：
    输入：10,2,[[1,3],[10,4]]
    返回：4
示例2：
    输入：10,2,[[1,3],[9,8]]
    返回：11

01背包_牛客题霸_牛客网

总结
  • 熟练掌握思路 1 的优化路径（解新题）；
  • 牢记 01 背包的一维转移方程：
    • 优化目标是最大重量：dp[i] = max(dp[i], dp[i - v[i]] + w[i])
    • 优化目标是最小空间：dp[i] = min(dp[i], dp[i - w[i]] + v[i])
思路1：暴力递归+记忆化搜索 -> 动态规划
Python：写法1）暴力递归+记忆化搜索 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        import sys
        sys.setrecursionlimit(1010)  # 解除递归深度限制
        
        # 记忆空间
        dp = dict()
        
        # 剩余空间为 rest 的情况下，前 i 个物品能装载的最大值
        def dfs(i, rest):
            if (i, rest) in dp:
                return dp[(i, rest)]
            
            # 递归基
            if i == 0:
                return 0
            
            # 不拿第 i 个物品
            r1 = dfs(i - 1, rest)
            # 拿第 i 个物品，前提是空间足够
            r2 = 0
            if rest >= vw[i - 1][0]:  # 注意第 i 个物品第下标是 i-1，这里最容易犯错
                r2 = dfs(i - 1, rest - vw[i - 1][0]) + vw[i - 1][1]
            
            # 记忆
            dp[(i, rest)] = max(r1, r2)
            return dp[(i, rest)]
        
        return dfs(n, V)  # 因为下标从 0 开始，所以第 n 个物品的下标为 n-1
Python：写法2）使用标准库提供的缓存（爆栈）
  • 不知道什么原因无法通过最长的用例，好像 lru_cache 和 setrecursionlimit 不能同时生效；
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        from functools import lru_cache
        import sys
        sys.setrecursionlimit(1010)  # 解除递归深度限制
        
        # 剩余空间为 rest 的情况下，前 i 个物品能装载的最大值
        @lru_cache(maxsize=None)
        def dfs(i, rest):
            if i == -1:  # 因为下标从 0 开始，所以递归基设为 -1
                return 0
            
            # 不拿第 i 个物品
            r1 = dfs(i - 1, rest)
            # 拿第 i 个物品，前提是空间足够
            r2 = 0 if rest < vw[i][0] else dfs(i - 1, rest - vw[i][0]) + vw[i][1]

            return max(r1, r2)
        
        return dfs(n - 1, V)  # 因为下标从 0 开始，所以第 n 个物品的下标为 n-1
Python：写法3）将暴力递归转成动态规划 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        dp = [[0] * (V + 1) for _ in range(n + 1)]
        # 对应递归基：剩余容量为 V 时前 0 个物品的最大重量
        dp[0][V] = 0
        
        for i in range(1, n + 1):
            for rest in range(V + 1):  # 这里正序逆序遍历都可以
                # 与 dfs 的过程一一对应
                r1 = dp[i - 1][rest]
                r2 = 0
                if rest >= vw[i - 1][0]:
                    r2 = dp[i - 1][rest - vw[i - 1][0]] + vw[i - 1][1]
                dp[i][rest] = max(r1, r2)
        
        return dp[n][V]
思路2：一维 DP（内存优化）
  • 因为每次更新第 i 行数据时，只与 i-1 行有关，所以可以使用一维数组优化；
Python 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        dp = [0] * (V + 1)
        dp[0] = 0  # 可以省略
        
        for i in range(1, n + 1):
            for rest in range(V, vw[i - 1][0] - 1, -1):
                # 不拿第 i 个物品
                r1 = dp[rest]
                # 拿第 i 个物品
                r2 = dp[rest - vw[i - 1][0]] + vw[i - 1][1]
                # 取较大的
                dp[rest] = max(r1, r2)
        
        return dp[V]

为什么一维 DP 中要逆序遍历体积？

二维状态的转移方程：dp[i][j]=max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]);
一维状态的转移方程：dp[j]=max(dp[j], dp[j-v[i]] + w[i]);

可以看到二维中更新第 i 层数据用的都是 i - 1 层的数据，因为第 i - 1 层的数据已经固定，所以正序逆序遍历都无所谓；而如果在一维状态中正序遍历，那么 dp[j-v[i]] 会在 dp[j] 前被更新，导致 dp[j] 得到错误的答案；

关于01背包和完全背包的优化的体积顺序问题_听-起风了的博客-CSDN博客

思路3：另一种尝试
  • 思路 1 是最直观的尝试方法；但存在一个问题，就是当 V 非常大时，可能会超时；
  • 此时可以尝试另一个递推思路，定义 dp[i][w] 表示前 i 个物品达到重量为 w 时需要的最小空间；
  • 最后的答案为满足 dp[n][w] <= V 时最大的 w；
  • 事实上，对比后可以发现两者的转移方程非常相似：
    • 最大重量：dp[i] = max(dp[i], dp[i - v[i]] + w[i])
    • 最小空间：dp[i] = min(dp[i], dp[i - w[i]] + v[i])
Python：写法1）二维 DP 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        # 重量上限，即所有物品的重量和
        W = sum(it[1] for it in vw)
        
        # 初始化为无穷大
        #   也可以初始化为 -1，表示不能达到的重量，但是没有直接初始化为无穷大方便；
        dp = [[float('inf')] * (W + 1) for _ in range(n + 1)]
        dp[0][0] = 0  # 重量为 0 所需的最小空间也是 0
            
        for i in range(1, n + 1):
            for w in range(W + 1):
                r1 = dp[i - 1][w]
                r2 = float('inf')
                if w - vw[i - 1][1] >= 0:
                    r2 = dp[i - 1][w - vw[i - 1][1]] + vw[i - 1][0]
                dp[i][w] = min(r1, r2)
            
        for w in range(W, -1, -1):
            if dp[n][w] <= V:
                return w
            
        return 0
Python：写法2）一维 DP 
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 计算01背包问题的结果
# @param V int整型 背包的体积
# @param n int整型 物品的个数
# @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
# @return int整型
#
class Solution:
    def knapsack(self , V: int, n: int, vw: List[List[int]]) -> int:
        # write code here
        
        # 最大重量
        W = sum(it[1] for it in vw)
        
        # 初始化为无穷大
        dp = [float('inf')] * (W + 1)
        dp[0] = 0  # 重量为 0 所需的最小空间也是 0
            
        for i in range(1, n + 1):
            for w in range(W, vw[i - 1][1] - 1, -1):
                dp[w] = min(dp[w], dp[w - vw[i - 1][1]] + vw[i - 1][0])
        
        # 逆序遍历 S，当找到需要的最小体积相遇等于 V 时，此时的 w 就是最大重量
        for w in range(W, -1, -1):
            if dp[w] <= V:
                return w
            
        return 0
代码验证
  • 因为上面一些代码不能通过 OJ，所以离线写了一个对数器验证正确性（假设能通过 OJ 的 Solution1 是正确的）；
Python 
from typing import *


class Solution1:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        dp = [[0] * (V + 1) for _ in range(n + 1)]
        # 对应递归基：剩余容量为 V 时前 0 个物品的最大重量
        dp[0][V] = 0

        for i in range(1, n + 1):
            for rest in range(V + 1):  # 这里正序逆序遍历都可以
                # 与 dfs 的过程一一对应
                r1 = dp[i - 1][rest]
                r2 = 0
                if rest >= vw[i - 1][0]:
                    r2 = dp[i - 1][rest - vw[i - 1][0]] + vw[i - 1][1]
                dp[i][rest] = max(r1, r2)

        return dp[n][V]


class Solution2:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        dp = [0] * (V + 1)
        dp[0] = 0  # 可以省略

        for i in range(1, n + 1):
            for rest in range(V, vw[i - 1][0] - 1, -1):
                # 不拿第 i 个物品
                r1 = dp[rest]
                # 拿第 i 个物品
                r2 = dp[rest - vw[i - 1][0]] + vw[i - 1][1]
                # 取较大的
                dp[rest] = max(r1, r2)

        return dp[V]


class Solution3:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        # 最大重量
        W = sum(it[1] for it in vw)

        # 初始化为无穷大
        dp = [[float('inf')] * (W + 1) for _ in range(n + 1)]
        dp[0][0] = 0  # 重量为 0 所需的最小空间也是 0

        for i in range(1, n + 1):
            for w in range(W + 1):
                r1 = dp[i - 1][w]
                r2 = float('inf')
                if w - vw[i - 1][1] >= 0:
                    r2 = dp[i - 1][w - vw[i - 1][1]] + vw[i - 1][0]
                dp[i][w] = min(r1, r2)

        for w in range(W, -1, -1):
            if dp[n][w] <= V:
                return w

        return 0


class Solution4:
    def knapsack(self, V: int, n: int, vw: List[List[int]]) -> int:
        # write code here

        # 最大重量
        W = sum(it[1] for it in vw)

        # 初始化为无穷大
        dp = [float('inf')] * (W + 1)
        dp[0] = 0  # 重量为 0 所需的最小空间也是 0

        for i in range(1, n + 1):
            for w in range(W, vw[i - 1][1] - 1, -1):
                dp[w] = min(dp[w], dp[w - vw[i - 1][1]] + vw[i - 1][0])

        # 逆序遍历 S，当找到需要的最小体积相遇等于 V 时，此时的 w 就是最大重量
        for w in range(W, -1, -1):
            if dp[w] <= V:
                return w

        return 0


def random_input():
    import random
    MAX = 1000

    V = random.randint(1, MAX)
    n = random.randint(1, 100)  # 因为 方法 3, 4 比较慢，所以控制一下 n 的范围

    vw = []
    for _ in range(n):
        v, w = random.randint(1, MAX), random.randint(1, MAX)
        vw.append([v, w])

    return V, n, vw


def _test():
    """"""
    for _ in range(10):
        V, n, vw = random_input()
        r1 = Solution1().knapsack(V, n, vw)
        r2 = Solution2().knapsack(V, n, vw)
        r3 = Solution3().knapsack(V, n, vw)
        r4 = Solution4().knapsack(V, n, vw)

        assert r1 == r2 == r3 == r4


if __name__ == '__main__':
    """"""
    _test()