Hot 100 第三部分

Hot 100 第三部分

Hot 100 指的是 LeetCode 上的一个题单

撰写第 68 ~ 100 题

15 三数之和

双指针枚举，需要尤其注意用排序去重

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        n = len(nums)
        ret = []
        for i in range(n - 2):
            if nums[i] > 0:
                continue
            if i != 0 and nums[i - 1] == nums[i]: # 重复值去重
                continue
            target = -nums[i]
            l = i + 1
            r = n - 1
            while l < r:
                curr = nums[l] + nums[r]
                if curr < target:
                    l += 1
                elif curr > target:
                    r -= 1
                else:
                    ret.append([nums[i], nums[l], nums[r]])
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]: # 重复值去重
                        l += 1
                    while l < r and nums[r] == nums[r + 1]: # 重复值去重
                        r -= 1
        return ret

11 盛最多水的容器

双指针算法，永远移动更短的那个，因为最大值永远受制于更短的那个值

class Solution:
    def maxArea(self, height: List[int]) -> int:
        n = len(height)
        l, r = 0, n - 1
        size = 0
        while l < r:
            if height[l] < height[r]:
                size = max(size, (r - l) * height[l])
                l += 1
            else:
                size = max(size, (r - l) * height[r])
                r -= 1
        return size

10 正则表达式匹配

这是一个 dp 题目，初见难想到

dp[i][j] 表示s[:i]（前 i 个字符）是否能匹配 p[:j]（前 j 个字符）

这个 dp 的初始化也要注意，算是一个相对困难的题目了

class Solution:
    def isMatch(self, s: str, p: str) -> bool:
        m = len(s) + 1
        n = len(p) + 1
        dp = [[False] * n for _ in range(m)] # dp[i][j]表示 s[:i] 匹配 p[:j]

        # 初始化
        dp[0][0] = True
        for j in range(2, n):
            if p[j - 1] == '*':
                dp[0][j] = dp[0][j - 2]

        def _match(sc, pc):
            return pc == '.' or sc == pc

        for i in range(1, m):
            for j in range(1, n):
                sc = s[i - 1]
                pc = p[j - 1]
                if pc != "*":
                    dp[i][j] = dp[i - 1][j - 1] and _match(sc, pc)
                else:
                    dp[i][j] = dp[i][j - 2] # 跳过不匹配
                    dp[i][j] |= _match(sc, p[j - 2]) and dp[i - 1][j]    # 尝试匹配一次
        return dp[m - 1][n - 1]

5 最长回文子串

Manacher 算法，背诵一下，其他时候直接遍历中心扩展就行了

class Solution:
    def longestPalindrome(self, s: str) -> str:
        # 预处理
        t = "^#" + "#".join(s) + "#$"
        n = len(t)
        p = [0] * n # 回文半径长度

        # center/right：当前已知“最右回文”的中心与其右边界（right 为该回文最右端索引）
        center = 0
        right = 0

        best_center = 0     # z最长字符串在预处理串 t 中的中心位置

        # 线性扫描每个中心 i
        for i in range(1, n - 1):
            mirror = 2 * center - i  # i 关于 center 的对称点

            #  i 在当前最右回文覆盖范围内，可以用对称性给 p[i] 一个下界
            if i < right:
                # right - i：i 到右边界还剩多少可用空间
                # p[mirror]：对称点的半径
                p[i] = min(right - i, p[mirror])

            # 在已有半径基础上继续向两侧暴力扩展
            while t[i + p[i] + 1] == t[i - p[i] - 1]:
                p[i] += 1

            # 如果以 i 为中心的回文超出了当前 right，则更新 center/right
            if i + p[i] > right:
                center = i
                right = i + p[i]

            # 维护全局最优
            if p[i] > p[best_center]:
                best_center = i

        # 映射回原串，注意到原来的 radius 就是回文串长度
        start = (best_center - p[best_center]) // 2
        return s[start:start + p[best_center]]

4 寻找两个正序数组的中位数

