CodeTop - Top 30

题目	简述、方案、死人坑
二叉树的锯齿形层序遍历	判空、队列长度提前记录，遍历队列
反转链表 II	迭代法：nxt->cur.next->nxt.next->pre.next->nxt 递归法：终止条件判断的是`head`，返回的也是`head` 递归法：p -> head -> tail/none -> p
合并K个升序链表	分治法：0/1/2/分治最小堆：折半逆序建堆，`pop`和`push`之后记得维护有序，`down`操作里面维护`idx`
螺旋矩阵	自己想办法吧，别反了方向就行
最长递增子序列	动态规划：`dp`维护最长子序列长度，起始为1，遍历前面计算耐心排序二分查找：堆内不严格递减，堆顶严格递增，堆数就是长度
字符串相加	`while i or j or carry:`
相交链表	两个指针，两边都走一遍，交点处相遇
重排链表	三位一体，重排链表=拆分链表+反转链表+合并链表拆分链表：这里必须从`head`开始，才会停在中点靠左，拆的时候中点要先记录再断开，最后再返回记录的这个点反转链表：老生常谈的问题，返回值是`head`不是其他合并链表：这个其实很简单
合并区间	`arr.sort(key=lambda x:(x[0], x[1]))`
接雨水	三次线性扫描：扫描左边最高点，扫描右边最高点 `left[i] = max(left[i-1], height[i])` `res += min(left[i], right[i]) - height[i]` 一次单调栈：栈内存坐标，栈里单调递减，每次都要入栈，遇到不符合的就弹栈，弹出的是底部坐标，栈顶是左侧坐标（没有就放弃），另外注意我们的高度是`min(h[r],h[l])-h[b]`，宽度是`r-l-1`一定是减一而不是加一

二叉树的锯齿形层序遍历

103. 二叉树的锯齿形层序遍历

题目描述

给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

方法1：BFS + 队列

核心思路

使用 BFS（广度优先搜索） 进行层序遍历。
通过一个队列来维护当前层的节点。
使用一个变量 direction 来标记当前层是否需要反转（即从右往左遍历），并在每一层遍历结束后切换方向。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []

        result = []  # 存储最终结果
        queue = deque([root])  # 初始化队列，加入根节点
        direction = 1  # 初始方向为从左到右（1 表示从左到右，-1 表示从右到左）

        while queue:  # 当队列不为空时继续遍历
            level_len = len(queue)  # 当前层节点数量
            current_level = []  # 存储当前层的节点值

            for _ in range(level_len):
                node = queue.popleft()  # 从队列中取出一个节点
                current_level.append(node.val)  # 将节点值加入当前层列表

                # 将子节点加入队列
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)

            # 根据方向决定是否反转当前层的列表
            if direction == -1:
                current_level = current_level[::-1]  # 反转列表
            result.append(current_level)  # 将当前层加入结果集

            direction *= -1  # 切换方向

        return result

时空复杂度

时间复杂度：O(n)，其中 n 是二叉树的节点数。每个节点仅被访问一次。
空间复杂度：O(n)，队列中最多存储一层的节点数，最坏情况下为 n/2。

易错点

方向切换：每遍历完一层后需要切换遍历方向，容易忘记更新 direction。
反转操作：判断是否需要反转当前层的节点值时，容易出错。
空树处理：需要单独处理根节点为空的情况。

方法2：DFS + 递归

核心思路

使用 DFS（深度优先搜索） 进行遍历。
递归时记录当前节点的层数，并根据层数决定是否需要反转当前层的节点值。
优点：不需要显式维护队列，代码更简洁。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution:
    def zigzagLevelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []  # 存储最终结果

        def dfs(node, level):
            if not node:
                return

            # 如果当前层的列表还没有创建，则创建一个空列表
            if len(result) <= level:
                result.append([])

            # 根据层数的奇偶性决定插入方式
            if level % 2 == 0:
                result[level].append(node.val)  # 从左到右插入
            else:
                result[level].insert(0, node.val)  # 从右到左插入

            # 递归遍历子节点
            dfs(node.left, level + 1)
            dfs(node.right, level + 1)

        dfs(root, 0)  # 从根节点开始递归
        return result