背诵题，用二分法切割最小长度的数组得到，尤其需要注意边界条件（很麻烦）

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        A, B = nums1, nums2
        if len(A) > len(B):
            A, B = B, A

        m, n = len(A), len(B)
        half = (m + n + 1) // 2

        low, high = 0, m
        while low <= high:
            i = (low + high) // 2
            j = half - i

            A_left  = A[i - 1] if i > 0 else float("-inf")
            A_right = A[i]     if i < m else float("inf")
            B_left  = B[j - 1] if j > 0 else float("-inf")
            B_right = B[j]     if j < n else float("inf")

            if A_left > B_right:
                high = i - 1
            elif B_left > A_right:
                low = i + 1
            else:
                left_max = max(A_left, B_left)
                if (m + n) % 2 == 1:
                    return float(left_max)
                right_min = min(A_right, B_right)
                return (left_max + right_min) / 2.0

        raise RuntimeError("unreachable")

3 无重复字符的最长子串

假如 [a, b] 区间是一个不重复的字串，那么 [a + 1, b] 一定也是，从下标 b 开始用 hash 扩展

本质是利用了下一个不重复字串的结尾一定 大于等于上一个的字串的性质

另外要注意的就是 python 中 set 的用法： add, discard 分别对应了增加和删除

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 双指针滑动窗口
        n = len(s)
        mp = set()
        r = 0
        ret = 0
        for l in range(n): # 闭区间区间窗口 [l, r]
            while r < n and s[r] not in mp: # 不在则加入，同时最长长度更新
                mp.add(s[r])
                ret = max(r - l + 1, ret)
                r += 1
            mp.discard(s[l]) # 左边界前移
        return ret

2 两数相加

罗列所有情况即可，能考虑到所有的情况就没有难度

class Solution:
    def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode()
        curr = dummy
        p1, p2 = l1, l2
        pre = 0 # 低位来的进位
        while p1 and p2:
            s = p1.val + p2.val + pre
            pre = s // 10
            new = ListNode(val=s % 10)
            curr.next = new
            curr = new
            p1, p2 = p1.next, p2.next
        left = p1 if p1 is not None else p2
        while left is not None: # 有一个没结束
            s = left.val + pre
            pre = s // 10
            new = ListNode(val=s % 10)
            curr.next = new
            curr = new
            left = left.next
        if pre != 0: # 还有进位
            new = ListNode(val=pre)
            curr.next = new
        return dummy.next

79 单词搜索

就是 dfs 回溯，可以有多种剪枝的方式

这里可以注意以下，能不用 hash 就不用，如果用到了 set() 尽可能用 remove() 因为能减少一次分支判断（代价是如果删除不存在的键会直接报错）

class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        direction = [(-1, 0), (1, 0), (0, 1), (0, -1)]
        start = word[0]
        m = len(board)   # m * n 矩形
        n = len(board[0])
        l = len(word)
        def dfs(x, y, idx): # [0, idx) 匹配成功
            if idx == l:
                return True
            for dir in direction:
                xn = x + dir[0]
                yn = y + dir[1]
                if not (0 <= xn < m and 0 <= yn < n):
                    continue
                if board[xn][yn] != word[idx]:
                    continue
                board[xn][yn] = '#'
                if (dfs(xn, yn, idx + 1)):
                    return True # 上报直接返回
                board[xn][yn] = word[idx]
            return False    # 4 个边界都不对
        for i in range(m):
            for j in range(n):
                if board[i][j] == start:
                    board[i][j] = '#'
                    if dfs(i, j, 1):
                        return True
                    board[i][j] = start
        return False

114 二叉树展开为链表

这道题的 O(1) 解法还是需要学习一下的

核心思想和 Morris 遍历算法类似，本质是能够确定两个点：

• 当前递归分支的“结束节点”是谁
• 结束之后的“唯一下一步”是谁

确定完毕后，把这两个点接上，就能展开递归栈为线性，不使用递归，改成循环

class Solution:
    def flatten(self, root):
        cur = root
        while cur:
            if cur.left:
                # 1. 找左子树最右节点（展开后左链表的尾）
                pre = cur.left
                while pre.right:
                    pre = pre.right

                # 2. 原右子树接到左子树尾部
                pre.right = cur.right

                # 3. 左子树整体搬到右边
                cur.right = cur.left
                cur.left = None

            # 4. 沿着先序链继续
            cur = cur.right

621 任务调度器

数学题，永远是任务数最多的影响总长度，同时最长的个数有可能是多个

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        m = len(tasks)
        count = [0] * 26
        tmax = 0 # 最多的任务的数量
        cmax = 1 # 有几个并列最多的
        for t in tasks:
            idx = ord(t) - ord('A')
            count[idx] += 1
            if count[idx] > tmax:
                cmax = 1
                tmax = count[idx]
            elif count[idx] == tmax:
                cmax += 1
        return max(m, (tmax - 1) * (n + 1) + cmax)

617 合并二叉树

前序遍历标准解法

class Solution:
    def mergeTrees(self, root1: Optional[TreeNode], root2: Optional[TreeNode]) -> Optional[TreeNode]:
        # 先序遍历
        def pretraversal(r1, r2):
            if not r1:
                return r2
            if not r2:
                return r1
            curr = TreeNode(r1.val + r2.val)
            curr.left = pretraversal(r1.left, r2.left)
            curr.right = pretraversal(r1.right, r2.right)
            return curr

        return pretraversal(root1, root2)

105 从前序与中序遍历序列构造二叉树

递归分割，有很多的细节需要注意一下

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        n = len(preorder)
        pos = {v: i for i, v in enumerate(inorder)}  # O(n)
        def build(pre_a, pre_b, in_a, in_b):
            if pre_a == pre_b:
                return None
            # 中分节点
            root_val = preorder[pre_a] # 前序遍历的第一个
            mid_idx = pos[root_val]
            left_len = mid_idx - in_a
            root = TreeNode(root_val)
            root.left = build(pre_a + 1, pre_a + 1 + left_len, in_a, mid_idx)
            root.right = build(pre_a + 1 + left_len, pre_b, mid_idx + 1, in_b)
            return root
        ret = build(0, n, 0, n)
        return ret

104 二叉树的最大深度

简单 dfs，另外还有层序遍历的方法，参考下一题

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        def dfs(curr):
            if curr is None:
                return 0
            l = dfs(curr.left)
            r = dfs(curr.right)
            return max(l , r) + 1
        return dfs(root)

102 二叉树的层序遍历

BFS 用队列实现层序遍历，唯一要注意的就是如何判断是同一层

用两重循环 + 队列大小就可以控制，保证外层循环一定是同一层

注意一下：BFS 中一般不会把没有意义的节点放入队列，这会破坏 BFS 的语义逻辑

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        # 规定左进右出， 二重循环保证层级关系
        q = deque()
        if root is None:
            return []
        q.appendleft(root)
        ret = []
        while q:
            size = len(q) # 当前层的节点数量
            level = []
            for _ in range(size):
                curr = q.pop()
                level.append(curr.val)
                if curr.left:
                    q.appendleft(curr.left)
                if curr.right:
                    q.appendleft(curr.right)
            ret.append(level)
        return ret

101 对称二叉树

对称性用左右节点对比，递归保持比较逻辑不变（只对比根节点逻辑，孩子交给下一层递归）

class Solution:
    def isSymmetric(self, root: Optional[TreeNode]) -> bool:
        def dfs(l, r):
            if l is None:
                return r is None
            if r is None:
                return l is None

            if l.val != r.val:
                return False
            return dfs(l.left, r.right) and dfs(l.right, r.left)
        if root is None:
            return True
        return dfs(root.left, root.right)

98 验证二叉搜索树

BST 最重要的性质就是中序遍历是递增的

所以实际上就是中序遍历把树线性化，然后检查这个序列的严格递增性