时空复杂度

时间复杂度：O(n)，每个节点仅被访问一次。
空间复杂度：O(h)，其中 h 是树的深度，递归调用栈的深度为 h。最坏情况下为 O(n)。

易错点

层数计算：递归时需要正确传递当前层数，否则会插入到错误的层中。
插入方式：需要根据层数的奇偶性决定是从左到右插入还是从右到左插入。
空树处理：递归函数中需要处理节点为空的情况，否则会报错。

方法1 vs 方法2

方法	优点	缺点
BFS + 队列	直观，易于理解和实现	需要显式维护队列，代码稍长
DFS + 递归	代码简洁，无需维护队列	递归调用栈可能导致栈溢出

反转链表 II

92. 反转链表 II

题目描述

给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

方法1：迭代法

核心思路

定位反转区间：找到反转区间的第一个，以及前一个
袁师傅翻转法：cur->nxt->pre 滚键盘

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution:
    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        # 创建虚拟头节点，简化边界条件处理
        dummy = ListNode(next=head)
        # 初始化 pre 和 cur 指针
        pre, cur = dummy, head 
      
        # 移动 pre 和 cur 到正确的位置，pre 指向第 left-1 个节点，cur 指向第 left 个节点
        for _ in range(left-1):
            pre, cur = pre.next, cur.next
      
        # 反转从 left 到 right 的部分
        for _ in range(right-left):
            nxt = cur.next          # 保存 cur 的下一个节点
            cur.next = nxt.next     # 将 cur 的 next 指向 nxt 的下一个节点
            nxt.next = pre.next     # 将 nxt 的 next 指向 pre 的下一个节点
            pre.next = nxt          # 将 pre 的 next 指向 nxt
      
        # 返回反转后的链表头节点
        return dummy.next

时间复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表两次，第一次找到反转区间，第二次进行反转操作。
空间复杂度：O(1)，只使用了常数个额外的指针。

方法2：递归法

核心思路

超牛的递归函数：第一个是终止条件是tail，第二个是head.next=tail
头会断，尾不含：reverse函数会帮我们把tail调整好，但是head是断头，因此我们需要把慢指针放到left的前一个。 另外tail是不包含在内的，所以需要在定位的时候把实际反转的尾部再往后一个，也就是把快指针放到right的后一个。
请注意head_pre.next = self.reverse(head_pre.next, tail)

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def reverse(self, head, tail):
        if head == tail or head.next == tail:
            return head 
        p = self.reverse(head.next, tail)
        head.next.next = head 
        head.next = tail 
        return p 

    def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
        dummy = ListNode(next=head)
        head_pre, tail = dummy, dummy
        for _ in range(left - 1):
            head_pre = head_pre.next 
        for _ in range(right + 1):
            tail = tail.next 
        #进行翻转
        head_pre.next = self.reverse(head_pre.next, tail)
        return dummy.next

时间复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。递归反转操作的时间复杂度是 O(n)。
空间复杂度：O(n)，递归调用栈的深度可能达到 n。

易错点

递归终止条件：tail是很容易错的一点
left, right, head, tail：这四个指针太容易错了

合并K个升序链表

23. 合并K个升序链表

题目描述

给你一个链表数组，每个链表都已经按升序排列。请你将所有链表合并到一个升序链表中，返回合并后的链表。

方法一：分治法

核心思路

分治法：将K个链表分成两半，递归地合并这两半，直到只剩下一个链表为止。
合并两个链表：使用双指针法合并两个有序链表。

代码实现

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