class Solution:
    def isValidBST(self, root: Optional[TreeNode]) -> bool:
        # 先写一个中序遍历
        pre = float("-inf")
        def dfs(curr):
            nonlocal pre
            if curr is None:
                return True

            if not dfs(curr.left):
                return False
            if curr.val <= pre:
                return False
            pre = curr.val
            if not dfs(curr.right):
                return False
            return True

        return dfs(root)

96 不同的二叉搜索树

动态规划题目（数学解法就不用考虑了）

BST 的个数只和节点的数量有关，就可以分析了，起始条件n = 0和 n = 1

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)
        dp[0] = 1
        dp[1] = 1
        for i in range(2, n + 1):
            for j in range(1, i + 1):
                dp[i] += dp[j - 1] * dp[i - j]
        return dp[n]

94 二叉树的中序遍历

递归不赘述了，这里写一个迭代法，迭代法还是要记忆一下逻辑的

当一个节点从栈顶 pop() 出来时，意味着：

• 它的左子树已经完全处理完（否则它不可能位于栈顶并被弹出）
• 现在该做的唯一事情就是：访问它自己（中）
• 然后把问题切换到它的右子树

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        stk = []
        ret = []
        curr = root

        while curr or stk:
            # 一直向左走
            while curr:
                stk.append(curr)
                curr = curr.left

            # 访问中间节点
            curr = stk.pop()
            ret.append(curr.val)

            # 转向右子树
            curr = curr.right

        return ret

85 最大矩形

先写 84 再写 85，是 84 的扩展解法，逐行计算 84

class Solution:
    @staticmethod
    def largestRectangleArea(heights: List[int]) -> int:
        hs = [0] + heights + [0]   # 不修改入参
        stk = [0]
        ret = 0
        for i in range(1, len(hs)):
            while hs[i] < hs[stk[-1]]:
                mid = stk.pop()
                left = stk[-1]
                ret = max(ret, hs[mid] * (i - left - 1))
            stk.append(i)
        return ret

    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0
        R, C = len(matrix), len(matrix[0])
        heights = [0] * C
        ret = 0

        # 从最小的高度开始逐步上升，一旦中断就归零
        for r in range(R):
            for c in range(C):
                heights[c] = heights[c] + 1 if matrix[r][c] == '1' else 0
            ret = max(ret, self.largestRectangleArea(heights),)
        return ret

84 柱状图中最大的矩形

单调栈的经典题目，这里使用了哨兵来处理栈中剩下的值

这里有隐患就是，如果heights中间出现了 0 值会出错，这在 85 题是比较麻烦的，具体修改可以看 85 解法

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stk = []
        heights.insert(0, 0)
        heights.append(0)
        n = len(heights)
        ret = 0
        for i in range(n):
            while stk and heights[i] < heights[stk[-1]]:
                # 不满足递减了，要弹出
                mid_idx = stk.pop()
                right_idx = i
                left_idx = stk[-1]
                sz = (right_idx - left_idx - 1) * heights[mid_idx]
                ret = max(sz, ret)
            stk.append(i)
        return ret

1 两数之和

哈希经典题

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        s = dict()
        n = len(nums)
        ret = [] * n
        for i in range(n):
            if target - nums[i] not in s:
                s[nums[i]] = i
            else:
                return [i, s[target - nums[i]]]

78 子集

回溯经典题

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        ret = [[]]
        n = len(nums)
        def dfs(idx, path):
            if idx >= n:
                return
            for i in range(idx, n):
                path.append(nums[i])
                ret.append(path.copy())
                dfs(i + 1, path)
                path.pop()
        dfs(0, [])
        return ret

76 最小覆盖子串

难题，建议掌握一下，滑动窗口思路

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        need = {}
        n = len(s)
        for c in t:
            need[c] = need.get(c, 0) + 1
        missing = len(need) # 表示窗口还缺多少字母种类
        l, r = 0, 0 # [l, r)
        best_l = 0
        ret = float('inf') # 表示最短窗口
        for r, ch in enumerate(s):  # [l , r]
            if ch in need:
                need[ch] -= 1
                if need[ch] == 0:
                    missing -= 1
            while missing == 0: # 窗口齐了，开始收缩左边
                # 左压缩窗口
                window = r - l + 1
                if window < ret:
                    best_l = l
                    ret = window
                if s[l] in need:
                    need[s[l]] += 1
                    if need[s[l]] == 1:
                        missing += 1
                l += 1

        return "" if ret == float('inf') else s[best_l:best_l + ret]

75 颜色分类

三指针算法，利用了快速排序的思想，维护两个已经确定的区间，并逐步扩大这个区间直到整个数组满足

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        n = len(nums)
        l, r, i = 0, n - 1, 0
        while i <= r:
            if nums[i] == 0:
                nums[i], nums[l] = nums[l], nums[i]
                l += 1
                i += 1
            elif nums[i] == 1:
                i += 1
            elif nums[i] == 2:
                nums[i], nums[r] = nums[r], nums[i]
                r -= 1

72 编辑距离

字符串 dp 经典题，遇到过就不难

这里写了个二维的，一维的优化一下就有了，不过一般是二维写出来再优化

class Solution:
    def minDistance(self, word1: str, word2: str) -> int:
        m = len(word1)
        n = len(word2)
        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):
                if word1[i - 1] == word2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1]
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1]) + 1 # 删减
                    dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + 1)
        return dp[m][n]

70 爬楼梯

dp 入门

class Solution:
    def climbStairs(self, n: int) -> int:
        now, pre1, pre2 = 1, 1, 1
        for i in range(2, n + 1):
            now = pre1 + pre2
            pre1, pre2 = pre2, now
        return now

581 最短无序连续子数组

双向扩展区间法，可以参考一下，有点贪心的思想

class Solution:
    def findUnsortedSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        l, r = 0, -1
        max_num = float('-inf')
        min_num = float('inf')
        for i in range(n):
            if nums[i] >= max_num: # 递增允许
                max_num = nums[i]
            else:
                r = i   # 破坏递增了
        if r == -1:
            return 0 # 有序
        for j in range(n - 1, -1, -1):
            if nums[j] <= min_num:
                min_num = nums[j]
            else:
                l = j
        return r - l + 1

64 最小路径和

动态规划，压缩 1 维 dp 的时候有很多特判边界条件

这里用第一行特判+从第二行开始只对第一列特判，解决了 [0][0] 的下标问题

class Solution:
    def minPathSum(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [float('inf')] * n
        dp[0] = grid[0][0]
        # 初始化第一行
        for j in range(1, n):
            dp[j] = dp[j - 1] + grid[0][j]
        # 从第二行开始
        for i in range(1, m):
            dp[0] += grid[i][0]  # 第一列只能从上面来
            for j in range(1, n):
                dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
        return dp[-1]

62 不同路径

上一题的简化版本，用同样的方式从二维压缩到一维

class Solution:
    def uniquePaths(self, m: int, n: int) -> int:
        dp = [1] * (n + 1) # 第一列全是 1
        dp[0] = 1
        for i in range(1, m):
            dp[0] = 0 # 最上面一个不允许从上来
            for j in range(1, n + 1):
                    dp[j] += dp [j - 1]
        return dp[n]

56 合并区间

排序后模拟即可，这里注意一下 python 中的排序语法就行了

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x : (x[0], x[1]))
        ret = []
        path = intervals[0].copy()
        for interval in intervals:
            # 可以扩展
            if interval[0] <= path[1]:
                path[1] = max(interval[1], path[1]) # 扩展右区间
            else: # 断开了
                ret.append(path.copy())
                path = interval.copy()
        if path:
            ret.append(path)
        return ret

55 跳跃游戏

简单贪心

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        i, far = 0, 0
        n = len(nums)
        while i <= far and i < n:
            far = max(far, i + nums[i])
            i += 1
        return i == n

53 最大子数组和

简答贪心

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 前缀和
        ret = float('-inf')
        curr = 0
        for n in nums:
            curr += n
            ret = max(ret, curr)
            if curr < 0:
                curr = 0
        return ret