class Solution:
    def merge2Lists(self, l1, l2):
        """
        合并两个有序链表
        :param l1: 第一个链表的头节点
        :param l2: 第二个链表的头节点
        :return: 合并后的链表的头节点
        """
        dummy = ListNode()  # 创建一个虚拟头节点
        curr = dummy  # curr用于遍历合并后的链表
        while l1 and l2:
            # 比较两个链表当前节点的值，将较小的节点连接到curr后面
            if l1.val < l2.val:
                curr.next = l1 
                l1 = l1.next 
            else:
                curr.next = l2 
                l2 = l2.next 
            curr = curr.next 
        # 如果其中一个链表还有剩余节点，直接连接到curr后面
        if l1:
            curr.next = l1 
        if l2:
            curr.next = l2 
        return dummy.next

    def mergeKLists(self, lists):
        """
        合并K个有序链表
        :param lists: 链表数组
        :return: 合并后的链表的头节点
        """
        match len(lists):
            case 0:
                return None  # 如果链表数组为空，返回None
            case 1:
                return lists[0]  # 如果只有一个链表，直接返回
            case 2:
                # 如果有两个链表，调用merge2Lists合并
                return self.merge2Lists(lists[0], lists[1])
            case _:
                # 如果有多个链表，递归地分成两半进行合并
                half = len(lists) // 2
                l1 = self.mergeKLists(lists[:half])  # 合并前半部分
                l2 = self.mergeKLists(lists[half:])  # 合并后半部分
                return self.merge2Lists(l1, l2)  # 合并前后两部分

分治法易错点

在数量为0/1/2的时候都要有返回值

方法二：最小堆

核心思路

最小堆：将每个链表的头节点放入最小堆中，每次从堆中取出最小的节点，将其连接到结果链表中，并将其下一个节点放入堆中。
堆的维护：确保堆中始终有链表中最小的节点。

代码实现

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118


class Heap:
    def __init__(self, seq):
        """
        初始化最小堆
        :param seq: 初始节点列表
        """
        self.heap = seq
        # 从数组的中间位置开始，自下而上进行heapify_down
        for i in range(len(seq)//2, -1, -1):
            self.heapify_down(i)
  
    def parent(self, i):
        """
        获取节点i的父节点索引
        :param i: 当前节点的索引
        :return: 父节点的索引
        """
        return (i-1)//2 if i else i 

    def son_left(self, i):
        """
        获取节点i的左子节点索引
        :param i: 当前节点的索引
        :return: 左子节点的索引
        """
        return 2*i+1
  
    def son_right(self, i):
        """
        获取节点i的右子节点索引
        :param i: 当前节点的索引
        :return: 右子节点的索引
        """
        return 2*i+2

    def swap(self, i, j):
        """
        交换堆中的两个节点
        :param i: 第一个节点的索引
        :param j: 第二个节点的索引
        """
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def heapify_up(self, i):
        """
        从节点i开始向上调整堆
        :param i: 当前节点的索引
        """
        p = self.parent(i)
        # 如果当前节点比父节点小，交换并继续向上调整
        if i and self.heap[i].val < self.heap[p].val:
            self.swap(i, p)
            self.heapify_up(p)

    def heapify_down(self, i):
        """
        从节点i开始向下调整堆
        :param i: 当前节点的索引
        """
        n = len(self.heap)
        l, r = self.son_left(i), self.son_right(i)
        idx = i 
        # 找到当前节点、左子节点和右子节点中最小的节点
        if l < n and self.heap[idx].val > self.heap[l].val:
            idx = l 
        if r < n and self.heap[idx].val > self.heap[r].val:
            idx = r 
        # 如果最小的节点不是当前节点，交换并继续向下调整
        if idx != i:
            self.swap(idx, i)
            self.heapify_down(idx)

    def push(self, node):
        """
        将节点加入堆
        :param node: 要加入的节点
        """
        self.heap.append(node)
        self.heapify_up(len(self.heap)-1)

    def empty(self):
        """
        判断堆是否为空
        :return: 堆是否为空
        """
        return len(self.heap) == 0

    def pop(self):
        """
        取出堆顶节点（最小值）
        :return: 堆顶节点
        """
        self.swap(0, len(self.heap)-1)  # 将堆顶节点与最后一个节点交换
        node = self.heap[-1]  # 取出最后一个节点（即最小值）
        self.heap.pop()  # 移除最后一个节点
        self.heapify_down(0)  # 从堆顶开始向下调整堆
        if node.next:
            self.push(node.next)  # 如果该节点有下一个节点，将该节点加入堆
        return node 

class Solution:
    def mergeKLists(self, lists) -> Optional[ListNode]:
        """
        合并K个有序链表
        :param lists: 链表数组
        :return: 合并后的链表的头节点
        """
        seq = []
        for node in lists:
            if node:
                seq.append(node)
        heap = Heap(seq=seq)
        dummy = ListNode()
        curr = dummy
        while not heap.empty():
            curr.next = heap.pop()
            curr = curr.next 
        return dummy.next

最小堆易错点

建堆：折半且逆序：for i in range(len(seq)//2, -1, -1):，这样做可以让时间复杂度变成O(n)，而如果挨个建堆则是O(nlogn)
父节点计算：减一后除二：return (i-1)//2 if i else i
下沉操作中注意边界：在堆下沉过程中需要考虑两个子节点的坐标是否在边界内，if l < n and self.heap[idx].val > self.heap[l].val
弹出操作中记得下沉和返回：
- 弹出操作时做了一步交换的，弹出以后应当立即下沉，而不是等到新元素入堆以后再去下沉
- self.swap(0, len(self.heap)-1) # 将堆顶节点与最后一个节点交换 node = self.heap[-1] # 取出最后一个节点（即最小值） self.heap.pop() # 移除最后一个节点 self.heapify_down(0) # 从堆顶开始向下调整堆
- 然后弹出操作需要一个返回值的
只有非空才能入队：if node: seq.append(node)
非必要不要这样写！！！

螺旋矩阵

54. 螺旋矩阵

题目描述

给定一个 m x n 的矩阵，按照顺时针螺旋顺序返回矩阵中的所有元素。

核心思路

这道题的核心思路是模拟螺旋遍历的过程。我们可以通过定义四个方向的移动顺序（右、下、左、上），并在遍历过程中根据边界条件和已访问过的元素来改变方向。

代码详解

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 如果矩阵为空，直接返回空列表
        if not matrix:
            return []
      
        # 定义四个方向的移动顺序：右、下、左、上
        dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        # 初始化起始位置和方向
        i, j, d = 0, 0, 0
        # 用于存储结果的列表
        res = []
        # 用来标记已访问过的元素，可以设定为一个特殊值（如999）
        used = 999
      
        # 总共需要遍历的元素的个数是矩阵的行数乘以列数
        for _ in range(len(matrix) * len(matrix[0])):
            # 如果当前位置的元素未被访问过，则将其加入结果列表，并标记为已访问
            if matrix[i][j] != used:
                res.append(matrix[i][j])
                matrix[i][j] = used
            # 计算下一个位置的坐标
            x, y = i + dir[d][0], j + dir[d][1]
            # 如果下一个位置超出矩阵边界或者已经访问过，则改变方向
            if x < 0 or y < 0 or x == len(matrix) or y == len(matrix[0]) or matrix[x][y] == used:
                d = (d + 1) % 4  # 改变方向
            # 更新当前位置
            i, j = i + dir[d][0], j + dir[d][1]
      
        # 返回结果列表
        return res

时空复杂度分析

时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要遍历矩阵中的每个元素一次。
空间复杂度：O(1)，除了存储结果的列表外，我们只使用了常数级别的额外空间（如方向数组和变量）。

易错点

边界条件：在判断下一个位置是否超出矩阵边界时，要注意 x 和 y 的取值是否在 [0, len(matrix) - 1] 和 [0, len(matrix[0]) - 1] 之间。
方向切换：当遇到边界或已访问过的元素时，需要正确地切换方向，否则会导致无限循环或错过某些元素。
已访问标记：在标记已访问的元素时，确保使用的特殊值（如 999）不会与矩阵中的实际元素冲突。

方法2：按层模拟

另一种思路是按层模拟，即从外向内逐层遍历矩阵。这种方法虽然思路不同，但时间复杂度与上述方法相同，都是 O(m * n)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix:
            return []
      
        res = []
        left, right = 0, len(matrix[0]) - 1
        top, bottom = 0, len(matrix) - 1
      
        while left <= right and top <= bottom:
            # 从左到右遍历上层
            for i in range(left, right + 1):
                res.append(matrix[top][i])
            top += 1
          
            # 从上到下遍历右层
            for i in range(top, bottom + 1):
                res.append(matrix[i][right])
            right -= 1
          
            if top <= bottom:
                # 从右到左遍历下层
                for i in range(right, left - 1, -1):
                    res.append(matrix[bottom][i])
                bottom -= 1
          
            if left <= right:
                # 从下到上遍历左层
                for i in range(bottom, top - 1, -1):
                    res.append(matrix[i][left])
                left += 1
      
        return res

时空复杂度分析

时间复杂度：O(m * n)，其中 m 是矩阵的行数，n 是矩阵的列数。我们需要遍历矩阵中的每个元素一次。
空间复杂度：O(1)，除了存储结果的列表外，我们只使用了常数级别的额外空间（如方向数组和变量）。

对比分析

按层模拟：思路更加直观，直接从外向内逐层遍历，代码结构清晰。
方向模拟：通过方向数组来控制移动方向，代码较为简洁，但需要对方向切换有较好的理解。

最长上升子序列

300. 最长递增子序列

题目描述

给你一个整数数组 nums ，找到其中最长严格递增子序列的长度。

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

方案一：动态规划（DP）

核心思路

子问题定义：
- 定义 dp[i] 为以 nums[i] 结尾的最长递增子序列的长度。
状态转移方程：
- 对于每个 i，遍历所有 j < i，如果 nums[i] > nums[j]，那么 dp[i] 可以更新为 max(dp[i], dp[j] + 1)。
最终结果：
- 最终的结果是 dp 数组中的最大值。

代码实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # 初始化 dp 数组，每个元素的最长递增子序列长度至少为 1（即自身）
        dp = [1] * len(nums)
      
        # 遍历数组中的每个元素
        for i in range(len(nums)):
            # 遍历该元素之前的所有元素
            for j in range(i):
                # 如果当前元素大于之前的某个元素，更新 dp[i]
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
      
        # 返回 dp 数组中的最大值，即为最长递增子序列的长度
        return max(dp)

时间复杂度：O(n^2)，遍历是O(n)，每一次遍历都要继续遍历O(n)
空间复杂度：维护一个dp数组，O(n)

时空复杂度

时间复杂度：O(n^2)，其中 n 是数组的长度。需要两层嵌套循环，外层循环遍历每个元素，内层循环遍历当前元素之前的所有元素。
空间复杂度：O(n)，需要一个长度为 n 的 dp 数组来存储中间结果。

易错点

初始化：dp 数组的每个元素应初始化为 1，因为每个元素自身至少可以构成一个长度为 1 的递增子序列。
状态转移：在更新 dp[i] 时，确保只有当 nums[i] > nums[j] 时才更新，否则会误判非递增的情况。
结果返回：dp 数组中的最大值才是最终结果，而不是 dp[-1]，因为最长递增子序列不一定以数组的最后一个元素结尾。

方案二：耐心排序+二分查找

核心思路

耐心排序指的是建立这样很多个堆，堆里面从大到小，新的元素依次遍历堆，找到堆顶比自己大或等于的第一个堆就放进去，如果没有则建立新堆
因为每一次都是遇到符合的堆就放进去，因此堆顶有序，我们用二分来找对应的堆
堆的数量就是最大子序列的长度
堆内部不严格单调，堆顶严格单调

代码实现

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


class Solution:
    def bisearch(top, target):
        """
        在 top 数组中查找第一个 >= target 的索引。
        如果 target 大于所有元素，则返回 len(top)。
        """
        l, r = 0, len(top)
        while l < r:
            m = (l + r) // 2
            if top[m] >= target:
                r = m 
            else:
                l = m + 1
        return l

    def lengthOfLIS(self, nums: List[int]) -> int:
        """
        返回 nums 的最长递增子序列的长度。
        """
        if not nums:
            return 0
        
        # top[i] 表示长度为 i+1 的递增子序列的最小末尾元素
        top = []
        for num in nums:
            # 找到 num 在 top 数组中的插入位置
            idx = self.bisearch(top, num)
            if idx == len(top):
                # 如果 num 大于所有元素，则扩展 top 数组
                top.append(num)
            else:
                # 否则，替换 top[idx] 为 num
                top[idx] = num
        return len(top)

时间复杂度：O(n log n)，遍历是O(n)，每一次遍历都要二分O(logn)
空间复杂度：维护一个堆顶数组，O(n)

理论依据 Dilworth 定理

Dilworth 定理指出，在偏序集中，最少的链划分等于最长的反链长度。
在序列中，最长上升子序列是一个最大的链，而最少的不下降子序列划分对应于最少的链划分。
因此，堆的个数等于最长上升子序列的长度。

易错点

二分右端点！！！
- 二分的区间是所有可能取值的区间，这道题里面，len(top)可以取到
- 取到len(top)的时候意味着没有符合要求的堆，就应该返回这个值
- 中点取左边的，所以top[m]不可能遍历到这个不存在的值
二分正确条件！！！
- 二分的正确条件是大于等于堆顶，而不是大于堆顶
- 我们考虑极端情况，八个八，这个时候如果是前者只有一堆，后者会有八个堆
别写了，我不信你哈哈

方案对比

方案	时间复杂度	空间复杂度	核心思路
动态规划	O(n^2)	O(n)	通过状态转移方程求解每个子问题
二分查找优化	O(n log n)	O(n)	维护一个 `top` 数组，使用二分查找优化

字符串相加

415. 字符串相加

题目描述

给定两个字符串形式的非负整数 num1 和num2 ，计算它们的和并同样以字符串形式返回。

你不能使用任何內建的用于处理大整数的库（比如 BigInteger），也不能直接将输入的字符串转换为整数形式。

方案：模拟即可

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def addStrings(self, num1: str, num2: str) -> str:
        i, j = len(num1), len(num2)
        num1, num2 = " " + num1, " " + num2
        res = ""
        carry = 0 
        while i or j or carry:
            carry += int(num1[i]) if i else 0
            carry += int(num2[j]) if j else 0
            carry, digit = divmod(carry, 10)
            res = str(digit) + res 
            i, j = max(0, i-1), max(0, j-1)
        return res

相交链表

160. 相交链表

题目描述

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

方案：两边都走一遍，交点处相遇

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13


class Solution:
    def getIntersectionNode(self, headA, headB) -> Optional[ListNode]:
        i, j = headA, headB
        a, b = False, False 
        while i and j :
            i, j = i.next, j.next 
            if not i and not a:
                i, a = headB, True 
            if not j and not b:
                j, b = headA, True 
            if i == j and a and b:
                return i 
        return None

重排链表

143. 重排链表

题目描述

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln - 1 → Ln

请将其重新排列后变为：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

方案：三位一体

这题我之前一直不理解，现在想来原来是三道题的合并

1
2
3
4


def reorderList(self, head: Optional[ListNode]) -> None:
    n1, n2 = self.splitList(head)
    n2 = self.reverseList(n2)
    self.mergeList(n1, n2)

组件1：递归法反转链表

第一个是反转链表的部分，这里最容易错的是return head，特别容易写成return None

1
2
3
4
5
6
7


def reverseList(self, head):
    if not head or not head.next:
        return head 
    p = self.reverseList(head.next)
    head.next.next = head 
    head.next = None 
    return p 

时间复杂度：O(n)，其中n是链表的长度。递归需要遍历链表的每个节点。
空间复杂度：O(n)，递归调用栈的深度为链表的长度。

组件2：双指针拆分链表

第二个是用双指针来拆分链表，这里最容易错的是中间的那个指针

要先记录它的下一个结点，那是新链表的头节点
然后要把它的下一个结点改成空
如果从head出发，奇数的时候停在正中心，偶数的时候停在中心靠左
如果从dummy出发，奇数的时候停在正中心，偶数的时候停在中心靠右

1
2
3
4
5
6
7
8


def splitList(self, head):
    slow, fast = head, head 
    while fast and fast.next:
        fast = fast.next.next 
        slow = slow.next 
    res = slow.next 
    slow.next = None
    return head, res 

时间复杂度：O(n)，其中n是链表的长度。快慢指针需要遍历链表的一半节点。
空间复杂度：O(1)，只使用了常数级别的额外空间。

组件3：遍历合并链表

第三个就是合并链表，这里因为两个链表长度相差不过1所以不用担心

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


def mergeList(self, n1, n2):
    dummy = ListNode()
    cur = dummy
    while n1 and n2:
        cur.next = n1 
        n1, cur = n1.next, cur.next 
        cur.next = n2 
        n2, cur = n2.next, cur.next
    if n1:
        cur.next = n1 
    if n2:
        cur.next = n2 

时间复杂度：O(n)，其中n是两个链表的长度之和。需要遍历两个链表的每个节点。
空间复杂度：O(1)，只使用了常数级别的额外空间。

易错点

递归法的终止条件，是return head
拆分链表的起始位置，是head，才能停在中心靠左
拆分链表以后要先记录、再断链、最后返回记录点

总复杂度

时间复杂度

reverseList：O(n)
splitList：O(n)
mergeList：O(n)

总时间复杂度为：O(n) + O(n) + O(n) = O(n)。

空间复杂度

reverseList：O(n)
splitList：O(1)
mergeList：O(1)

总空间复杂度为：O(n) + O(1) + O(1) = O(n)。

合并区间

56. 合并区间

题目描述

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

方案：利用lambda函数排序

先排序，然后每次用头去碰尾，碰不上就新加入，碰上了就更新尾巴

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x:(x[0], x[1]))
        res = []
        for i in intervals:
            if not res or i[0] > res[-1][1]:
                res.append(i)
            else:
                res[-1][1] = max(i[1], res[-1][1])
        return res

接雨水

42. 接雨水

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

方法一：线性扫描

扫描三次，每一次扫到的是从i这里看过去，左边最高的边和右边最高的边
如果没有就会返回自身高度，这样就会变成增量，不是非负的
每次看到左右最低的那个最高值，和自己的差值就是此处的雨水

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


class Solution:
    def trap(self, height: List[int]) -> int:
        n, res = len(height), 0
        # 注意这个*n是在外面
        left, right = [0]*n, [0]*n
        # left是左侧见过最高的高度
        # right是右侧见过最高的高度
        left[0], right[n-1] = height[0], height[n-1]
        
        # 分别从左边和右边遍历
        for i in range(1, n):
            left[i] = max(left[i-1], height[i])
        for i in range(n-2, -1, -1):
            right[i] = max(right[i+1], height[i])
        # 因为带上了height[i]所以一定非负
        for i in range(n):
            res += min(left[i], right[i]) - height[i]
       
		return res

时间复杂度，扫描3次，O(n)
空间复杂度，存2个数组，O(n)

方法二：单调栈

扫描一次即可，维护一个值单调递减的栈，存的是里面的坐标
遇到不单调的值，就可以存下雨水，不断弹出坐标，每个坐标都能存下水

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution:
    def trap(self, h: List[int]) -> int:
        # 单调递减栈，存储柱子的索引
        stk = []
        # 用于存储最终接到的雨水量
        res = 0
        # 遍历数组中的每个柱子
        for r in range(len(h)):
            # 当栈不为空，且当前柱子的高度大于栈顶柱子的高度
            while stk and h[r] >= h[stk[-1]]:
                # 弹出栈顶元素，作为凹槽的底部
                b = stk.pop()
                # 如果栈为空，说明左边没有更高的柱子，无法接雨水，直接跳出循环
                if not stk:
                    break
                # 左边界是新的栈顶元素
                l = stk[-1]
                # 计算雨水量
                # 高度差：min(h[l], h[r]) - h[b]，表示凹槽的深度
                # 宽度：r - l - 1，表示凹槽的宽度
                res += (min(h[l], h[r]) - h[b]) * (r - l - 1)
            # 将当前柱子的索引压入栈
            stk.append(r)
        # 返回最终接到的雨水量
        return res

时间复杂度，扫描1次，O(n)
空间复杂度，存1个数组，O(n)

线性扫描易错点

left, right = [0]*n, [0]*n
left[i] = max(left[i-1], height[i])

单调栈易错点

维护一个单调递减的栈，而后遍历右侧壁
while stk and h[r] >= h[stk[-1]]，弹出池底坐标，此时栈顶为左壁坐标
如果弹出池底后栈空，放弃
栈的单调性是高度递减，栈内存的是坐标