LeetCode Notes

算法随想录

数组

704. 二分查找

区间一般可以定义为两种：左闭右闭 [left, right]，或者左闭右开 [left, right]。

这里采用左闭右闭进行代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def search(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        left = 0
        right = len(nums) - 1
        while left <= right:
            middle = (left + right) // 2
            if nums[middle] > target:
                right = middle - 1
            elif nums[middle] < target:
                left = middle + 1
            else:
                return middle
        return -1

27. 移除元素

双指针法：通过一个快指针和一个慢指针在一个 for 循环下完成两个 for 循环的工作。

  • 快指针：寻找新数组的元素，新数组就是不含有目标元素的数组
  • 慢指针：指向更新新数组下标的位置

这里不采用暴力解法，使用双指针实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        slow = 0
        fast = 0
        size = len(nums)
        while fast < size:
            # slow 用来收集不等于 val 的值，如果 fast 对应值不等于 val，则把它与 slow 替换
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            fast+= 1
        return slow

977. 有序数组的平方

数组是有序的，但负数平方之后可能成为最大数了。所以最大值不是在最左边就是在最右边，不可能是中间。

可以考虑双指针法，left指向最左边，right 指向最右边。

定义一个新的数组，和 A 数组一样大小，让 k 指向 res 数组终止位置。

如果 A[left] * A[left] < A[right] * A[right]，那么 res[k–] = A[right] * A[right]

如果 A[left] * A[left] >= A[right] * A[right]，那么 res[k–] = A[left] * A[left]

以下是代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def sortedSquares(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        left = 0
        right = len(nums) - 1
        k = len(nums) - 1
        res = [float('inf')] * len(nums)

        while left <= right:
            if nums[left] ** 2 > nums[right] ** 2:
                res[k] = nums[left] ** 2
                left += 1
            else:
                res[k] = nums[right] ** 2
                right -= 1
            k -= 1
        return res

209. 长度最小的子数组

不断的调节子序列的起始位置和终止位置

  • 窗口内是什么？
  • 如何移动窗口的起始位置？
  • 如何移动窗口的结束位置？

窗口：满足其和 >= target 的长度最小的连续数组

起始位置如何移动：如果当前窗口的值大于等于 target 了，窗口就要向前移动了（也就是该缩小了）。

结束位置如何移动：窗口的结束位置就是遍历数组的指针，也就是 for 循环里的索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def minSubArrayLen(self, target, nums):
        """
        :type target: int
        :type nums: List[int]
        :rtype: int
        """
        l = len(nums)
        res = 999999
        start = 0
        end = 0
        total = 0
        while end < l:
            total += nums[end]
            while total >= target:
                res = min(res, end - start + 1)
                total -= nums[start]
                start += 1
            end += 1
        return 0 if res == 999999 else res

59. 螺旋矩阵

初始化一个 n * n 大小的矩阵 matrix，然后模拟整个内向环绕的填入过程。

模拟顺时针画矩阵的过程

  • 填充上行从左到右
  • 填充右列从上到下
  • 填充下行从右到左
  • 填充左列从下到上
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution(object):
    def generateMatrix(self, n):
        """
        :type n: int
        :rtype: List[List[int]]
        """
        # 定义当前左右上下边界，初始值 num = 1，迭代终止值 target = n * n
        l, r, t, b = 0, n - 1, 0 , n - 1
        matrix = [[0] * n for _ in range(n)]
        num, target = 1, n * n
        
        # 使用 num <= target 而不是 l < r || t < b 作为迭代条件，是为了解决 n 为奇数时，矩阵中心数字无法在迭代过程中被填充的问题
        while num <= target:
            for i in range(l, r + 1):
                matrix[t][i] = num
                num += 1
            t += 1
            for i in range(t, b + 1):
                matrix[i][r] = num
                num += 1
            r -= 1
            for i in range(r, l - 1, -1):
                matrix[b][i] = num
                num += 1
            b -= 1
            for i in range(b, t - 1, -1):
                matrix[i][l] = num
                num += 1
            l += 1
        return matrix

链表

203. 移除链表元素

链表操作两种方式：

  • 直接使用原来的链表来进行删除操作
  • 设置一个虚拟头节点在进行删除操作

推荐设置虚拟头节点，这样原链表的所有节点就都可以按照统一的方式进行移除了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeElements(self, head, val):
        """
        :type head: Optional[ListNode]
        :type val: int
        :rtype: Optional[ListNode]
        """
        current = dummy_head = ListNode(next = head)
        while current.next:
            if current.next.val == val:
                current.next = current.next.next
            else:
                current = current.next
        return dummy_head.next

707. 设计链表

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
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class MyLinkedList(object):

    def __init__(self):
        self.dummy_head = ListNode()
        self.size = 0

    def get(self, index):
        """
        :type index: int
        :rtype: int
        """
        if index < 0 or index >= self.size:
            return -1
        
        current = self.dummy_head.next
        for i in range(index):
            current = current.next
        
        return current.val

    def addAtHead(self, val):
        """
        :type val: int
        :rtype: None
        """
        self.dummy_head.next = ListNode(val, self.dummy_head.next)
        self.size += 1

    def addAtTail(self, val):
        """
        :type val: int
        :rtype: None
        """
        current = self.dummy_head
        while current.next:
            current = current.next
        current.next = ListNode(val)
        self.size += 1
        

    def addAtIndex(self, index, val):
        """
        :type index: int
        :type val: int
        :rtype: None
        """
        if index < 0 or index > self.size:
            return
        
        current = self.dummy_head
        for i in range(index):
            current = current.next
        current.next = ListNode(val, current.next)
        self.size += 1
        
    def deleteAtIndex(self, index):
        """
        :type index: int
        :rtype: None
        """
        if index < 0 or index >= self.size:
            return
        
        current = self.dummy_head
        for i in range(index):
            current = current.next
        
        current.next = current.next.next
        self.size -= 1
        


# Your MyLinkedList object will be instantiated and called as such:
# obj = MyLinkedList()
# param_1 = obj.get(index)
# obj.addAtHead(val)
# obj.addAtTail(val)
# obj.addAtIndex(index,val)
# obj.deleteAtIndex(index)

206. 反转链表

本题采用双指针写法：

首先定义一个 current 指针，指向头节点， 再定义一个 previous 指针，初始化 null。

然后开始反转，首先把 current -> next 节点用 temp 指针保存一下，接下来将 current -> next 指向 previous，此时已经反转了第一个节点了。

接下来循环，继续移动 previous 和 current 指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reverseList(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        current, previous = head, None
        while current:
            temp = current.next     # 暂存后继节点 cur.next
            current.next = previous # 修改 next 引用指向
            previous = current      # pre 暂存 cur
            current = temp          # cur 访问下一节点
        return previous

24. 两两交换链表中的节点

建议使用虚拟头节点，这样会方便很多，接下来就是交换相邻两个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def swapPairs(self, head):
        """
        :type head: Optional[ListNode]
        :rtype: Optional[ListNode]
        """
        dummy_head = ListNode(next=head)
        current = dummy_head

        while current.next and current.next.next:
            temp1 = current.next
            temp2 = current.next.next.next

            current.next = current.next.next
            current.next.next = temp1
            temp1.next = temp2
            current = current.next.next
        return dummy_head.next

19. 删除链表的倒数第 N 个节点

采用双指针，如果要删除倒数第 n 个节点，让 fast 移动 n 步。然后让 fast 和 slow 同时移动，直到 fast 指向链表末尾。删掉 slow 所指向的节点就可以。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def removeNthFromEnd(self, head, n):
        """
        :type head: Optional[ListNode]
        :type n: int
        :rtype: Optional[ListNode]
        """
        # 创建一个虚拟节点，并将其下一个指针设置为链表的头部
        dummy_head = ListNode(0, head)

        # 创建两个指针，慢指针和快指针，并将它们初始化为虚拟节点
        slow = fast = dummy_head

        # 快指针比慢指针快 n + 1 步
        for i in range(n + 1):
            fast = fast.next

        while fast:
            fast = fast.next
            slow = slow.next

        # 通过更新第 (n - 1) 节点的 next 指针删除第 n 个节点
        slow.next = slow.next.next

        return dummy_head.next

142. 环形链表Ⅱ

主要考察两知识点：

  • 判断链表是否有环
  • 如果有环，如何找到这个环的入口

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头节点出发，fast 指针每次移动两个节点，slow 指针每次移动一个节点，如果 fast 指针和 slow 指针在途中相遇，说明这个链表有环。

假设从头节点到环形入口节点的节点数为 x，环形入口节点到 fast 指针与 slow 指针相遇节点节点数为 y，从相遇节点再到环形入口节点数为 z。

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
# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def detectCycle(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        slow = head
        fast = head

        while fast and fast.next:
            fast = fast.next.next
            slow = slow.next
            if fast == slow:
                index1 = fast
                index2 = head
                while index1 != index2:
                    index1 = index1.next
                    index2 = index2.next
                return index1
        return None

哈希表

242. 有效的字母异位词

字符 a 到字符 z 的 ASCII 是 26 个连续的数值，所以字符 a 映射为下标 0，相应的字符 z 映射为下标 25。

record 数组中如果有的元素不为 0，说明字符串 s 和 t 一定是谁多了字符或谁少了字符，return False。

如果 record 数组所有元素都为 0，说明字符串 s 和 t 是字母异位词，return True。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def isAnagram(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        record = [0] * 26
        for i in s:
            # ord()函数的主要功能是将单个字符转换为其对应的Unicode码点
            record[ord(i) - ord("a")] += 1
        for i in t:
            record[ord(i) - ord("a")] -= 1
        
        for i in range(26):
            if(record[i] != 0):
                return False
        return True

349. 两个数组的交集

输出结果中的每个元素一定是唯一的，也就是说输出的结果是去重的，同时可以不考虑输出结果的顺序。

使用集合方式:

1
2
3
4
5
6
7
8
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        return list(set(nums1) & set(nums2))

使用数组方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def intersection(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        record = [0] * 1001
        result = []

        for i in nums1:
            record[i] = 1

        for i in nums2:
            if(record[i] == 1):
                result.append(i)
                record[i] = 0
                
        return result

1. 两数之和

此题采用 map 映射方法

map 的目的用来存放访问过的元素，因为遍历数组的时候，需要记录之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的。

map 中的存储结构为 {key：数据元素，value：数组元素对应的下标}

在遍历数组的时候，只需要向 map 去查询是否有和目前遍历数组元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进 map 中，因为 map 存放的就是访问过的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        record = dict()

        for index, value in enumerate(nums):
            if target - value in record:
                return [record[target - value], index]
            record[value] = index
        return []

454. 四数相加Ⅱ

四个独立的数组，只要找到 A[i] + B[j] + C[k] + D[i] = 0 就可以，不用考虑有重复的四个元素相加等于 0 的情况。

  1. 首先定义一个字典，key 存放 num1 和 num2 两数之和，value 存放 num1 和 num2 两数之和出现的次数
  2. 遍历 num1 和 num2 数组，统计两个数组元素之和，和出现的次数，放到 map 中
  3. 定义变量 count，用来统计 num1 + num2 + num3 + num4 = 0 出现的次数
  4. 再遍历 num3 和 num4 数组，找到如果 0 - (num3 + num4) 在 map 中出现过的话，就用 count 把 map 中 key 对应的 value 也就是统计次数统计出来
  5. 最后返回统计值 count
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
class Solution(object):
    def fourSumCount(self, nums1, nums2, nums3, nums4):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :type nums3: List[int]
        :type nums4: List[int]
        :rtype: int
        """
        # 使用字典存储nums1和nums2中的元素及其和
        hashmap = dict()

        for n1 in nums1:
            for n2 in nums2:
                if n1 + n2 in hashmap:
                    hashmap[n1 + n2] += 1
                else:
                    hashmap[n1 + n2] = 1

        count = 0
        for n3 in nums3:
            for n4 in nums4:
                # 0 - (c + d) = a + b
                target = 0 - (n3 + n4)
                if target in hashmap:
                    count += hashmap[target]

        return count

15. 三数之和

使用哈希法并不十分合适，因为在去重的操作中有很多细节需要注意。

采用双指针法，比哈希法高效一些

首先将数组排序，然后有一层 for 循环，i 从下标 0 的地方开始，同时定义一个下标 left 定义在 i + 1 的位置上，定义下标 right 在数组结尾的位置上。

在数组中找到 abc 使得 a + b + c = 0，这里相当于 a = nums[i]，b = nums[left]，c = nums[right]。

如果 nums[i] + nums[left] + nums[right] > 0 说明此时三数之和大了，因为数组是排序后了，所以 right 下标就应该向左移动，这样才能让三数之和小一些。

如果 nums[i] + nums[left] + nums[right] < 0 说明此时三数之和小了，left 就向右移动，才能让三数之和大一些，直到 left 与 right 相遇为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        
        for i in range(len(nums)):
            # 如果当前数字大于0，后面的数字也都大于0，不可能找到和为0的三元组
            if nums[i] > 0:
                break

            # 跳过相同的元素以避免重复
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            left = i + 1
            right = len(nums) - 1

            while right > left:
                total = nums[i] + nums[left] + nums[right]
                
                if total > 0:
                    right -= 1
                elif total < 0:
                    left += 1
                else:
                    # 将三元组加入结果
                    result.append([nums[i], nums[left], nums[right]])

                    # 跳过相同的元素以避免重复
                    while right > left and nums[right] == nums[right - 1]:
                        right -= 1
                    while right > left and nums[left] == nums[left + 1]:
                        left += 1

                    right -= 1
                    left += 1

        return result

18. 四数之和

基本解法就是在三数之和的基础上再套一层 for 循环。

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
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        result = []
        nums.sort()
        n = len(nums)

        for i in range(n):
            if nums[i] > target and nums[i] > 0 and target > 0:
                break
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            
            for j in range(i + 1, n):
                if nums[i] + nums[j] > target and target > 0:
                    break
                if j > i + 1 and nums[j] == nums[j - 1]:
                    continue
                left, right = j + 1, n - 1

                while left < right:
                    total = nums[i] + nums[j] + nums[left] + nums[right]
                    if total == target:
                        result.append([nums[i], nums[j], nums[left], nums[right]])
                    
                        while left < right and nums[left] == nums[left + 1]:
                            left += 1
                        while left < right and nums[right] == nums[right - 1]:
                            right -= 1

                        left += 1
                        right -= 1
                    
                    elif total < target:
                        left += 1
                    else:
                        right -= 1
        return result

字符串

344. 反转字符串

采用双指针方法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
    def reverseString(self, s):
        """
        :type s: List[str]
        :rtype: None Do not return anything, modify s in-place instead.
        """
        left = 0
        right = len(s) - 1

        while left < right:
            s[left], s[right] = s[right], s[left]
            left += 1
            right -= 1

541. 反转字符串Ⅱ

在遍历字符串的过程中，只要让 i += (2 * k)，i 每次移动 2 * k 就可以了，然后判断是否需要有反转的区间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def reverseStr(self, s, k):
        """
        :type s: str
        :type k: int
        :rtype: str
        """
        def reverse_substring(text):
            left = 0
            right = len(text) - 1
            while left < right:
                text[left], text[right] = text[right], text[left]
                left += 1
                right -= 1
            return text
        
        result = list(s)

        for i in range(0, len(s), 2 * k):
            result[i: i + k] = reverse_substring(result[i: i + k])

        return ''.join(result)

151. 反转字符串中的单词

采用双指针方法

解题思路：

  • 移除多余空格
  • 将整个字符串反转
  • 将每个单词反转
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def reverseWords(self, s):
        """
        :type s: str
        :rtype: str
        """
        # 将字符串拆分为单词，即转换成列表类型
        words = s.split()

        left, right = 0, len(words) - 1
        while left < right:
            words[left], words[right] = words[right], words[left]
            left += 1
            right -= 1

        # 将列表转换为字符串
        return ' '.join(words)

栈与队列

232. 用栈实现队列

需要两个栈，一个输入栈，一个输出栈

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false
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
class MyQueue(object):

    def __init__(self):
        # in 主要负责 push，out主要负责 pop
        self.stack_in = []
        self.stack_out = []

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        # 有新元素进来，就往 in 里面 push
        self.stack_in.append(x)
        

    def pop(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        
        if self.stack_out:
            return self.stack_out.pop()
        else:
            for i in range(len(self.stack_in)):
                self.stack_out.append(self.stack_in.pop())
            return self.stack_out.pop()

    def peek(self):
        """
        :rtype: int
        """
        ans = self.pop()
        self.stack_out.append(ans)
        return ans
        

    def empty(self):
        """
        :rtype: bool
        """
        # 只要 in 或者 out 有元素，说明队列不为空
        return not (self.stack_in or self.stack_out)
        
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()

225. 用队列实现栈

队列模拟栈，一个队列就够了。

队列是先进先出的规则，把一个队列中的数据导入另一个队列中，数据的顺序并没有变，并没有变成先进后出的规则。

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
class MyStack(object):

    def __init__(self):
        # deque 双端队列，支持从两端快速添加和删除元素
        self.queue = deque()
    
    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        self.queue.append(x)
        
    def pop(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        for i in range(len(self.queue) - 1):
            # popleft() 方法用于从队列的左侧（开头）删除元素，并返回被删除的元素。
            self.queue.append(self.queue.popleft())
        return self.queue.popleft()
        
    def top(self):
        """
        :rtype: int
        """
        if self.empty():
            return None
        for i in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
        ans = self.queue.popleft()
        self.queue.append(ans)
        return ans

    def empty(self):
        """
        :rtype: bool
        """
        return not self.queue

# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()

20. 有效的括号

第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以 return false

第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以 return false

第三章情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false

当字符串全部遍历完之后，栈是空的，说明全部匹配了。

还有一些技巧，右括号先入栈，就只需要比较当前元素和栈顶相不相等就可以了，比左括号先入栈实现要简单很多。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        stack = []

        for item in s:
            if item == '(':
                stack.append(')')
            elif item == '[':
                stack.append(']')
            elif item == '{':
                stack.append('}')
            elif not stack or stack[-1] != item:
                return False
            else:
                stack.pop()

        return True if not stack else False

1047. 删除字符串中的所有相邻重复项

使用栈来解决

在删除相邻重复项的时候，应该知道当前遍历的这个元素，在前一位是不是遍历过一样数值的元素。

栈的目的就是存放遍历过的元素，当遍历当前的这个元素时，去栈里看看是不是遍历过相同数值的相邻元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def removeDuplicates(self, s):
        """
        :type s: str
        :rtype: str
        """
        res = list()

        for item in s:
            if res and res[-1] == item:
                res.pop()
            else:
                res.append(item)

        # 字符串拼接
        return "".join(res)

150. 逆波兰表达式求值

栈与递归之间在某种程度上是可以相互转换的。

逆波兰表达式相当于是二叉树中的后序遍历。

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(object):
    def evalRPN(self, tokens):
        """
        :type tokens: List[str]
        :rtype: int
        """
        stack = []
        for token in tokens:
            try:
                stack.append(int(token))
            except:
                num2 = stack.pop()
                num1 = stack.pop()
                stack.append(self.calculate(num1, num2, token))
        return stack[0]

    def calculate(self, num1, num2, op):
        if op == "+":
            return num1 + num2
        elif op == "-":
            return num1 - num2
        elif op == "*":
            return num1 * num2
        elif op == "/":
            return int(num1 / float(num2))

239. 滑动窗口最大值

使用单调队列

队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。

设计单调队列的时候，pop 和 push 操作要保持如下规则：

  1. pop（value）：如果窗口移除的元素 value 等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作。
  2. push（value）：如果 push 的元素 value 大于入口元素的数值，那么就将队列入口的元素弹出，直到 push 元素的数值小于等于队列入口元素的数值为止。

本题采用双端队列实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        res = []
        queue = collections.deque()  # 双端队列
        for i, num in enumerate(nums):
            # 如果队列最左侧索引已不在滑动窗口范围内，弹出队列最左侧索引
            if queue and queue[0] == i - k:
                queue.popleft()
            while queue and nums[queue[-1]] < num:
                queue.pop()  # 维护 queue 的单调性
            queue.append(i)  # 入队
            if i >= k - 1:
                # 由于队首到队尾单调递减，所以窗口最大值就是队首
                res.append(nums[queue[0]])
        return res

347. 前 k个高频元素

  1. 要统计元素出现频率
  2. 对频率排序
  3. 找出前 K 个高频元素

首先统计元素出现的频率，这一类的问题可以使用 map 来进行统计。

然后是对频率进行排序，可以使用一种容器适配器就是优先级队列。

使用小顶堆，因为要统计最大前 k 个元素，只有小顶堆每次将最小的元素弹出，最后小顶堆里积累的才是前 k 个最大元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def topKFrequent(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        # 使用字典统计频率
        dictionary = collections.Counter(nums)
        heap, res = [],[]
        
        # 使用堆存储频率的负数来实现最大堆
        for i in dictionary:
            heapq.heappush(heap, (-dictionary[i], i))
            
        # 提取前 k 个频率最高的元素
        for _ in range(k):
            res.append(heapq.heappop(heap)[1])
        return res

二叉树

  1. 确定递归函数的参数和返回值：确定哪些参数是递归的过程中需要处理的，那么就在递归函数里加上这个参数，并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。
  2. 确定终止条件：写完了递归算法，运行时经常遇到栈溢出的错误，就是没写终止条件或者终止条件写的不对，操作系统也是用一个栈的结构来保存每一层递归的信息，如果递归没有终止，操作系统的内存栈必然就会溢出。
  3. 确定单层递归的逻辑：确定每一层递归需要处理的信息。

144. 二叉树的前序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        res = []

        def dfs(node):
            if node is None:
                return

            res.append(node.val)
            dfs(node.left)
            dfs(node.right)

        dfs(root)
        return res

145. 二叉树的后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        res = []

        def dfs(node):
            if node is None:
                return

            dfs(node.left)
            dfs(node.right)
            res.append(node.val)

        dfs(root)
        return res

94. 二叉树的中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def inorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        res = []

        def dfs(node):
            if node is None:
                return

            dfs(node.left)
            res.append(node.val)
            dfs(node.right)

        dfs(root)
        return res

144. 前序遍历（迭代遍历）

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def preorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        # 根节点为空则返回空列表
        if not root:
            return []

        stack = [root]
        res = []

        while stack:
            node = stack.pop()
            # 中结点先处理
            res.append(node.val)
            # 右孩子先入栈
            if node.right:
                stack.append(node.right)
            # 左孩子后入栈
            if node.left:
                stack.append(node.left)
        return res

145. 后序遍历（迭代遍历）

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def postorderTraversal(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        # 根节点为空则返回空列表
        if not root:
            return []

        stack = [root]
        res = []
        
        while stack:
            node = stack.pop()
            # 中结点先处理
            res.append(node.val)
            # 左孩子先入栈
            if node.left:
               stack.append(node.left)
            # 右孩子后入栈
            if node.right:
               stack.append(node.right)
        # 将最终的数组翻转
        return res[::-1]

102. 二叉树的层序遍历

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过应用在二叉树上。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def levelOrder(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[List[int]]
        """
        if not root:
            return []

        queue = [root]
        res = []
        while queue:
            level = []
            for _ in range(len(queue)):
                cur = queue.pop(0)
                level.append(cur.val)
                if cur.left:
                    queue.append(cur.left)
                if cur.right:
                    queue.append(cur.right)
            res.append(level)
        return res

226. 翻转二叉树

只要把每一个节点的左右孩子翻转一下，就可以达到整体翻转的效果。

使用前序遍历和后序遍历都可以，唯独中序遍历不方便，因为中序遍历会把某些节点的左右孩子翻转两次。

递归法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        # 递归函数的终止条件，节点为空时返回
        if not root:
            return 
        
        # 将当前节点的左右子树交换
        root.left, root.right = root.right, root.left
        # 递归交换当前节点的 左子树和右子树
        self.invertTree(root.left)
        self.invertTree(root.right)
        return root

迭代法实现

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def invertTree(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        if not root:
            return 
        # 将二叉树中的节点逐层放入栈中，再迭代处理队列中的元素
        stack = [root]
        while stack:
            # 每次都从栈中拿一个节点，并交换这个节点的左右子树
            node = stack.pop(0)
            node.left, node.right = node.right, node.left
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return root

101. 对称二叉树

判断对称二叉树要比较的是哪两个节点，不是左右节点。

对于二叉树是否对称，要比较的是根节点的左子树与右子树是不是相互翻转的。

将根节点的左子树记做 left，右子树记做 right。比较 left 是否等于 right，不等的话直接返回就可以了。

如果相当，比较 left 的左节点和 right 的右节点，再比较 left 的右节点和 right 的左节点。

递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        if not root:
            return
        
        def dfs(left, right):
            # 递归的终止条件是两个节点都为空
			# 或者两个节点中有一个为空
			# 或者两个节点的值不相等
            if not(left or right):
                return True
            if not(left and right):
                return False
            if left.val != right.val:
                return False
            return dfs(left.left, right.right) and dfs(left.right, right.left)
        return dfs(root.left, root.right)

迭代法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isSymmetric(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        if not root:
            return 
        
        stack = [root.left, root.right]
        while stack:
            # 从栈中取出两个节点，再比较这两个节点
            left = stack.pop(0)
            right = stack.pop(0)
            # 如果两个节点都为空就继续循环，两者有一个为空就返回false
            if not(left or right):
                continue
            if not(left and right):
                return False
            if left.val != right.val:
                return False
            # 将左节点的左孩子， 右节点的右孩子放入栈
            stack.append(left.left)
            stack.append(right.right)
            # 将左节点的右孩子，右节点的左孩子放入栈
            stack.append(left.right)
            stack.append(right.left)
        return True

104. 二叉树的最大深度

可以使用前序（中左右），也可以使用后序遍历（左右中），使用前序求的就是深度，使用后序求的是高度。

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从 0 开始还是从 1 开始）
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数或者节点数（取决于高度从 0 开始还是从 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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        return self.getDepth(root)
        
    def getDepth(self, node):
            if not node:
                return 0
            # 左
            leftHeight = self.getDepth(node.left)
            # 右
            rightHeight = self.getDepth(node.right)
            # 中
            height = 1 + max(leftHeight, rightHeight)
            return height

迭代法

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def maxDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if not root:
            return 0
        
        depth = 0
        queue = [root]

        while queue:
            depth += 1
            for _ in range(len(queue)):
                node = queue.pop(0)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return depth

111. 二叉树的最小深度

递归法

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def minDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        return self.getDepth(root)
        
    def getDepth(self, node):
        if node is None:
            return 0
        leftDepth = self.getDepth(node.left)
        rightDepth = self.getDepth(node.right)

        # 当一个左子树为空，右不为空，这时并不是最低点
        if node.left is None and node.right is not None:
            return 1 + rightDepth
        
        # 当一个右子树为空，左不为空，这时并不是最低点
        if node.left is not None and node.right is None:
            return 1 + leftDepth

        height = 1 + min(leftDepth, rightDepth)
        return height

迭代法

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def minDepth(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if not root:
            return 0

        depth = 0
        queue = [root]

        while queue:
            depth += 1
            for _ in range(len(queue)):
                node = queue.pop(0)

                if not node.left and not node.right:
                    return depth

                if node.left:
                    queue.append(node.left)

                if node.right:
                    queue.append(node.right)

        return depth

110. 平衡二叉树

概念：

  • 二叉树节点的深度：指从根节点到该节点的最长简单路径边的条数。
  • 二叉树节点的高度：指从该节点到叶子节点的最长简单路径边的条数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isBalanced(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        if not root:
            return True
        # 检查当前节点的左右子树高度差是否小于 2。
        # 确保左右子树本身也是平衡的。
        return abs(self.height(root.right) - self.height(root.left)) < 2 and self.isBalanced(root.left) and self.isBalanced(root.right)

    def height(self, node):
        if not node:
            return 0
        return 1 + max(self.height(node.right), self.height(node.left))

257. 二叉树的所有路径

要求从根节点到叶子的路径，所以需要前序遍历，方便让父节点指向孩子节点，找到对应的路径。

这道题目涉及到回溯，因为要把路径记录下来，需要回溯来回退一个路径再进入另一个路径。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def binaryTreePaths(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[str]
        """
        res = []
        path = []
        if not root:
            return res
        self.traversal(root, path, res)
        return res

    def traversal(self, temp, path, res):
        path.append(temp.val) # 中
        if not temp.left and not temp.right: # 到达叶子节点
            sPath = '->'.join(map(str, path))
            res.append(sPath)
            return
        if temp.left: # 左
            self.traversal(temp.left, path, res)
            path.pop() # 回溯
        if temp.right: # 右
            self.traversal(temp.right, path, res)
            path.pop() # 回溯

404. 左叶子之和

首先要注意是判断左叶子，不是二叉树左侧节点。

左叶子的明确定义：节点 A 的左孩子不为空，且左孩子的左右孩子都为空（说明是叶子节点），那么 A 节点的左孩子为左叶子节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sumOfLeftLeaves(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if root is None:
            return 0
        if root.left is None and root.right is None:
            return 0

        leftValue = self.sumOfLeftLeaves(root.left) # 左
        if root.left and not root.left.left and not root.left.right:  # 左子树是左叶子的情况
            leftValue = root.left.val

        rightValue = self.sumOfLeftLeaves(root.right) # 右

        sumValue = leftValue + rightValue # 中
        return sumValue

222. 完全二叉树的节点个数

在完全二叉树中，除了最底层节点可能没填满，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~2^(h-1) 个节点。

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def countNodes(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        return self.getNodesNum(root)

    def getNodesNum(self, temp):
        if not temp:
            return 0
        leftNum = self.getNodesNum(temp.left) # 左
        rightNum = self.getNodesNum(temp.right) # 右
        treeNum = leftNum + rightNum + 1 # 中
        return treeNum

完全二叉树写法

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def countNodes(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if not root:
            return 0
        left = root.left
        right = root.right
        leftDepth = 0
        rightDepth = 0
        while left: # 求左子树深度
            left = left.left
            leftDepth += 1
        while right: # 求右子树深度
            right = right.right
            rightDepth += 1
        if leftDepth == rightDepth:
            # 这一步利用了满二叉树的性质：一个深度为 d 的满二叉树有 2^(d+1) - 1 个节点
            return (2 << leftDepth) - 1
        return self.countNodes(root.left) + self.countNodes(root.right) + 1

513. 找树左下角的值

采用递归方法实现：

  1. 确定递归函数的参数和返回值
    • 参数必须有要遍历的树的根节点
  2. 确定终止条件
    • 当遇到叶子节点的时候，就需要统计一下最大的深度了，所以需要遇到叶子节点来更新最大深度
  3. 确定单层递归的逻辑
    • 在找最大深度的时候，递归的过程中依然要使用回溯
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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def findBottomLeftValue(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        if not root:
            return 0
        queue = deque()
        queue.append(root)
        res = 0
        while queue:
            size = len(queue)
            for i in range(size):
                node = queue.popleft()
                if i == 0:
                    res = node.val
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
        return res

112. 路径总和

可以使用深度优先遍历的方式来遍历二叉树

递归函数什么时候需要返回值？

  • 如果需要搜索整棵二叉树且不用处理递归返回值，递归函数就不要返回值。
  • 如果需要搜索整棵二叉树且需要处理递归返回值，递归函数就需要返回值。
  • 如果要搜索其中一条符合条件的路径，那么递归一定需要返回值，因为遇到符合条件的路径就要及时返回。
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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def hasPathSum(self, root, targetSum):
        """
        :type root: Optional[TreeNode]
        :type targetSum: int
        :rtype: bool
        """
        if not root:
            return False

        # 如果当前节点为叶子节点，且叶子节点的值等于减去该路径之前节点的值，返回 True
        if not root.left and not root.right and root.val == targetSum:
            return True
        
        # 递归左子树
        leftPath = self.hasPathSum(root.left, targetSum - root.val)
        # 递归右子树
        rightPath = self.hasPathSum(root.right, targetSum - root.val)

        return leftPath or rightPath

106. 从中序与后序遍历序列构造二叉树

一层一层切割，应该想到递归。

  • 第一步：如果数组大小为零的话，说明是空节点了。
  • 第二步：如果不为空，那么取后序数组最后一个元素作为节点元素。
  • 第三步：找到后序数组最后一个元素在中序数组的位置，作为切割点
  • 第四步：切割中序数组，切成中序左数组和中序右数组 （顺序别搞反了，一定是先切中序数组）
  • 第五步：切割后序数组，切成后序左数组和后序右数组
  • 第六步：递归处理左区间和右区间
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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def buildTree(self, inorder, postorder):
        """
        :type inorder: List[int]
        :type postorder: List[int]
        :rtype: Optional[TreeNode]
        """
        # 1. 数为空
        if not postorder:
            return None

        # 2. 后序遍历的最后一个就是当前的中间节点
        root_val = postorder[-1]
        root = TreeNode(root_val)

        # 3. 找切割点
        separator_idx = inorder.index(root_val)

        # 4. 切割 inroder 数组
        inorder_left = inorder[:separator_idx]
        inorder_right = inorder[separator_idx + 1:]

        # 5. 切割 postorder 数组
        # 中序数组大小一定跟后序数组大小是相同的
        postorder_left = postorder[:len(inorder_left)]
        postorder_right = postorder[len(inorder_left): -1]

        # 6. 递归
        root.left = self.buildTree(inorder_left, postorder_left)
        root.right = self.buildTree(inorder_right, postorder_right)

        # 7. 返回答案
        return root

654. 最大二叉树

以此数组构建的最大二叉树定义如下：

  • 二叉树的根是数组中的最大元素
  • 左子树是通过数组中最大值左边部分构造出的最大二叉树
  • 右子树是通过数组中最大值右边部分构造出的最大二叉树

构造树一般采用的是前序遍历，因为先构造中间节点，然后递归构造左子树和右子树。

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def constructMaximumBinaryTree(self, nums):
        """
        :type nums: List[int]
        :rtype: Optional[TreeNode]
        """
        if len(nums) == 1:
            return TreeNode(nums[0])
        node = TreeNode(0)

        # 找到数组中最大的值和对应的下标
        maxValue = 0
        maxValueIndex = 0
        for i in range(len(nums)):
            if nums[i] > maxValue:
                maxValue = nums[i]
                maxValueIndex = i
        node.val = maxValue

        # 最大值所在的下标左区间 构造左子树
        if maxValueIndex > 0:
            new_list = nums[:maxValueIndex]
            node.left = self.constructMaximumBinaryTree(new_list)
        # 最大值所在的下标右区间 构造右子树
        if maxValueIndex < len(nums) - 1:
            new_list = nums[maxValueIndex + 1:]
            node.right = self.constructMaximumBinaryTree(new_list)
        return node

617. 合并二叉树

和遍历一个树逻辑一样，只不过传入两个树的节点，同时操作。

迭代法实现：

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def mergeTrees(self, root1, root2):
        """
        :type root1: Optional[TreeNode]
        :type root2: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        if not root1:
            return root2
        if not root2:
            return root1
        
        queue = deque()
        queue.append(root1)
        queue.append(root2)

        while queue:
            node1 = queue.popleft()
            node2 = queue.popleft()

            # 更新 queue
            # 只有两个节点都有左节点时，再往 queue 里面放
            if node1.left and node2.left:
                queue.append(node1.left)
                queue.append(node2.left)
            # 只有两个节点都有右节点时，再往 queue 里面放
            if node1.right and node2.right:
                queue.append(node1.right)
                queue.append(node2.right)
            
            # 更新当前节点，同时改变当前节点的左右孩子
            node1.val += node2.val
            if not node1.left and node2.left:
                node1.left = node2.left
            if not node1.right and node2.right:
                node1.right = node2.right
        return root1

700. 二叉搜索树中的搜索

二叉搜索树是一个有序树：

  • 若它的左子树不为空，则左子树上所有节点的值均小于它的根节点的值
  • 若它的右子树不为空，则右子树上所有节点的值均大于它的根节点的值
  • 它的左、右子树也分别为二叉搜索树
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def searchBST(self, root, val):
        """
        :type root: Optional[TreeNode]
        :type val: int
        :rtype: Optional[TreeNode]
        """
        while root:
            if val < root.val:
                root = root.left
            elif val > root.val:
                root = root.right
            else:
                return root
        return None

98. 验证二叉搜索树

中序遍历下，输出的二叉搜索树节点的数值是有序序列。

迭代法实现：

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def isValidBST(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: bool
        """
        stack = []
        cur = root
        pre = None # 记录前一个节点

        while cur is not None or len(stack) > 0:
            if cur is not None:
                stack.append(cur)
                cur = cur.left # 左
            else:
                cur = stack.pop() # 中
                if pre is not None and cur.val <= pre.val:
                    return False
                pre = cur # 保存前一个访问的节点
                cur = cur.right # 右
        return True

530. 二叉搜索树的最小绝对差

二叉搜索树是有序的。

想象成在一个有序数组上求最值，求差值。

  • getMinimumDifference 方法首先用中序遍历将 BST 的节点值存入 res 列表，这样列表 res 中的值是有序的。
  • 然后计算 res 中相邻元素的最小绝对差，并返回该最小值。
  • inorderTraversal 方法使用递归实现中序遍历，保证节点值按升序排列。
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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def getMinimumDifference(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        res = []
        minRes = float('inf')
        self.inorderTraversal(root, res)
        # 求最小绝对差
        for i in range(len(res) - 1):
            minRes = min(abs(res[i] - res[i + 1]), minRes)

        return minRes
        
    def inorderTraversal(self, root, res):
        if root == None:
            return
        self.inorderTraversal(root.left, res)
        res.append(root.val)
        self.inorderTraversal(root.right, res)

501. 二叉搜索树中的众数

使用迭代法实现：

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def findMode(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: List[int]
        """
        stack = []
        # 记录前一个元素
        pre = None
        # 记录次数
        count = 0
        # 记录最大次数
        maxCount = 0
        # 记录结果
        res = []

        while root or stack:
            if root:
                stack.append(root)
                root = root.left
            else:
                cur = stack.pop()
                # 第一个节点
                if pre == None:
                    count = 1
                # 如果与前一个节点的值相等
                elif pre.val == cur.val:
                    count += 1
                else:
                    count = 1

                # 如果和最大次数相同，将值放入 res
                if count == maxCount:
                    res.append(cur.val)
                # 如果大于最大次数
                if count > maxCount:
                    maxCount = count
                    res = [cur.val]
                pre = cur
                root = cur.right
        return res

236. 二叉树的最近公共祖先

首先想到自底向上查找，这样就可以找到公共祖先了。

二叉树回溯的过程就是自底向上。

后序遍历（左右中）就是天然的回溯过程，可以根据左右子树的返回值，来处理中节点的逻辑。

  • 求最小公共祖先，需要从底向上遍历，二叉树只能通过后序遍历实现从底向上的遍历方式。
  • 在回溯的过程中，必然要遍历整颗二叉树，即使已经找到结果，依然要把其他节点遍历完，因为要使用递归函数的返回值（也就是代码中的 left 和 right）做逻辑判断。
  • 如果返回值 left 为空，right 不为空返回 right，可以用返回 right 传给上一层结果。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        if root == p or root == q or root is None:
            return root
        
        left = self.lowestCommonAncestor(root.left, p, q)
        right = self.lowestCommonAncestor(root.right, p, q)

        if left is not None and right is not None:
            return root
        
        if left is None and right is not None:
            return right
        elif left is not None and right is None:
            return left
        else:
            return None

235. 二叉搜索树的最近公共祖先

可以利用二叉搜索树有序的特点

使用迭代法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def lowestCommonAncestor(self, root, p, q):
        """
        :type root: TreeNode
        :type p: TreeNode
        :type q: TreeNode
        :rtype: TreeNode
        """
        while root:
            if root.val > p.val and root.val > q.val:
                root = root.left
            elif root.val < p.val and root.val < q.val:
                root = root.right
            else:
                return root
        return None

701. 二叉搜索树中的插入操作

只要按照二叉搜索树的规则去遍历，遇到空节点就插入节点就可以了。

采用递归方法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def insertIntoBST(self, root, val):
        """
        :type root: Optional[TreeNode]
        :type val: int
        :rtype: Optional[TreeNode]
        """
        if not root:
            node = TreeNode(val)
            return node
        
        if root.val > val:
            root.left = self.insertIntoBST(root.left, val)
        if root.val < val:
            root.right = self.insertIntoBST(root.right, val)

        return root

450. 删除二叉搜索树中的节点

搜索树的节点删除要比节点增加复杂的多，有很多情况需要考虑。

  • 第一种情况：没找到删除的节点，遍历到空节点直接返回了。
  • 找到删除的节点：
    • 第二种情况：左右孩子都为空（叶子节点），直接删除节点，返回 NULL 为根节点。
    • 第三种情况：删除节点的左孩子为空，右孩子不为空，删除节点，右孩子补位，返回右孩子为根节点。
    • 第四种情况：删除节点的右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点。
    • 第五种情况：左右孩子节点都不为空，则将删除节点的左子树头结点（左孩子）放到删除节点的右子树的最左面节点的左孩子上，返回删除节点右孩子为新的根节点。
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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def deleteNode(self, root, key):
        """
        :type root: Optional[TreeNode]
        :type key: int
        :rtype: Optional[TreeNode]
        """
        if not root:
            return root

        if root.val == key:
            if root.left is None and root.right is None:
                return None
            elif root.left is None:
                return root.right
            elif root.right is None:
                return root.left
            else:
                # 临时存储
                cur = root.right
                while cur.left is not None:
                    cur = cur.left
                cur.left = root.left
                return root.right
        
        if root.val > key:
            root.left = self.deleteNode(root.left, key)
        if root.val < key:
            root.right = self.deleteNode(root.right, key)

        return root

669. 修剪二叉树

删除节点时，将删除节点的右孩子直接赋给父节点的左孩子就可以。

使用递归法实现

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def trimBST(self, root, low, high):
        """
        :type root: Optional[TreeNode]
        :type low: int
        :type high: int
        :rtype: Optional[TreeNode]
        """
        if not root:
            return None
        if root.val < low:
            # 寻找符合区间 [low, high] 的节点
            return self.trimBST(root.right, low, high)
        if root.val > high:
            # 寻找符合区间 [low, high] 的节点
            return self.trimBST(root.left, low, high)
        root.left = self.trimBST(root.left, low, high) # root.left 接入符合条件的左孩子
        root.right = self.trimBST(root.right, low, high) # root.right 接入符合条件的右孩子
        return root

108. 将有序数组转换为二叉搜索树

数组构造二叉树，构成平衡树时自然而然地事情，默认都是从数组中间位置取值作为节点元素。

本质就是寻找分割点，分割点作为当前节点，然后递归左区间和右区间。

如果数组长度为偶数，中间节点有两个，取哪一个都可以，只不过构成了不同的平衡二叉树。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def sortedArrayToBST(self, nums):
        """
        :type nums: List[int]
        :rtype: Optional[TreeNode]
        """
        root = self.traversal(nums, 0, len(nums) - 1)
        return root
    
    def traversal(self, nums, left, right):
        if left > right:
            return None

        mid = left + (right - left) // 2
        root = TreeNode(nums[mid])
        root.left = self.traversal(nums, left, mid - 1)
        root.right = self.traversal(nums, mid + 1, right)
        return root

538. 把二叉搜索树转换为累加树

从树中可以看出累加的顺序是右中左，所以需要反中序遍历这个二叉树，然后顺序累加就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def convertBST(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: Optional[TreeNode]
        """
        self.pre = 0   # 记录前一个节点的数值
        self.traversal(root)
        return root
        
    def traversal(self, cur):
        if cur is None:
            return

        self.traversal(cur.right)
        cur.val += self.pre
        self.pre = cur.val
        self.traversal(cur.left)

回溯算法

回溯法也叫做回溯搜索法，是一种搜索方式。

回溯是递归的副产品，只要有递归就会有回溯。

回溯的本质是穷举，穷举所有可能，然后选出想要的答案，如果想让回溯法高效一些，可以加一些剪枝的操作，但也改不了回溯法就是穷举的本质。

回溯法一般可以解决如下几种问题：

  • 组合问题：N 个数里面按一定规则找出 k 个数的集合
  • 切割问题：一个字符按一定规则有几种切割方式
  • 子集问题：一个 N 个数的集合里有多少符合条件的子集
  • 排列问题：N 个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N 皇后，解数独等等

77. 组合

未剪枝：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        result = []  # 存放结果集
        self.backtracking(n, k, 1, [], result)
        return result
        
    def backtracking(self, n, k, startIndex, path, result):
        if len(path) == k:
            result.append(path[:])  # 将当前的 path 添加到结果集
            return
        for i in range(startIndex, n + 1):
            path.append(i)  # 处理节点
            self.backtracking(n, k, i + 1, path, result)
            path.pop()  # 回溯，撤销处理的节点

剪枝优化：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def combine(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: List[List[int]]
        """
        result = []  # 存放结果集
        self.backtracking(n, k, 1, [], result)
        return result
        
    def backtracking(self, n, k, startIndex, path, result):
        if len(path) == k:
            result.append(path[:])  # 将当前的 path 添加到结果集
            return
        for i in range(startIndex, n - (k - len(path)) + 2):  # 剪枝优化
            path.append(i)  # 处理节点
            self.backtracking(n, k, i + 1, path, result)
            path.pop()  # 回溯，撤销处理的节点

216. 组合总和Ⅲ

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(object):
    def combinationSum3(self, k, n):
        """
        :type k: int
        :type n: int
        :rtype: List[List[int]]
        """
        result = []  # 存放结果集
        self.backtracking(n, k, 0, 1, [], result)
        return result

    def backtracking(self, tragetSum, k, currentSum, startIndex, path, result):
        if currentSum > tragetSum:  # 剪枝操作
            return
        if len(path) == k:
            if currentSum == tragetSum:
                result.append(path[:])
            return

        for i in range(startIndex, 9 - (k - len(path)) + 2):
            currentSum += i  # 处理节点
            path.append(i)   # 处理 
            self.backtracking(tragetSum, k, currentSum, i + 1, path, result)
            currentSum -= i  # 回溯
            path.pop()  # 回溯，撤销处理的节点

17. 电话号码的字母组合

  1. 数字与字母如何映射
  2. 两个字母就两个 for 循环，三个字母三个 for 循环，以此类推，无法写出代码
  3. 输入 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
35
36
37
class Solution(object):
    def __init__(self):
        self.letterMap = [
            "",     # 0
            "",     # 1
            "abc",  # 2
            "def",  # 3
            "ghi",  # 4
            "jkl",  # 5
            "mno",  # 6
            "pqrs", # 7
            "tuv",  # 8
            "wxyz"  # 9
        ]
        self.result = []
        self.s = ""

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        if len(digits) == 0:
            return self.result
        self.backtracking(digits, 0)
        return self.result

    def backtracking(self, digits, index):
        if index == len(digits):
            self.result.append(self.s)
            return
        digit = int(digits[index])         # 将索引处的数字转换为整数
        letters = self.letterMap[digit]   # 获取对应的字符集
        for i in range(len(letters)):
            self.s += letters[i]           # 处理字符
            self.backtracking(digits, index + 1)  # 递归调用
            self.s = self.s[:-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
35
36
37
38
39
class Solution(object):
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        # 边界条件
        if not digits:
            return []
        
        # 一个映射表
        phoneMap = {
            "2": "abc",
            "3": "def",
            "4": "ghi",
            "5": "jkl",
            "6": "mno",
            "7": "pqrs",
            "8": "tuv",
            "9": "wxyz",
        }

        # 回溯函数
        def backtrack(index):
            # 递归结束条件
            if index == len(digits):
                combinations.append("".join(combination))
            else:
                digit = digits[index]
                for letter in phoneMap[digit]:
                    combination.append(letter)
                    backtrack(index + 1)
                    combination.pop()
            
        # 初始化变量
        combination = list()
        combinations = list()
        backtrack(0)
        return combinations

39. 组合总和

注意叶子结点的返回条件，本题没有组合要求，仅仅是总和的限制，所以递归没有层数的限制，只要选取的元素总和超过 target，就直接返回

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def combinationSum(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []  # 用于存储所有符合条件的组合
        self.backtrack(candidates, target, 0, 0, [], res)  # 调用回溯函数
        return res
    
    def backtrack(self, candidates, target, total, startIndex, path, res):
        if total > target:
            return
        if total == target:
            res.append(path[:])  # 将当前路径的拷贝存储到结果中
            return

        for i in range(startIndex, len(candidates)):
            total += candidates[i]  # 选择当前数字
            path.append(candidates[i])  # 将当前数字加入路径
            self.backtrack(candidates, target, total, i, path, res)  # 表示可以重复读取当前的数
            total -= candidates[i]  # 撤销选择（回溯）
            path.pop()  # 从路径中移除最后一个数字（回溯）

40. 组合总和Ⅱ

集合（camdidates）中有重复元素，但还不能有重复的组合。

把所有组合求出来，再用 set 或者 map 去重，这样容易超时。

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
class Solution(object):
    def combinationSum2(self, candidates, target):
        """
        :type candidates: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        res = []
        candidates.sort()
        self.backtrack(candidates, target, 0, 0, [], res)
        return res

    def backtrack(self, candidates, target, total, startIndex, path, res):
        if total == target:
            res.append(path[:])
            return
        
        for i in range(startIndex, len(candidates)):
            if i > startIndex and candidates[i] == candidates[i - 1]:
                continue
            if total + candidates[i] > target:
                break
            
            total += candidates[i]
            path.append(candidates[i])
            self.backtrack(candidates, target, total, i + 1, path, res)
            total -= candidates[i]
            path.pop()

131. 分割回文串

例如对于字符串abcdef：

  • 组合问题：选取一个a之后，在bcdef中再去选取第二个，选取b之后在cdef中再选取第三个…
  • 切割问题：切割一个a之后，在bcdef中再去切割第二段，切割b之后在cdef中再切割第三段…
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def partition(self, s):
        """
        :type s: str
        :rtype: List[List[str]]
        """
        res = []
        self.backtrack(s, 0, [], res)
        return res 
        
    def backtrack(self, s, startIndex, path, res):
        if startIndex == len(s):
            res.append(path[:])
            return

        for i in range(startIndex, len(s)):
            # 若反序和正序相同，意味着这是回文串
            if s[startIndex: i + 1] == s[startIndex: i + 1][::-1]:
                path.append(s[startIndex:i + 1])
                self.backtrack(s, i + 1, path, res)  # 从下一处进行切割，判断其余是否仍为回文串
                path.pop()

99. 复原 IP 地址

回溯三部曲

  • 递归参数
  • 递归终止条件
  • 单层搜索的逻辑

判断字串是否合法

主要考虑如下三点：

  • 段位以 0 为开头的数字不合法
  • 段位里有非正整数字符不合法
  • 段位如果大于 255 不合法
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
class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        res = []
        self.backtrack(s, 0, 0, "", res)
        return res

    def backtrack(self, s, start_index, point_num, current, res):
        if point_num == 3:  # 逗点数量为3时，分隔结束
            if self.is_valid(s, start_index, len(s) - 1):
                current += s[start_index:]  # 添加最后一段子字符串
                res.append(current)
            return

        for i in range(start_index, len(s)):
            if self.is_valid(s, start_index, i):
                sub = s[start_index:i+1]
                self.backtrack(s, i + 1, point_num + 1, current + sub + '.', res)
            else:
                break

    def is_valid(self, s, start, end):
        if start > end:
            return False
        if s[start] == '0' and start != end:  # 0 开头数字不合法
            return False
        num = 0
        for i in range(start, end + 1):
            if not s[i].isdigit():
                return False
            num = num * 10 + int(s[i])
            if num > 255:
                return False
        return True

78. 子集

如果把子集问题、组合问题、分割问题都抽象为一棵树的话，那么组合问题和分割问题都是收集树的叶子节点，而子集问题是找树的所有节点。

子集也是一种组合问题，因为它的集合是无序的，子集 {1,2} 和子集 {2,1} 是一样的。

既然是无序，取过的元素不会重复取，写回溯算法的时候，for 就要从 startIndex 开始，而不是从 0 开始。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def subsets(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        path = []
        self.backtrack(nums, 0, path, res)
        return res

    def backtrack(self, nums, startIndex, path, res):
        res.append(path[:])
        if startIndex >= len(nums):
            return 

        for i in range(startIndex, len(nums)):
            path.append(nums[i])
            self.backtrack(nums, i + 1, path, res)
            path.pop()

90. 子集Ⅱ

利用集合去重：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def subsetsWithDup(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        path = []
        nums.sort()  # 去重需要排序
        self.backtrack(nums, 0, path, res)
        return res

    def backtrack(self, nums, startIndex, path, res):
        res.append(path[:])
        uset = set()
        for i in range(startIndex, len(nums)):
            if nums[i] in uset:
                continue
            uset.add(nums[i])
            path.append(nums[i])
            self.backtrack(nums, i + 1, path, res)
            path.pop()

491. 递增子序列

回溯（利用 set 去重）

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(object):
    def findSubsequences(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        path = []
        self.backtrack(nums, 0, path, res)
        return res

    def backtrack(self, nums, startIndex, path, res):
        if len(path) > 1:
            res.append(path[:])
            # 这里不加 return，要取树上的节点

        uset = set()
        for i in range(startIndex, len(nums)):
            if(path and nums[i] < path[-1]) or nums[i] in uset:
                continue

            uset.add(nums[i])
            path.append(nums[i])
            self.backtrack(nums, i + 1, path, res)
            path.pop()

46. 全排列

首先排列是有序的，也就是说 [1,2] 和 [2,1] 是两个集合，这和之前分析的子集以及组合有不同之处。

使用 used 布尔列表，表示每个元素是否已被使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def permute(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        res = []
        path = []
        self.backtrack(nums, path, [False] * len(nums), res)
        return res

    def backtrack(self, nums, path, used, res):
        if len(path) == len(nums):
            res.append(path[:])
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtrack(nums, path, used, res)
            path.pop()
            used[i] = False  # 将当前元素的使用标记重置为未使用

47. 全排列Ⅱ

和上一题的区别在于给定一个可包含重复数字的序列，要返回所有不重复的全排列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        path = []
        self.backtrack(nums, path, [False] * len(nums), res)
        return res

    def backtrack(self, nums, path, used, res):
        if len(path) == len(nums):
            res.append(path[:])
            return 

        for i in range(len(nums)):
            # 如果当前数字与前一个相同且前一个未被使用，则跳过以避免重复
            if (i > 0 and nums[i] == nums[i - 1] and not used[i - 1]) or used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            self.backtrack(nums, path, used, res)
            path.pop()
            used[i] = False

51. N 皇后

n 皇后问题研究的是如何将 n 个皇后放置在 n 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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        res = []  # 存储最终结果的二维字符串数组

        chessboard = ['.' * n for _ in range(n)]  # 初始化棋盘
        self.backtrack(n, 0, chessboard, res)
        return [[''.join(row) for row in solution] for solution in res]  # 返回结果集

    def backtrack(self, n, row, chessboard, res):
        if row == n:
            res.append(chessboard[:])
            return
        
        for col in range(n):
            if self.isValid(row, col, chessboard):
                chessboard[row] = chessboard[row][:col] + 'Q' + chessboard[row][col+1:]  # 放置皇后
                self.backtrack(n, row + 1, chessboard, res)  # 递归到下一行
                chessboard[row] = chessboard[row][:col] + '.' + chessboard[row][col+1:]  # 回溯

    def isValid(self, row, col, chessboard):
        # 检查列
        for i in range(row):
            if chessboard[i][col] == 'Q':
                return False  # 当前列已经存在皇后
        
        # 检查 45 度角是否有皇后
        i, j = row - 1, col - 1
        while i >= 0 and j >= 0:
            if chessboard[i][j] == 'Q':
                return False  # 左上角已经存在皇后
            i -= 1
            j -= 1
        
        # 检查 135 度角是否有皇后
        i, j = row - 1, col + 1
        while i >= 0 and j < len(chessboard):
            if chessboard[i][j] == 'Q':
                return False  # 右上角已经出现皇后
            i -= 1
            j += 1

        return True  # 当前位置合法

37. 解数独

判断棋盘是否合法

  • 同行是否重复
  • 同列是否重复
  • 9 宫格里是否重复
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
class Solution(object):
    def solveSudoku(self, board):
        """
        :type board: List[List[str]]
        :rtype: None Do not return anything, modify board in-place instead.
        """
        self.backtrack(board)

    def backtrack(self, board):
        # 若有解，返回 True；若无解，返回 False
        for i in range(len(board)):  # 遍历行
            for j in range(len(board[0])):  # 遍历列
                if board[i][j] != '.':
                    continue
                for k in range(1, 10):
                    if self.isValid(i, j, k, board):
                        board[i][j] = str(k)
                        if self.backtrack(board):
                            return True
                        board[i][j] = '.'
                # 若数字1-9都不能成功填入空格，返回 Fasle 无解
                return False
        return True
    
    def isValid(self, row, col, val, board):
        # 判断同一行是否冲突
        for i in range(9):
            if board[row][i] == str(val):
                return False
        # 判断同一列是否冲突
        for j in range(9):
            if board[j][col] == str(val):
                return False
        # 判断九宫格是否有冲突
        start_row = (row // 3) * 3
        start_col = (col // 3) * 3
        for i in range(start_row, start_row + 3):
            for j in range(start_col, start_col + 3):
                if board[i][j] == str(val):
                    return False
        return True

贪心算法

一般分为如下四步：

  • 将问题分解为若干个子问题
  • 找出适合的贪心策略
  • 求解每一个子问题的最优解
  • 将局部最优解堆叠成全局最优解

455. 分发饼干

为了满足更多的小孩，就不要造成饼干尺寸的浪费。

这里的局部最优解就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        g.sort()
        s.sort()
        index = len(s) - 1  # 饼干数组的下标
        res = 0  # 满足孩子的数量

        for i in range(len(g) - 1, -1, -1):  # 遍历胃口，从最后一个孩子开始
            if index >= 0 and s[index] >= g[i]:
                res += 1
                index -= 1
        return res

376. 摆动序列

局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。

整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。

实际操作上，其实连删除操作都不用做，题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了（相当于是删除单一坡度上的节点，然后统计长度）。

这就是使用贪心的地方，让峰值尽可能地保持峰值，然后删除单一坡度上的节点。

需要考虑三种情况：

  1. 上下坡中有平坡
  2. 数组首尾两端
  3. 单调坡中有平坡
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) <= 1:
            return len(nums)  # 如果数组长度为0或1，则返回数组长度
        curDiff = 0
        preDiff = 0
        res = 1
        for i in range(len(nums) - 1):
            curDiff = nums[i + 1] - nums[i]  # 计算下一个元素与当前元素地差值
            # 如果遇到一个峰值
            if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
                res += 1
                preDiff = curDiff  # 只在摆动变化的时候更新 preDiff
        return res

53. 最大子序和

局部最优：当前 “连续和” 为负数的时候立刻放弃，从下一个元素重新计算 “连续和”，因为负数加上下一个元素 “连续和” 只会越来越小。

全局最优：选取最大 “连续和”。

局部最优的情况下，并记录最大的 “连续和”，可以推出全局最优。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = float("-inf")  # 初始化结果为负无穷大
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > res:  # 取区间累计的最大值
                res = count
            if count <= 0:  # 相当于重置最大子序起始位置
                count = 0
        return res

122. 买卖股票的最佳时机Ⅱ

首先要清楚两点：

  • 只有一只股票！
  • 当前只有买股票或者卖股票的操作

想获得利润至少要两天为一个交易单元。

只需要收集每天的正利润就可以，收集正利润的区间，就是股票买卖的区间，而只需要关注最终利润，不需要记录区间。

局部最优：收集每天的正利润，全局最优：求的最大利润。

1
2
3
4
5
6
7
8
9
10
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        res = 0
        for i in range(1, len(prices)):
            res += max(prices[i] - prices[i - 1], 0)
        return res

55. 跳跃游戏

局部最优：每次取最大跳跃步数（取最大覆盖范围）。

整体最优：最后得到整体最大覆盖范围，看是否能到终点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def canJump(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        cover = 0
        if len(nums) == 1:
            return True
        
        for i in range(len(nums)):
            if i <= cover:
                cover = max(i + nums[i], cover)
                if cover >= len(nums) - 1:
                    return True
        return False

45. 跳跃游戏Ⅱ

局部最优：当前可移动距离尽可能多走，如果还没到终点，步数加一。

整体最优：一步尽可能多走，从而达到最少步数。

要从覆盖范围出发，不管怎么跳，覆盖范围内一定是可以跳到的，以最小的步数增加覆盖范围，覆盖范围一旦覆盖了终点，得到的就是最少步数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def jump(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        cur_dis = 0  # 当前覆盖最远距离下标
        res = 0  # 记录走的最大步数
        next_dis = 0  # 下一步覆盖最远距离下标

        for i in range(len(nums) - 1):
            next_dis = max(i + nums[i], next_dis)  # 更新下一步覆盖最远距离下标
            if i == cur_dis:  # 遇到当前覆盖最远距离下标
                cur_dis = next_dis  # 更新当前覆盖最远距离下标
                res += 1
        return res

1005. K 次取反后最大化的数组和

局部最优：让绝对值大的负数变为正数，当前数值达到最大。

整体最优：整个数组和达到最大。

  • 将数组按照绝对值大小从大到小排序，注意要按照绝对值的大小。
  • 从前向后遍历，遇到负数将其变为正数，同时 K–。
  • 如果 K 还大于 0，那么反复转变数值最小的元素，将 K 用完。
  • 求和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def largestSumAfterKNegations(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        nums.sort(key=lambda x: abs(x), reverse=True)  # 按照绝对值降序排序数组

        for i in range(len(nums)):  # 执行 k 次取反操作
            if nums[i] < 0 and k > 0:
                nums[i] *= -1
                k -= 1
        
        if k % 2 == 1:  # 如果 k 还有剩余次数，将绝对值最小的元素取反
            nums[-1] *= -1

        res = sum(nums)  # 计算数组 nums 的元素和
        return res

134. 加油站

如果总油量减去总消耗大于等于零，那么一定可以跑完一圈，说明各个站点的加油站剩油量 rest[i] 相加一定是大于等于零的。

每个加油站的剩余量 res[i] 为 gas[i] - cost[i]。

局部最优：当前累加 rest[i] 的和 curSum 一旦小于 0，起始位置至少是 i + 1，因为之前从 i 之前开始一定不行。

全局最优：找到可以跑一圈的起始位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def canCompleteCircuit(self, gas, cost):
        """
        :type gas: List[int]
        :type cost: List[int]
        :rtype: int
        """
        curSum = 0  # 当前累计的剩余油量
        totalSum = 0  # 总剩余油量
        start = 0  # 起始位置

        for i in range(len(gas)):
            curSum += gas[i] - cost[i]
            totalSum += gas[i] - cost[i]

            if curSum < 0:  # 当前累计剩余油量 curSum 小于 0
                start = i + 1  # 起始位置更新为 i + 1
                curSum = 0  # curSum 重新从 0 开始累计
        
        if totalSum < 0: 
            return -1  # 总剩余油量 totalSum 小于 0，说明无法环绕一圈
        return start

135. 分发糖果

一定要确定一边之后，再确定另一边，例如比较每一个孩子的左边，然后再比较右边，如果两边一起考虑一定会顾此失彼。

先确定右边评分大于左边的情况（也就是从前向后遍历）

局部最优：只要右边评分比左边大，右边的孩子就多一颗糖果。

全局最优：相邻的孩子中，评分高的右孩子获得比左边孩子更多的糖果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def candy(self, ratings):
        """
        :type ratings: List[int]
        :rtype: int
        """
        candy = [1] * len(ratings)

        # 从前向后遍历，处理右侧比左侧评分高的情况
        for i in range(1, len(ratings)):
            if ratings[i] > ratings[i - 1]:
                candy[i] = candy[i - 1] + 1

        # 从后向前遍历，处理左侧比右侧评分高的情况
        for i in range(len(ratings) - 2, -1, -1):
            if ratings[i] > ratings[i + 1]:
                candy[i] = max(candy[i], candy[i + 1] + 1)

        # 统计结果
        res = sum(candy)
        return res

860. 柠檬水找零

只需要维护三种金额的数量，5、10 和 20。

有如下三种情况：

  • 账单是 5，直接收下。
  • 账单是 10，消耗一个 5，增加一个 10。
  • 账单是 20，优先消耗一个 10 和一个 5，如果不够，再消耗三个 5。

局部最优：遇到账单 20，优先消耗美元 10，完成本次找零。

全局最优：完成全部账单的找零。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution(object):
    def lemonadeChange(self, bills):
        """
        :type bills: List[int]
        :rtype: bool
        """
        five = 0
        ten = 0
        twenty = 0

        for bill in bills:
            # 收到 5 美元
            if bill == 5:
                five += 1

            # 收到 10 美元
            if bill == 10:
                if five <= 0:
                    return False
                ten += 1
                five -= 1

            # 收到 20 美元
            if bill == 20:
                if five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                elif five >= 3:
                    five -= 3
                else:
                    return False
        return True

406. 根据身高重建队列

如果按照 k 来从小到大排序，排完之后会发现 k 的排列并不符合条件，身高也不符合条件，两个维度都没确定。

按照身高 h 来排序，身高一定是从大到小排（身高相同的话则 k 小的站前面），让高个子在前面。

此时可以确定一个维度了，就是身高，前面的节点一定都比本节点高！

局部最优：优先按身高高的 people 的 k 来插入，插入操作过后的 people 满足队列属性。

全局最优：最后都做完插入操作，整个队列满足题目队列属性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def reconstructQueue(self, people):
        """
        :type people: List[List[int]]
        :rtype: List[List[int]]
        """
        # 先按照h维度的身高顺序从高到低排序。确定第一个维度
        # lambda返回的是一个元组：当-x[0](维度h）相同时，再根据x[1]（维度k）从小到大排序
        people.sort(key=lambda x: (-x[0], x[1]))
        queue = []

        # 根据每个元素的第二个维度k，贪心算法，进行插入
        for p in people:
            queue.insert(p[1], p)
        return queue

452. 用最小数量的箭引爆气球

局部最优：当气球出现重叠，一起射，所用弓箭最少。

全局最优：把所有气球射爆所用弓箭最少。

为了让气球尽可能重叠，需要对数组进行排序。

按照起始位置排序，那么就从前向后遍历气球数组，靠左尽可能让气球重复。

如果气球重叠了，重叠气球中右边边界的最小值之间的区间一定需要一个弓箭。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def findMinArrowShots(self, points):
        """
        :type points: List[List[int]]
        :rtype: int
        """
        if len(points) == 0:
            return 0
        
        points.sort(key = lambda x: x[0])

        cur_min_right = points[0][1]
        count = 1

        for i in points:
            if i[0] > cur_min_right:
                # 当前气球左侧大于这个阈值，那么一定就需要再发射一只箭，并且将阈值更新为当前气球的右侧
                count += 1
                cur_min_right = i[1]
            else:
                # 否则，只需要求阈值和当前气球的右侧较小值来更新阈值
                cur_min_right = min(cur_min_right, i[1])
        return count

435. 无重叠区间

按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def eraseOverlapIntervals(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: int
        """
        if not intervals:
            return 0

        intervals.sort(key = lambda x: x[1])  # 按照右边界升序排序

        result = 1

        for i in range(1, len(intervals)):
            if intervals[i][0] >= intervals[0][1]:  # 没有重叠
                result += 1
                intervals[0][1] = intervals[i][1]  # 更新重叠区间的右边界

        return len(intervals) - result

763. 划分字母区间

在遍历的过程中相当于是要找每一个字母的边界，**如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。**此时前面出现过所有字母，最远也就到这个边界了。

  • 统计每一个字符最后出现的位置。
  • 从头遍历字符，并更新字符的最远出现下标，如果找到字符最远出现位置下标和当前下标相等了，则找到了分割点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def partitionLabels(self, s):
        """
        :type s: str
        :rtype: List[int]
        """
        last_occur = {}  # 存储每个字符最后出现的位置
        for i, char in enumerate(s):
            last_occur[char] = i

        res = []
        start = 0
        end = 0

        for i, char in enumerate(s):
            end = max(end, last_occur[char])  # 找到当前字符出现的最远位置
            if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间
                res.append(end - start + 1)
                start = i + 1
            
        return res

56. 合并区间

先排序，让所有的相邻区间尽可能的重叠在一起，按左边界或者右边界排序都可以，处理逻辑稍有不同。

模拟合并区间，用合并区间后左边界和右边界，作为一个新的区间，加入到 result 数组里就可以了。如果没有合并就把原区间加入到 result 数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        res = []
        if not intervals:
            return res  # 区间集合为空，直接返回

        intervals.sort(key = lambda x: x[0])  # 按照左边界进行排序

        res.append(intervals[0])

        for i in range(1, len(intervals)):
            if res[-1][1] >= intervals[i][0]:  # 发现重叠区间
                # 合并区间，只需要更新结果集最后一个区间的右边界
                res[-1][1] = max(res[-1][1], intervals[i][1])
            else:
                res.append(intervals[i])  # 区间不重叠

        return res

738. 单调递增的数字

举例：数字 332 从前向后遍历的话，变成 329，此时 2 又小于了第一位的 3，真正的结果应该是 299。

那么从后向前遍历，就可以重复利用上次比较得出的结果，从后向前遍历 332 的数值变化为：332 -> 329 -> 299。

采用从后向前遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def monotoneIncreasingDigits(self, n):
        """
        :type n: int
        :rtype: int
        """
        # 将整数转换为字符串
        strNum = list(str(n))

        # 从右往左遍历字符串
        for i in range(len(strNum) - 1, 0, -1):
            # 如果当前字符比前一个字符小，说明需要修改前一个字符
            if strNum[i - 1] > strNum[i]:
                strNum[i - 1] = str(int(strNum[i - 1]) - 1)  # 将前一个字符减 1

                # 将修改位置后面的字符都设置为 9， 因为修改前一个字符可能破坏了递增性质
                for j in range(i, len(strNum)):
                    strNum[j] = '9'

        # 将列表转换为字符串，并将字符串转换为整数并返回
        return int(''.join(strNum))

986. 监控二叉树

摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费了一层的覆盖。

所以把摄像头放在叶子节点的父节点的位置，才能充分利用摄像头的覆盖面积。

局部最优：让叶子节点的父节点安摄像头，所用摄像头最少。

全局最优：全部摄像头数量所用最少。

可以使用后序遍历也就是左右中的顺序，这样就可以在回溯的过程中从下到上进行推导了。

每个节点可能有几种状态：

  • 该节点无覆盖
  • 本节点有摄像头
  • 本节点有覆盖

情况 1：左右节点都有覆盖

左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该是无覆盖的状态。

情况 2：左右节点至少有一个无覆盖的情况

如果是以下情况，则中间节点（父节点）应该放摄像头：

  • left == 0 && right == 0 左右节点无覆盖
  • left == 1 && right == 0 左节点有摄像头，右节点无覆盖
  • left == 0 && right == 1 左节点无覆盖，右节点摄像头
  • left == 0 && right == 2 左节点无覆盖，右节点覆盖
  • left == 2 && right == 0 左节点覆盖，右节点无覆盖

情况 3：左右节点至少有一个摄像头

如果是以下情况，其实就是左右孩子节点有一个摄像头了，那么其父节点就应该是 2（覆盖的状态）

  • left == 1 && right == 2 左节点有摄像头，右节点有覆盖
  • left == 2 && right == 1 左节点有覆盖，右节点有摄像头
  • left == 1 && right == 1 左右节点都有摄像头

情况 4：头结点没有覆盖

以上都处理完了，递归结束之后，可能头结点还有一个无覆盖的情况。

贪心 + 二叉树代码实现

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def minCameraCover(self, root):
        # 0: 该节点未覆盖
        # 1: 该节点有摄像头
        # 2: 该节点有覆盖
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        res = [0]  # 用于记录摄像头的安装数量
        if self.traversal(root, res) == 0:
            res[0] += 1

        return res[0]

    def traversal(self, cur, res):
        if not cur:
            return 2

        left = self.traversal(cur.left, res)
        right = self.traversal(cur.right, res)

        # 左右节点都有覆盖
        if left == 2 and right == 2:
            return 0

        # 左右节点至少有一个无覆盖的情况
        if left == 0 or right == 0:
            res[0] += 1
            return 1

        # 左右节点至少有一个摄像头
        if left == 1 or right == 1:
            return 2

动态规划

如果某一问题有很多重叠子问题，使用动态规划是最有效的。

动态规划中每一个状态一定是由上一个状态推导出来的，这一点区分于贪心，贪心没有状态推导，而是从局部直接选取最优的。

动态规划五部曲：

  1. 确定 dp 数组（dp table）以及下标的含义
  2. 确定递推公式
  3. dp 数组如何初始化
  4. 确定遍历顺序
  5. 举例推导 dp 数组

灵魂三问？

  • 举例推导状态转移公式了吗？
  • 打印 dp 数组的日志了吗？
  • 打印出来的 dp 数组和我想的一样吗？

509. 斐波那契数

  1. 确定 dp 数组以及下标的含义

    dp[i] 的定义为：第 i 个数的斐波那契数值是 dp[i]

  2. 确定递推公式

    状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]

  3. dp 数组如何初始化

    dp[0] = 0, dp[1] = 1

  4. 确定遍历顺序

    dp[i] 是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

  5. 举例推导 dp 数组

    当 N 为 10 的时候，dp 数组应该是如下的数列：

    0 1 1 2 3 5 8 13 21 34 55

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def fib(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 0:
            return 0

        # 创建 dp table
        dp = [0] * (n + 1)

        # 初始化 dp 数组
        dp[0] = 0
        dp[1] = 1

        # 遍历顺序：由前向后
        for i in range(2, n + 1):
            # 确定递推公式
            dp[i] = dp[i - 1] + dp[i - 2]

        return dp[n]

70. 爬楼梯

  1. 确定 dp 数组以及下标的含义

    dp[i]：爬到第 i 层楼梯，有 dp[i] 种方法

  2. 确定递推公式

    状态转移方程 dp[i] = dp[i - 1] + dp[i - 2]

  3. dp 数组如何初始化

    dp[1] = 1, dp[2] = 2

  4. 确定遍历顺序

    dp[i] 是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

  5. 举例推导 dp 数组

    当 N 为 5 的时候，dp 数组应该是如下的数列：

    1 2 3 5 8

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n <= 1:
            return n

        # 创建 dp table
        dp = [0] * (n + 1)

        dp[1] = 1
        dp[2] = 2

        for i in range(3, n + 1):
            # 确定递推公式
            dp[i] = dp[i - 1] + dp[i - 2]
        
        return dp[n]

746. 使用最小花费爬楼梯

  1. 确定 dp 数组以及下标的含义

    dp[i] 的定义：到达第 i 台阶所花费的最少体力为 dp[i]

  2. 确定递推公式

    状态转移方程 dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

  3. dp 数组如何初始化

    dp[0] = 0, dp[1] = 0

  4. 确定遍历顺序

    dp[i] 是依赖 dp[i - 1] 和 dp[i - 2]，那么遍历的顺序一定是从前到后遍历的

  5. 举例推导 dp 数组

    cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]，dp 数组应该是如下的数列：

    0 0 1 2 2 3 3 4 4 5 6

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def minCostClimbingStairs(self, cost):
        """
        :type cost: List[int]
        :rtype: int
        """
        dp = [0] * (len(cost) + 1)
        dp[0] = 0
        dp[1] = 0

        for i in range(2, len(cost) + 1):
            # 选择其中花费体力较小的路径，加上当前步的花费，更新 dp 数组
            dp[i] = min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2])

        # 返回到达楼顶的最小花费
        return dp[len(cost)]

62. 不同路径

最直观的想法就是用图论里的深搜，来枚举出来有多少种路径。机器人每次只能向下或向右移动一步，其实机器人走过的路径可以抽象为一棵二叉树，而叶子节点就是终点。

动态规划实现

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：表示从（0，0）出发，到（i, j）有 dp[i][j]条不同的路径。

  2. 确定递推公式

    状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，因为 dp[i][j]只有这两个方向过来。

  3. dp 数组如何初始化

    dp[i][0] = 1, dp[0][j] = 1

  4. 确定遍历顺序

    dp[i][j]都是从其上方和左方推导而来，那么从左到右一层层遍历即可。

  5. 举例推导 dp 数组

    1 1 1 1 1 1 1
    1 2 3 4 5 6 7
    1 3 6 10 15 21 28 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def uniquePaths(self, m, n):
        """
        :type m: int
        :type n: int
        :rtype: int
        """
        # 创建一个二维列表用于存储唯一路径
        dp = [[0] * n for _ in range(m)]

        # 设置第一行和第一列的基本情况
        for i in range(m):
            dp[i][0] = 1
        for j in range(n):
            dp[0][j] = 1

        # 计算每个单元格的唯一路径数
        for i in range(1, m):
            for j in range(1, n):
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        # 返回右下角单元格的唯一路径数
        return dp[m - 1][n - 1]

63. 不同路径Ⅱ

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：表示从（0，0）出发，到（i, j）有 dp[i][j]条不同的路径。

  2. 确定递推公式

    状态转移方程 dp[i][j] = dp[i - 1][j] + dp[i][j - 1]，但因为有了障碍，（i, j）如果就是障碍的话应该保持初始状态（初始状态为 0）。

  3. dp 数组如何初始化

    dp[i][0] = 1, dp[0][j] = 1

  4. 确定遍历顺序

    dp[i][j]都是从其上方和左方推导而来，那么从左到右一层层遍历即可。

  5. 举例推导 dp 数组

    1 1 1
    1 0 1
    1 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
class Solution(object):
    def uniquePathsWithObstacles(self, obstacleGrid):
        """
        :type obstacleGrid: List[List[int]]
        :rtype: int
        """
        m = len(obstacleGrid)  # 网格的行数
        n = len(obstacleGrid[0])  # 网格的列数

        if obstacleGrid[m - 1][n - 1] == 1 or obstacleGrid[0][0] == 1:
            return 0

        # 创建一个二维列表用于存储路径数
        dp = [[0] * n for _ in range(m)]

        # 设置起点的路径数为 1
        dp[0][0] = 1 if obstacleGrid[0][0] == 0 else 0

        # 计算第一列的路径数
        for i in range(1, m):
            if obstacleGrid[i][0] == 0:
                dp[i][0] = dp[i - 1][0]
            
        # 计算第一行的路径数
        for j in range(1, n):
            if obstacleGrid[0][j] == 0:
                dp[0][j] = dp[0][j - 1]

        # 计算其他位置的路径数
        for i in range(1, m):
            for j in range(1, n):
                if obstacleGrid[i][j] == 1:
                    continue
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1]

        # 返回终点的路径数
        return dp[m - 1][n - 1]

416. 分割等和子集

首先，要求集合里能否出现总和为 sum / 2 的子集。

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[j] 表示：容量（所能装的重量）为 j 的背包，所背的物品价值最大可以为 dp[j]。

  2. 确定递推公式

    递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i])

  3. dp 数组如何初始化

    dp[0] = 0

    题目中只包含正整数的非空数组，所以非 0 下标的元素初始化为 0 即可。

  4. 确定遍历顺序

    如果使用一维 dp 数组，物品遍历的 for 循环放在外层，遍历背包的 for 循环放在内层，且内层 for 循环倒序遍历。

  5. 举例推导 dp 数组

    dp[j] 的数值一定是小于等于 j 的。

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(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        total = 0

        dp = [0] * 10001
        for num in nums:
            total += num
        
        if total % 2 == 1:
            return False
        target = total // 2

        # 开始 0-1 背包
        for num in nums:
            for j in range(target, num - 1, -1):
                dp[j] = max(dp[j], dp[j - num] + num)

        # 集合中的元素正好可以凑成总和 target
        if dp[target] == target:
            return True
        return False

1049. 最后一块石头的重量Ⅱ

尽量让石头分成重量相同的两堆（尽可能相同），相撞之后剩下的石头就是最小的。

一堆的石头重量是 sum，尽可能拼成重量为 sum / 2 的石头堆。

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[j] 表示容量（其实就是重量）为 j 的背包，最多可以背最大重量为 dp[j]。

  2. 确定递推公式

    递推公式：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i])

  3. dp 数组如何初始化

    dp[j] = 0

  4. 确定遍历顺序

    如果使用一维 dp 数组，物品遍历的 for 循环放在外层，遍历背包的 for 循环放在内层，且内层 for 循环倒序遍历。

  5. 举例推导 dp 数组

    输入：[2, 4, 1, 1]，此时 target = (2 + 4 + 1 + 1) / 2 = 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def lastStoneWeightII(self, stones):
        """
        :type stones: List[int]
        :rtype: int
        """
        dp = [0] * 15001
        total_sum = sum(stones)
        target = total_sum // 2

        for stone in stones:  # 遍历物品
            for j in range(target, stone - 1, -1):  # 遍历背包
                dp[j] = max(dp[j], dp[j - stone] + stone)

        return total_sum - dp[target] - dp[target]

494. 目标和

如何使表达式结果为 target？

既然为 target，那么一定有 left 组合 - right 组合 = target。

left + right = sum，而 sum 使固定的。right = sum - left。

left - (sum - left) = target 推导出 left = (target + sum) / 2。

target 是固定的，sum 是固定的，left 就可以求出来。

此时问题就是在集合 nums 中找出和为 left 的组合。

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：使用下标为 [0, i] 的 nums[i] 能够凑满 j（包括 j）这么大容量的包，有 dp[i][j] 种方法。

  2. 确定递推公式

    不放物品 i：即背包容量为 j，里面不放物品 i，装满有 dp[i - 1][j] 种方法。

    放物品 i：即空出物品 i 的容量，背包容量为（j - 物品 i 容量），放满背包有 dp[i - 1][j - 物品 i 容量] 种方法。

    递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]]

  3. dp 数组如何初始化

    dp[i][0] = 1

  4. 确定遍历顺序

    从上到下，从左到右。只有这样，才能基于之前的数值做推导。

  5. 举例推导 dp 数组

    输入：nums: [1, 1, 1, 1, 1]，target：3

    bagSize = (target + sum) / 2 = (3 + 5) / 2 = 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def findTargetSumWays(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        total_sum = sum(nums)  # 计算 nums 的总和
        if abs(target) > total_sum:
            return 0
        if (target + total_sum) % 2 == 1:
            return 0
        target_sum = (target + total_sum) // 2  # 目标和
        dp = [0] * (target_sum + 1)
        dp[0] = 1
        for num in nums:
            for j in range(target_sum, num - 1, -1):
                dp[j] += dp[j - num]  # 状态转移方程
        return dp[target_sum]

474. 一和零

本题中 strs 数组里的元素就是物品，每个物品都是一个！而 m 和 n 相当于是一个背包，两个维度的背包。

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：最多有 i 个 0 和 j 个 1 的 strs 的最大子集的大小为 dp[i][j]。

  2. 确定递推公式

    不放物品 i：即背包容量为 j，里面不放物品 i，装满有 dp[i - 1][j] 种方法。

    放物品 i：即空出物品 i 的容量，背包容量为（j - 物品 i 容量），放满背包有 dp[i - 1][j - 物品 i 容量] 种方法。

    递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)

  3. dp 数组如何初始化

    因为物品价值不会是负数，初始为 0，保证递推的时候 dp[i][j] 不会被初始值覆盖。

  4. 确定遍历顺序

    外层 for 循环遍历物品，内层 for 循环遍历背包容量且从后向前遍历。

    本题也是，物品就是 strs 里的字符串，背包容量就是题目描述中的 m 和 n。

  5. 举例推导 dp 数组

    输入：[“10”,“0001”,“111001”,“1”,“0”]，m = 3，n = 3

    0 1 2 3
    0 1 1 1
    1 2 2 2
    1 2 3 3
    1 2 3 3 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def findMaxForm(self, strs, m, n):
        """
        :type strs: List[str]
        :type m: int
        :type n: int
        :rtype: int
        """
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        for s in strs:  # 遍历物品
            zeroNum = s.count('0')  # 统计 0 的个数
            oneNum = len(s) - zeroNum  # 统计 1 的个数
            for i in range(m, zeroNum - 1, -1):  # 遍历背包容量，从后往前
                for j in range(n, oneNum - 1, -1):
                    dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1)
        return dp[m][n]

518. 零钱兑换Ⅱ

  1. 确定 dp 数组以及下标的含义

    定义二维 dp 数组 dp[i][j]：使用下标为 [0, i] 的 coins[i] 能够凑满 j 这么大容量的包，有 dp[i][j] 种组合方法。

  2. 确定递推公式

    递推公式：dp[i][j] = dp[i - 1][j] + dp[i][j - nums[i]]

  3. dp 数组如何初始化

    dp[i][0] = 1

  4. 确定遍历顺序

    二维 DP 数组的完全背包的两个 for 循环先后顺序是无所谓的。

    先遍历背包，还是先遍历物品都是可以的。

  5. 打印 dp 数组

    以 amount 为 5，coins 为：[2,3,5]

    dp数组应该是这样的：

    1
    2
    3
    1 0 1 0 1 0
    1 0 1 1 1 1
    1 0 1 1 1 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        dp = [0] * (amount + 1)
        dp[0] = 1

        # 遍历物品
        for i in range(len(coins)):
            # 遍历背包
            for j in range(coins[i], amount + 1):
                dp[j] += dp[j - coins[i]]
        
        return dp[amount]

377. 组合总和Ⅳ

描述说是求组合，但元素相同顺序不同的组合算两个组合，其实就是求排列。

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i]：凑成目标正整数为 i 的排列个数为 dp[i]

  2. 确定递推公式

    递推公式：dp[i] += dp[i - nums[j]]

  3. dp 数组如何初始化

    dp[0] = 1

  4. 确定遍历顺序

    个数可以不限使用，说明这是一个完全背包。

    得到的集合是排列，说明需要考虑元素之间的顺序。

    如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。

    如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。

    最终遍历顺序：target（背包）放在外循环，将 nums（物品）放在内循环，内循环从前向后遍历。

  5. 举例推导 dp 数组

    dp[0] = 1

    dp[1] = dp[0] = 1

    dp[2] = dp[1] + dp[0] = 2

    dp[3] = dp[2] + dp[1] + dp[0] = 4

    dp[4] = dp[3] + dp[2] + dp[1] = 7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def combinationSum4(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        dp = [0] * (target + 1)
        dp[0] = 1

        for i in range(1, target + 1):  # 遍历背包
            for j in range(len(nums)):  # 遍历物品
               if i - nums[j] >= 0:
                dp[i] += dp[i - nums[j]]

        return dp[target]

322. 零钱兑换

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[j]：凑足金额为 j 所需钱币的最少个数为 dp[j]

  2. 确定递推公式

    dp[j] = min(dp[j - coins[i]] + 1, dp[j])

  3. dp 数组如何初始化

    dp[0] = 0

  4. 确定遍历顺序

    如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。

    如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。

    本题的两个 for 循环的关系是：外层 for 循环遍历物品，内层 for 遍历背包或者外层 for 遍历背包，内层 for 循环遍历物品都是可以的。

  5. 举例推导 dp 数组

    以输入：coin = [1, 2, 5] ，amount = 5 为例：

    dp[i]：0 1 1 2 2 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        dp = [float('inf')] * (amount + 1)  # 创建数组，初始值为正无穷大
        dp[0] = 0

        for coin in coins:  # 遍历硬币列表，相当于遍历物品
            for i in range(coin, amount + 1):  # 遍历背包容量
                if dp[i - coin] != float('inf'):  # 进行状态转移
                    dp[i] = min(dp[i - coin] + 1, dp[i])  # 更新最小硬币数量

        if dp[amount] == float('inf'):
            return -1
        return dp[amount]

279. 完全平方数

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[j]：和为 j 的完全平方数的最少数量为 dp[j]

  2. 确定递推公式

    dp[j] = min(dp[j - i * i] + 1, dp[j])

  3. dp 数组如何初始化

    dp[0] = 0

  4. 确定遍历顺序

    如果求组合数就是外层 for 循环遍历物品，内层 for 遍历背包。

    如果求排列数就是外层 for 遍历背包，内层 for 循环遍历物品。

    本题的两个 for 循环的关系是：外层 for 循环遍历物品，内层 for 遍历背包或者外层 for 遍历背包，内层 for 循环遍历物品都是可以的。

  5. 举例推导 dp 数组

​ 输入 n = 5，

​ dp[i]：0 1 2 3 1 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def numSquares(self, n):
        """
        :type n: int
        :rtype: int
        """
        dp = [float('inf')] * (n + 1)
        dp[0] = 0

        for i in range(1, n + 1):  # 遍历背包
            for j in range(1, int(i ** 0.5 + 1)):  # 遍历物品
                # 更新凑成数字 i 所需的最少完全平方数数量
                dp[i] = min(dp[i], dp[i - j * j] + 1)

        return dp[n]

139. 单词拆分

单词就是物品，字符串 s 就是背包，单词能否组成字符串 s，就是问物品能不能把背包装满。

拆分时可以重复使用字典中的单词，说明就是一个完全背包。

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i]：字符串长度为 i 的话，dp[i] 为 true，表示可以拆分为一个或多个在字典中出现的单词。

  2. 确定递推公式

    if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

  3. dp 数组如何初始化

    dp[0] = true

  4. 确定遍历顺序

    先遍历背包，再遍历物品。

  5. 举例推导 dp 数组

    以输入：s = “leetcode”, wordDict = [“leet”, “code”]为例，dp 状态如图：

    dp[i]：1 0 0 0 1 0 0 0 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def wordBreak(self, s, wordDict):
        """
        :type s: str
        :type wordDict: List[str]
        :rtype: bool
        """
        wordSet = set(wordDict)
        n = len(s)
        dp = [False] * (n + 1)  # dp[i] 表示字符串的前 i 个字符是否可以被拆分成单词
        dp[0] = True

        for i in range(1, n + 1):  # 遍历背包
            for j in range(i):  # 遍历单词
                if dp[j] and s[j:i] in wordSet:
                    # 如果 s[0:j] 可以被拆分成单词，并且 s[j:i] 在单词集合中存在，则 s[0:i] 可以被拆分成单词
                    dp[i] = True  
                    break
        return dp[n]

198. 打家劫舍

  1. 确定 dp 数组以及下标的含义

    dp[i]：考虑下标 i（包括 i）以内的房屋，最多可以偷窃的金额为 dp[i]。

  2. 确定递推公式

    偷 i：dp[i] = dp[i - 2] + nums[i]

    不偷 i：dp[i] = dp[i - 1]

    递推公式：dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

  3. dp 数组如何初始化

    dp[0] = nums[0]

    dp[1] = max(nums[0], nums[1])

  4. 确定遍历顺序

    从前向后遍历。

  5. 举例推导 dp 数组

    0 1 2 3 4
    2 7 11 11 12 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:  # 如果没有房屋，返回0
            return 0
        if len(nums) == 1:  # 如果只有一个房屋，返回其金额
            return nums[0]

        # 创建一个动态规划数组，用于存储最大金额
        dp = [0] * len(nums)
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
        n = len(nums)

        # 遍历剩余的房屋
        for i in range(2, n):
            # 对于每个房屋，选择抢劫当前房屋和抢劫前一个房屋的最大金额
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])

        return dp[-1]  # 返回最后一个房屋中可抢劫的最大金额

213. 打家劫舍Ⅱ

对于一个数组，成环的话主要有如下三种情况：

  • 情况一：考虑不包含首尾元素
  • 情况二：考虑包含首元素，不包含尾元素
  • 情况三：考虑包含尾元素，不包含首元素
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
class Solution(object):
    def rob(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]

        res1 = self.robRange(nums, 0, len(nums) - 2)  # 情况二
        res2 = self.robRange(nums, 1, len(nums) - 1)  # 情况三
        return max(res1, res2)

    def robRange(self, nums, start, end):
        if end == start:
            return nums[start]

        pre_max = nums[start]
        cur_max = max(nums[start], nums[start + 1])

        for i in range(start + 2, end + 1):
            temp = cur_max
            cur_max = max(pre_max + nums[i], cur_max)
            pre_max = temp
    
        return cur_max

337. 打家劫舍Ⅲ

对于树的话，首先想到遍历方式，前中后序（深度优先搜索）还是层序遍历（广度优先搜索）。

本题一定要后序遍历，因为通过递归函数的返回值来做下一步计算。

如果抢了当前节点，两个孩子就不能动；如果没抢到当前节点，就可以考虑抢左右孩子。

  1. 确定 dp 数组以及下标的含义

    dp[i]：下标为 0 记录不偷该节点所得到的最大金钱，下标为 1 记录偷该节点所得到的最大金钱。

  2. 确定终止条件

    在遍历的过程中，如果遇到空节点的话，无论偷还是不偷都是 0。

    相当于 dp 数组的初始化。

  3. 确定遍历顺序

    使用后序遍历。

    通过递归左节点，得到左节点偷与不偷的金钱。

    通过递归右节点，得到右节点偷与不偷的金钱。

  4. 确定单层递归的逻辑

    如果偷当前节点，那么左右孩子不能偷。

    如果不偷当前节点，那么左右孩子可以偷，选最大的。

  5. 举例推导 dp 数组

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
# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def rob(self, root):
        """
        :type root: Optional[TreeNode]
        :rtype: int
        """
        dp = self.traversal(root)
        return max(dp)

    def traversal(self, node):
        if not node:
            return (0, 0)

        left = self.traversal(node.left)
        right = self.traversal(node.right)

        # 不偷当前节点，偷子节点
        val0 = max(left[0], left[1]) + max(right[0], right[1])

        # 偷当前节点，不偷子节点
        val1 = node.val + left[0] + right[0]

        return (val0, val1)

121. 买卖股票的最佳时机

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i][0] 表示第 i 天持有股票所得最多现金。

    dp[i][1] 表示第 i 天不持有股票所得最多现金。

  2. 确定递推公式

    如果第 i 天持有股票：

    • 第 i - 1 天就持有股票，dp[i - 1][0]
    • 第 i 天买入股票，-price[i]

    那么 dp[i][0] 应该选所得现金最大的，所以 dp[i][0] = max(dp[i - 1][0], -prices[i])

    如果第 i 天不持有股票：

    • 第 i - 1 天不持有股票，dp[i - 1][1]
    • 第 i 天卖出股票，prices[i] + dp[i - 1][0]

    同样 dp[i][1] 取最大的，dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])

  3. dp 数组如何初始化

    dp[0][0] = -price[0]

    dp[0][1] = 0

  4. 确定遍历顺序

    dp[i] 都是由 dp[i - 1] 遍历出来的，那么一定是从前向后遍历。

  5. 举例推导 dp 数组

    输入：[7, 1, 5, 3, 6, 4]

    0 0 4 4 4 5 5

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n == 0:
            return 0

        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = - prices[0]
        dp[0][1] = 0

        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], - prices[i])
            dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])

        return dp[-1][1]

122. 买卖股票的最佳时机Ⅱ

和上一题唯一不同的地方，就是推导 dp[i][0] 时，第 i 天买入股票的情况。

因为一只股票可以买卖多次，所以当第 i 天买入股票的时候，所持有的现金可能有之前买卖过的利润。

第 i 天持有股票即 dp[i][0] ，如果是第 i 天买入股票，所得现金就是昨天不持有股票得所的现金减去今天得股票价格即：dp[i - 1][1] - prices[i]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n == 0:
            return 0
        
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = - prices[0]
        dp[0][1] = 0

        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
            dp[i][1] = max(dp[i - 1][1], prices[i] + dp[i - 1][0])
        
        return dp[-1][1]

123. 买卖股票的最佳时机Ⅲ

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    一天一共有五个状态：

    1. 没有操作
    2. 第一次持有股票
    3. 第一次不持有股票
    4. 第二次持有股票
    5. 第二次不持有股票

    dp[i][j] 中 i 表示第 i 天，j 为 [0 - 4] 五个状态，dp[i][j] 表示第 i 天状态 j 所剩最大现金。

    注意：dp[i][1] 表示得是第 i 天，买入股票的状态，并不是说一定要第 i 天买入股票。

  2. 确定递推公式

    dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])

    dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

    dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])

    dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4])

  3. dp 数组如何初始化

    dp[0][0] = 0

    dp[0][1] = - prices[0]

    dp[0][2] = 0

    dp[0][3] = - prices[0]

    dp[0][4] = 0

  4. 确定遍历顺序

    一定是从前向后遍历

  5. 举例推导 dp 数组

    0 1 2 3 4
    0 -1 0 -1 0
    0 -1 1 -1 1
    0 -1 2 -1 2
    0 -1 3 -1 3
    0 -1 4 -1 4 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n == 0:
            return 0

        dp = [[0] * 5 for _ in range(n)]
        dp[0][1] = - prices[0]
        dp[0][3] = - prices[0]

        for i in range(1, n):
            dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])
            dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])
            dp[i][3] = max(dp[i - 1][2] - prices[i], dp[i - 1][3])
            dp[i][4] = max(dp[i - 1][3] + prices[i], dp[i - 1][4])

        return dp[-1][4]

188. 买卖股票的最佳时机Ⅳ

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    使用二维数组 dp[i][j]：第 i 天的状态为 j，所剩下的最大现金是 dp[i][j]。

    至多有 K 笔交易，那么 j 的范围就定义为 2 * k + 1 即可。

  2. 确定递推公式

    dp[i][1]

    • 操作一：第 i 天买入股票，dp[i][1] = dp[i - 1][0] - prices[i]
    • 操作二：第 i 天没有操作，沿用前一天买入的状态，dp[i][1] = dp[i - 1][1]

    递推公式：dp[i][1] = max(dp[i - 1][0] - prices[i], dp[i - 1][1])

    dp[i][2]

    • 操作一：第 i 天卖出股票，dp[i][2] = dp[i - 1][1] + prices[i]
    • 操作二：第 i 天没有操作，沿用前一天卖出的状态，dp[i][2] = dp[i - 1][2]

    递推公式：dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

  3. dp 数组如何初始化

    dp[0][0] = 0

    dp[0][1] = - prices[0]

    dp[0][3] = - prices[0]

    dp[0][4] = 0

    同理，可以推出 dp[0][j] 当 j 为奇数的时候都初始化为 -prices[0]

  4. 确定遍历顺序

    从前向后遍历

  5. 举例推导 dp 数组

    0 1 2 3 4
    0 -1 0 -1 0
    0 -1 1 -1 1
    0 -1 2 -1 2
    0 -1 3 -1 3
    0 -1 4 -1 4 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution(object):
    def maxProfit(self, k, prices):
        """
        :type k: int
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n == 0:
            return 0
        
        dp = [[0] * (2 * k + 1) for _ in range(n)]
        
        for j in range(1, 2 * k, 2):
            dp[0][j] = -prices[0]

        for i in range(1, n):
            for j in range(0, 2 * k - 1, 2):
                dp[i][j + 1] = max(dp[i - 1][j] - prices[i], dp[i - 1][j + 1])
                dp[i][j + 2] = max(dp[i - 1][j + 1] + prices[i], dp[i - 1][j + 2])

        return dp[-1][2 * k]

309. 买卖股票的最佳时机含冷冻期

  1. 确定 dp 数组以及下标的含义

    dp[i][j]，第 i 天状态为 j，所剩的最多现金为 dp[i][j]。

    • 状态一：持有股票
    • 不持有股票：
      • 状态二：保持卖出股票的状态（两天前卖出股票，度过一天冷冻期。或者前一天卖出股票状态，一直没操作）
      • 状态三：今天卖出股票
    • 状态四：今天为冷冻期，但冷冻期不可持续，只有一天

  2. 确定递推公式

    达到买入股票的状态（状态一），即 dp[i][0]：

    • 操作一：前一天持有股票（状态一），dp[i][0] = dp[i - 1][0]
    • 操作二：
      • 前一天是冷冻期（状态四），dp[i - 1][3] - prices[i]
      • 前一天是卖出股票（状态二），dp[i - 1][1] - prices[i]

    dp[i][0] = max(dp[i - 1][0], dp[i - 1][3] - prices[i])

    达到保持卖出股票状态（状态二），即 dp[i][1]：

    • 操作一：前一天就是状态二
    • 操作二：前一天是冷冻期

    dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])

    达到今天就卖出股票状态（状态三），即 dp[i][2]：

    昨天一定持有股票，今天买出

    dp[i][2] = dp[i - 1][0] + prices[i]

    达到冷冻期状态（状态四），即 dp[i][3]：

    昨天卖出了股票

    dp[i][3] = dp[i - 1][2]

  3. dp 数组如何初始化

    dp[0][0] = -prices[0]

    dp[0][1] = 0

    dp[0][2] = 0

    dp[0][3] = 0

  4. 确定遍历顺序

    从前向后遍历

  5. 举例推导 dp 数组

    0 1 2 3
    -1 0 0 0
    -1 0 1 0
    -1 0 2 1
    1 1 -1 2
    1 2 3 -1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        n = len(prices)
        if n == 0:
            return 0
 
        dp = [[0] * 4 for _ in range(n)]
        dp[0][0] = -prices[0]
        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], max(dp[i - 1][3], dp[i - 1][1]) - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][3])
            dp[i][2] = dp[i - 1][0] + prices[i]
            dp[i][3] = dp[i - 1][2]
        
        return max(dp[n - 1][1], dp[n - 1][2], dp[n - 1][3])

714. 买卖股票的最佳时机含手续费

  1. 确定 dp 数组以及下标含义

    dp[i][0] 表示第 i 天持有股票所得最多现金。dp[i][1] 表示第 i 天不持有股票所得最多现金。

  2. 确定递推公式

    如果第 i 天持有股票即 dp[i][0]

    • 第 i - 1 天持有股票，保持现状，所得现金就是昨天持有股票的所得现金，dp[i - 1][0]。
    • 第 i 天买入股票，所得现金就是昨天不持有股票的所得现金减去今天股票价格，dp[i - 1][1] - prices[i]。

    dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])

    如果第 i 天不持有股票即 dp[i][1]

    • 第 i - 1天不持有股票，保持现状，所得现金就是昨天不持有股票得所得现金，dp[i - 1][1]。
    • 第 i 天卖出股票，所得现金就是按照今天股票价格卖出后所得现金，需要计算手续费，dp[i - 1][0] + prices[i] - fee。

    dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def maxProfit(self, prices, fee):
        """
        :type prices: List[int]
        :type fee: int
        :rtype: int
        """
        n = len(prices)
        dp = [[0] * 2 for _ in range(n)]
        dp[0][0] = -prices[0]

        for i in range(1, n):
            dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] - prices[i])
            dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] + prices[i] - fee)

        return max(dp[-1][0], dp[-1][1])

300. 最长递增子序列

动规五部曲：

  1. dp[i] 的定义

    dp[i] 表示 i 之前包括 i 的以 nums[i] 结尾的最长递归子序列的长度

  2. 状态转移方程

    if (nums[i] > nums[j]):

    ​ dp[i] = max(dp[i], dp[j] + 1)

    这里不是要 dp[i] 与 dp[j] + 1 进行比较，而是要取 dp[j] + 1 的最大值。

  3. dp[i] 的初始化

    每一个 i，对应的 dp[i]（即最长递增子序列）起始大小至少都是 1。

  4. 确定遍历顺序

    从前往后遍历

  5. 举例推导 dp 数组

    0 1 2 3 4
    1 2 1 1 1
    1 2 1 1 1
    1 2 1 3 1
    1 2 1 3 3 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def lengthOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n <= 1:
            return n
        dp = [1] * n
        res = 1
        for i in range(1, n):
            for j in range(0, i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            res = max(res, dp[i])  # 取最长的子序列
        return res

674. 最长连续递增序列

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i]：以下标 i 为结尾的连续递增的子序列长度为 dp[i]。

  2. 确定递推公式

    如果 nums[i] > nums[i - 1]，那么以 i 为结尾的连续递增子序列长度一定等于以 i - 1 为结尾的连续递增子序列长度 + 1。

    递推公式：dp[i] = dp[i - 1] + 1

  3. dp 数组如何初始化

    dp[i] = 1

  4. 确定遍历顺序

    从前向后遍历

  5. 举例推导 dp 数组

    0 1 2 3 4

    1 2 3 1 2

    取 dp[i] 里的最大值，所以 dp[2] 才是结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def findLengthOfLCIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if not nums:
            return 0

        max_len = 1
        cur_len = 1

        for i in range(1, len(nums)):
            if nums[i] > nums[i - 1]:
                cur_len += 1
                max_len = max(max_len, cur_len)
            else:
                cur_len = 1
        return max_len

718. 最长重复子数组

用二维数组可以记录两个字符串的所有比较情况。

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：以下标为 i - 1 为结尾的 A，以下标为 j - 1 为结尾的 B，最长重复子数组长度为 dp[i][j]。

    dp[i][j] 的定义也就决定了遍历 dp[i][j] 的时候 i 和 j 都要从 1 开始。

  2. 确定递推公式：

    根据 dp[i][j] 的定义，dp[i][j] 的状态只能由 dp[i - 1][j - 1] 推导出来。

    当 A[i - 1] 和 B[j - 1] 相等的时候，dp[i][j] = dp[i - 1][j - 1] + 1

  3. dp 数组如何初始化

    dp[i][0] 和 dp[0][j] 初始化为 0。

  4. 确定遍历顺序

    外层 for 循环遍历 A，内层 for 循环遍历 B。

  5. 举例推导 dp 数组

    输入：A[1, 2, 3, 2, 1] B[3, 2, 1, 4, 7]

    最大长度为 3

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(object):
    def findLength(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        # 创建二维数组 dp
        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]
        # 记录最长公共子数组的长度
        res = 0

        # 遍历数组 nums1
        for i in range(1, len(nums1) + 1):
            # 遍历数组 nums2
            for j in range(1, len(nums2) + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    # 在当前位置上的最长公共子数组的长度为前一个位置上的长度 + 1
                    dp[i][j] = dp[i - 1][j - 1] + 1
                # 更新最长公共子数组的长度
                if dp[i][j] > res:
                    res = dp[i][j]

        return res

1143. 最长公共子序列

  1. 确定 dp 数组以及下标的含义：

    dp[i][j]：长度为 [0, i - 1] 的字符串 text1 与长度为 [0, j - 1] 的字符串 text2 的最长公共子序列为 dp[i][j]。

  2. 确定递推公式

    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

  3. dp 数组如何初始化

    dp[i][0] = 0

    dp[0][j] = 0

  4. 确定遍历顺序

    从前往后，从上到下遍历这个矩阵

  5. 举例推导 dp 数组

    输入：text1 = “abcde”，text2 = “ace”

    0 0 0 0

    0 1 1 1

    0 1 1 1

    0 1 2 2

    0 1 2 2

    0 1 2 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def longestCommonSubsequence(self, text1, text2):
        """
        :type text1: str
        :type text2: str
        :rtype: int
        """
        # 创建一个二维数组 dp, 用于存储最长公共子序列的长度
        dp = [[0] * (len(text2) + 1) for _ in range(len(text1) + 1)]

        # 遍历 text1 和 text2，填充 dp 数组
        for i in range(1, len(text1) + 1):
            for j in range(1, len(text2) + 1):
                if text1[i - 1] == text2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        
        # 返回最长公共子序列的长度
        return dp[len(text1)][len(text2)]

1035. 不相交的线

绘制一些连接两个数字 nums1[i] 和 nums2[j] 的直线，只要 nums1[i] == nums2[j]，且直线不能相交。

直线不能相交，就是说在字符串 nums1 中找到一个字符串 nums2 相同的子序列，且这个子序列不能改变相对顺序，只要相对顺序不改变，连接相同数字的直线就不会相交。

本题说是求绘制的最大连接数，其实就是求两个字符串的最长公共子序列的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def maxUncrossedLines(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: int
        """
        # 创建一个二维数组 dp, 用于存储最长公共子序列的长度
        dp = [[0] * (len(nums2) + 1) for _ in range(len(nums1) + 1)]

        for i in range(1, len(nums1) + 1):
            for j in range(1, len(nums2) + 1):
                if nums1[i - 1] == nums2[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        return dp[len(nums1)][len(nums2)]

53. 最大子序和

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i]：包括下标 i 的最大连续子序列和为 dp[i]。

  2. 确定递推公式

    dp[i] 只有两个方向可以推导：

    • dp[i - 1] + nums[i]，即 nums[i] 加入当前连续子序列和。
    • nums[i]，即从头开始计算当前连续子序列和。

    递推公式：dp[i] = max(dp[i - 1] + nums[i], nums[i])

  3. dp 数组如何初始化

    dp[0] = nums[0]

  4. 确定遍历顺序

    从前向后遍历

  5. 举例推导 dp 数组

    输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]

    0 1 2 3 4 5 6 7 8
    -2 1 -2 4 3 5 6 1 5 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [0] * len(nums)
        dp[0] = nums[0]
        res = dp[0]

        for i in range(1, len(nums)):
            # 递推公式
            dp[i] = max(dp[i - 1] + nums[i], nums[i])
            res = max(res, dp[i])
        return res

392. 判断子序列

根据题意可以发现，只需要计算删除的情况，不用考虑增加和替换的情况。

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：表示以下标 i - 1 为结尾的字符换 s，和以下标 j - 1 为结尾的字符串 t，相同子序列的长度为 dp[i][j]。

  2. 确定递推公式

    • if (s[i - 1] == t[j - 1])

      • t 中找到了一个字符在 s 中也出现了

    • if (s[i - 1] != t[j - 1])

      • 相当于 t 要删除元素，继续匹配

  3. dp 数组初始化

    dp[i][j] 都是依赖于 dp[i - 1][j - 1] 和 dp[i][j - 1]，需要初始化。

  4. 确定遍历顺序

    从上到下，从左到右

  5. 举例推导 dp 数组

    输入 s = “abc”，t = “ahbgdc”

    a h b g d c
    0 0 0 0 0 0 0
    0 1 1 1 1 1 1
    0 0 0 2 2 2 2
    0 0 0 0 0 0 3 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution(object):
    def isSubsequence(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
        for i in range(1, len(s) + 1):
            for j in range(1, len(t) + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    dp[i][j] = dp[i][j - 1]
        if dp[-1][-1] == len(s):
            return True
        return False

115. 不同的子序列

只有删除操作，不用考虑替换增加。

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：以 i - 1 为结尾的 s 子序列中出现以 j - 1 为结尾的 t 的个数为 dp[i][j]。

  2. 确定递推公式

    基本要分析两种情况：

    • s[i - 1] 与 t[j - 1] 相等
    • s[i - 1] 与 t[j - 1] 不相等

    当s[i - 1] 与 t[j - 1] 相等时，dp[i][j] 可以有两部分组成。

    一部分用 s[i - 1] 来匹配，个数为 dp[i - 1][j - 1]。即不需要考虑当前 s 字串和 t 字串的最后一位字母，所以只需要 dp[i - 1][j - 1]。

    另一部分是不用 s[i - 1] 来匹配，个数为 dp[i - 1][j]。

    递推公式为：dp[i][j] = dp[i - 1][j]。

  3. dp 数组如何初始化

    dp[0][j] = 0

    dp[0][0] = 1

  4. 确定遍历顺序

    从上到下，从左到右

  5. 距离推导 dp 数组

    s：“baegg”，t：“bag” 为例，推导 dp 数组状态

    ​ b a g

    ​ 1 0 0 0

    b 1 1 0 0

    a 1 1 1 0

    e 1 1 1 0

    g 1 1 1 1

    g 1 1 1 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def numDistinct(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: int
        """
        dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]

        for i in range(len(s)):
            dp[i][0] = 1
        for j in range(1, len(t)):
            dp[0][j] = 0
        for i in range(1, len(s) + 1):
            for j in range(1, len(t) + 1):
                if s[i - 1] == t[j - 1]:
                    dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
                else: 
                    dp[i][j] = dp[i - 1][j]
        return dp[-1][-1]

583. 两个字符串的删除操作

两个字符串可以相互删除。

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：以 i - 1 为结尾的字符串 word1，和以 j - 1 为结尾的字符串 word2。想要达到相等，所需要删除元素的最少次数。

  2. 确定递推公式

    • 当 word1[i - 1] 与 word2[j - 1] 相同的时候
    • 当 word1[i - 1] 与 word2[j - 1] 不相同的时候

    当 word1[i - 1] 与 word2[j - 1] 相同的时候，dp[i][j] = dp[i - 1][j - 1]

    当 word1[i - 1] 与 word2[j - 1] 不相同的时候，有三种情况：

    • 删 word1[i - 1]，最少操作次数为 dp[i - 1][j] + 1
    • 删 word2[j - 1]，最少操作次数为 dp[i][j - 1] + 1
    • 同时删 word1[i - 1] 和 word2[j - 1]，操作的最少次数为 dp[i - 1][j - 1] + 2

    最后取最小值，所以当 word1[i - 1] 与 word2[j - 1] 不相同的时候，

    递推公式：dp[i][j] = min({dp[i - 1][j - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1})。

    可简化为：dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1)。

  3. dp 数组如何初始化

    dp[i][0] = i

    dp[0][j] = j

  4. 确定遍历顺序

    从上到下，从左到右

  5. 举例推导 dp 数组

    ​ e a t

    ​ 0 1 2 3

    s 1 2 3 4

    e 2 1 2 3

    a 3 2 1 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
        for i in range(len(word1) + 1):
            dp[i][0] = i
        for j in range(len(word2) + 1):
            dp[0][j] = j
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 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 - 1] + 2, dp[i - 1][j] + 1, dp[i][j - 1] + 1)
        return dp[-1][-1]

72. 编辑距离

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i][j] 表示以下标 i - 1 为结尾的字符串 word1，和以下标 j - 1 为结尾的字符串 word2，最近编辑距离为 dp[i][j]。

  2. 确定递推公式

    1
    2
    3
    4
    if word1[i - 1] == word2[j - 1]:
        dp[i][j] = dp[i - 1][j - 1]
    else:
        dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1

  3. dp 数组如何初始化

    dp[i][j] 表示以下标 i - 1 为结尾的字符串 word1，和以下标 j - 1 为结尾的字符串 word2，最近编辑距离为 dp[i][j]。

    dp[i][0] = i

    dp[0][j] = j

  4. 确定遍历顺序

    从左到右，从上到下

  5. 举例推导 dp 数组

    输入：word1 = “horse”，word2 = “ros”

    0 1 2 3

    1 1 2 3

    2 2 1 2

    3 2 2 2

    4 3 3 2

    5 4 4 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        dp = [[0] * (len(word2) + 1) for _ in range(len(word1) + 1)]
        for i in range(1, len(word1) + 1):
            dp[i][0] = i
        for j in range(1, len(word2) + 1):
            dp[0][j] = j
        for i in range(1, len(word1) + 1):
            for j in range(1, len(word2) + 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 - 1], dp[i - 1][j], dp[i][j - 1]) + 1
        return dp[-1][-1]

647. 回文子串

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    布尔类型的 dp[i][j]：表示区间范围 [i, j]（注意是左闭右闭）的子串是否是回文子串，如果是 dp[i][j] 为 true，否则为 false。

  2. 确定递推公式

    整体上是两种，s[i] 与 s[j] 相等，s[i] 与 s[j] 不相等。

    当 s[i] 与 s[j] 不相等，dp[i][j] 一定是 false。

    当 s[i] 与 s[j] 相等时，有如下三种情况

    • 情况一：下标 i 与 j 相同，同一个字符例如 a，当然是回文子串
    • 情况二：下标 i 与 j 相差为 1，例如 aa，也是回文子串
    • 情况三：下标 i 与 j 相差大于 1 的时候，例如 cabac，此时 s[i] 与 s[j] 已经相同了，看 i 到 j 区间是不是回文子串就看 aba 是不是回文就可以，那么 aba 的区间就是 i + 1 与 j - 1 区间，是不是回文就看 dp[i + 1][j - 1] 是否为 true。

    递推公式：

    1
    2
    3
    4
    5
    6
    7
    if s[i] == s[j]:
        if j - i <= 1:
            result += 1
            dp[i][j] = true
        elif dp[i + 1][j - 1]:
            result += 1
            dp[i][j] = true

  3. dp 数组如何初始化

    dp[i][j] 初始化为 false。

  4. 确定遍历顺序

    从上到下，从左到右

  5. 举例推导 dp 数组

    a a a
    1 1 1
    0 1 1
    0 0 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
    def countSubstrings(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = [[0] * len(s) for _ in range(len(s))]
        res = 0
        for i in range(len(s) - 1, -1, -1):
            for j in range(i, len(s)):
                if s[i] == s[j]:
                    if j - i <= 1:  # 情况一和二
                        res += 1
                        dp[i][j] = True
                    elif dp[i + 1][j - 1]:  # 情况三
                        res += 1
                        dp[i][j] = True
        return res

516. 最长回文子序列

回文字串是要连续的，回文子序列不是连续的！

动规五部曲：

  1. 确定 dp 数组以及下标的含义

    dp[i][j]：字符串 s 在 [i, j] 范围内最长的回文子序列的长度为 dp[i][j]。

  2. 确定递推公式

    如果 s[i] 与 s[j] 相同，那么 dp[i][j] = dp[i + 1][j - 1] + 2。

    如果 s[i] 与 s[j] 不相同，

    加入 s[j] 的回文子序列长度为 dp[i + 1][j]。

    加入 s[i] 的回文子序列长度为 dp[i][j - 1]。

    dp[i][j] 一定取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。

  3. dp 数组如何初始化

    dp[i][i] = 1

  4. 确定遍历顺序

    从上到下，从左向右

  5. 举例推导 dp 数组

    c b b d
    1 1 2 2
    0 1 2 2
    0 0 1 1
    0 0 0 1 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def longestPalindromeSubseq(self, s):
        """
        :type s: str
        :rtype: int
        """
        dp = [[0] * len(s) for _ in range(len(s))]
        for i in range(len(s)):
            dp[i][i] = 1
        for i in range(len(s) - 1, -1, -1):
            for j in range(i + 1, len(s)):
                if s[i] == s[j]:
                    dp[i][j] = dp[i + 1][j - 1] + 2
                else:
                    dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])
        return dp[0][-1]

单调栈

通常是一维数组，要寻找任一个元素的右边或者左边第一个比自己大或者小的元素的位置，此时就要想到可以用单调栈了。

单调栈的本质是空间换时间，因为在遍历的过程中需要用一个栈来记录右边第一个比当前元素高的元素，优点是整个数组只需要遍历一次。

直白来说，就是用一个栈来记录遍历过的元素，因为在遍历数组的时候，不知道之前都遍历了哪些元素，以至于遍历一个元素找不到是不是之前遍历过一个更小的，所以需要用一个容器来记录遍历过的元素。

  1. 单调栈里存什么？

    单调栈里只需要存放元素的下标 i 就可以了，如果需要使用对应的元素，直接 T[i] 就可以获取。

  2. 单调栈里元素是递增？还是递减？

    如果求一个元素右边第一个更大元素，单调栈就是递增的；如果求一个元素右边第一个更小元素，单调栈就是递减的。

使用单调栈主要有三个判断条件：

  • 当前遍历的元素 T[i] < 栈顶元素 T[st.top()] 的情况
  • 当前遍历的元素 T[i] = 栈顶元素 T[st.top()] 的情况
  • 当前遍历的元素 T[i] > 栈顶元素 T[st.top()] 的情况

739. 每日温度

定义 result 数组的时候，应该直接初始化为 0，如果 result 没有更新，说明这个元素右边没有更大的元素，也就是为 0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def dailyTemperatures(self, temperatures):
        """
        :type temperatures: List[int]
        :rtype: List[int]
        """
        ans = [0] * len(temperatures)
        stack = [0]

        for i in range(1, len(temperatures)):
            # 情况一和情况二
            if temperatures[i] <= temperatures[stack[-1]]:
                stack.append(i)
            # 情况三
            else:
                while len(stack) != 0 and temperatures[i] > temperatures[stack[-1]]:
                    ans[stack[-1]] = i - stack[-1]
                    stack.pop()
                stack.append(i)
        return ans

496. 下一个更大元素Ⅰ

如果不存在对应位置就输出 -1，所以 result 数组如果某位置没有被赋值，就应该是 -1，所以初始化 -1。

在遍历 nums2 的过程中，要判断 nums2[i] 是否在 num1 中出现过，因为最后要根据 nums1 元素的下标来更新 result 数组。

没有重复元素，就可以用 map 来做映射了。根据数值快速找到下标，还可以判断 nums2[i] 是否在 nums1 中出现过。

栈头到栈底的顺序，要从小到大，也就是保持栈里的元素为递增顺序。

  1. 情况一：当前遍历的元素 T[i] < 栈顶元素 T[st.top()] 的情况

    此时满足递增栈，所以直接入栈

  2. 情况二：当前遍历的元素 T[i] = 栈顶元素 T[st.top()] 的情况

    如果相等依然直接入栈，因为要求的是右边第一个比自己大的元素

  3. 情况三：当前遍历的元素 T[i] > 栈顶元素 T[st.top()] 的情况

    此时如果入栈就不满足递增栈了，判断栈顶元素是否在 nums1 里出现过，如果出现过，开始记录结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution(object):
    def nextGreaterElement(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: List[int]
        """
        res = [-1] * len(nums1)
        stack = [0]

        for i in range(1, len(nums2)):
            # 情况一和情况二
            if nums2[i] <= nums2[stack[-1]]:
                stack.append(i)
            # 情况三
            else:
                while len(stack) != 0 and nums2[i] > nums2[stack[-1]]:
                    if nums2[stack[-1]] in nums1:
                        index = nums1.index(nums2[stack[-1]])
                        res[index] = nums2[i]
                    stack.pop()
                stack.append(i)
        return res

503. 下一个更大元素Ⅱ

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def nextGreaterElements(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        res = [-1] * len(nums)
        stack = [0]

        for i in range(len(nums) * 2):
            while (len(stack) != 0 and nums[i % len(nums)] > nums[stack[-1]]):
                res[stack[-1]] = nums[i % len(nums)]
                stack.pop()
            stack.append(i % len(nums))
        return res

42. 接雨水

单调栈就是保持栈内元素有序。接雨水正需要寻找一个元素，右边最大元素以及左边最大元素，来计算雨水面积。

  1. 首先单调栈是按行方向来计算雨水

  2. 使用单调栈内元素的顺序

    从栈头（元素从栈头弹出）到栈底的顺序应该是从小到大的顺序。

  3. 遇到相同高度的柱子怎么办？

    遇到相同元素，更新栈内下标，就是将栈里元素（旧下标）弹出，将新元素（新下标）加入栈中。

    因为要求宽度的时候，如果遇到相同高度的柱子，需要使用最右边的柱子来计算宽度。

  4. 栈里要保存什么数值

    使用单调栈，也是通过长 * 宽来计算雨水面积的。

    长就是通过柱子的高度来计算，宽就是通过柱子之间的下标来计算。

以下逻辑主要有三种情况：

  • 情况一：当前遍历的元素（柱子）高度 < 栈顶元素的高度 height[i] < height[st.top()]
  • 情况二：当前遍历的元素（柱子）高度 = 栈顶元素的高度 height[i] == height[st.top()]
  • 情况三：当前遍历的元素（柱子）高度 > 栈顶元素的高度 height[i] > height[st.top()]
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
class Solution(object):
    def trap(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        res = 0
        stack = [0]

        for i in range(1, len(height)):
            # 情况一
            if height[i] < height[stack[-1]]:
                stack.append(i)

            # 情况二
            elif height[i] == height[stack[-1]]:
                stack.pop()
                stack.append(i)
            
            # 情况三
            else:
                while stack and height[i] > height[stack[-1]]:
                    # 栈顶就是中间柱子
                    mid_height = height[stack[-1]]
                    stack.pop()
                    if stack:
                        right_height = height[i]
                        left_height = height[stack[-1]]
                        # 两侧的较矮一方的高度 - 凹槽底部高度
                        h = min(right_height, left_height) - mid_height
                        # 凹槽右侧下标 - 凹槽左侧下标 - 1：只求中间宽度
                        w = i - stack[-1] - 1
                        # 体积：高 * 宽
                        res += h * w
                stack.append(i)
        return res

84. 柱状图中最大的矩形

本题要找每个柱子左右两边第一个小于该柱子的柱子，所以从栈头（元素从栈头弹出）到栈底的顺序应该是从大到小的顺序。

只有栈里从大到小的顺序，才能保证栈顶元素找到左右两边第一个小于栈顶元素的柱子。

本题单调栈的顺序正好与接雨水反过来。

栈顶和栈底的下一个元素以及要入栈的三个元素组成了要求最大面积的高度和宽度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution(object):
    def largestRectangleArea(self, heights):
        """
        :type heights: List[int]
        :rtype: int
        """
        res = 0
        stack = [0]
        # 输入数组首尾各补上一个0，原首尾两个柱子可作为核心柱进行最大面积尝试
        heights.insert(0, 0)
        heights.append(0)

        for i in range(1, len(heights)):
            # 情况一
            if heights[i] > heights[stack[-1]]:
                stack.append(i)
            
            # 情况二
            elif heights[i] == heights[stack[-1]]:
                stack.pop()
                stack.append(i)
            
            # 情况三
            else:
                while stack and heights[i] < heights[stack[-1]]:
                    # 栈顶就是中间的柱子
                    mid_height = stack[-1]
                    stack.pop()
                    if stack:
                        left_height = stack[-1]
                        right_height = i
                        width = right_height - left_height - 1
                        height = heights[mid_height]
                        res = max(res, width * height)
                stack.append(i)
        return res

背包问题

二维

有 n 件物品和一个最多能背重量为 w 的背包。第i件物品的重量是 weight[i]，得到的价值是 value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

动态规划五部曲：

  1. 确定 dp 数组以及下标的含义

    i 表示物品、j 表示背包容量

    dp[i][j]：表示从下标为 [0 - i] 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。

  2. 确定递推公式

    不放物品 i：背包容量为 j，里面不放物品 i 的最大价值是 dp[i - 1][j]。

    放物品 i：背包空出物品 i 的容量后，背包容量为 j - weight[i]，dp[i - 1][j - weight[i]]为背包容量 j - weight[i] 且不放物品 i 的最大价值，那么 dp[i - 1][j - weight[i]] + value[i](物品的价值)，就是背包放物品 i 得到的最大价值。

    递归公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

  3. dp 数组如何初始化

    dp[i][0] = 0, dp[0][j] = value[0]

  4. 确定遍历顺序

    先遍历物品，再遍历背包重量。

  5. 举例推导 dp 数组

    0 1 2 3 4
    0 15 15 15 15
    0 15 15 20 15
    0 15 15 20 35

一维

在使用二维数组的时候，递推公式：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])

其实可以发现如果把 dp[i - 1] 那一层拷贝到 dp[i] 上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i])

与其把 dp[i - 1] 这一层拷贝到 dp[i] 上，不如只用一个一维数组（一维数组也可以理解为一个滚动数组）。

动规五部曲：

  1. 确定 dp 数组的定义

    在一堆 dp 数组中，dp[j] 表示：容量为 j 的背包，所背的物品价值可以最大为 dp[j]。

  2. 一维 dp 数组的递推公式

    递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])

  3. 一维 dp 数组如何初始化

    关于初始化，一定要和 dp 数组的定义吻合，否则到递推公式的时候就会越来越乱。

    假设物品价值都是大于 0 的，所以 dp 数组初始化的时候，都初始化为 0 就可以了。

  4. 遍历顺序

    二维 dp 遍历的时候，背包容量从小到大，而一维 dp 遍历的时候，背包是从大到小。

    举例：物品 0 的重量 weight[0] = 1，价值 value[0] = 15

    正序遍历：

    dp[1] = dp[1 - weight[0]] + value[0] = 15

    dp[2] = dp[2 - weight[0]] + value[0] = 30

    此时 dp[2] 就已经是 30 了，意味着物品 0 被放入了两次，所以不能正序遍历。

    倒序遍历：

    dp[2] = dp[2 - weight[0]] + value[0] = 15 （dp数组已经都初始化为0）

    dp[1] = dp[1 - weight[0]] + value[0] = 15

    所以从后往前循环，每次取得状态不会和之前取得状态重合，这样每种物品就只取一次了。

  5. 举例推导 dp 数组

    用物品 0，遍历背包：0 15 15 15 15

    用物品 1，遍历背包：0 15 15 20 35

    用物品 2，遍历背包：0 15 15 20 35

完全背包

完全背包和 0-1 背包问题唯一不同的地方就是每种物品有无限件。

动规五部曲：

  1. 确定 dp 数组的定义

    dp[i][j] 表示从下标为 [0-i] 的物品，每个物品可以取无限次，放进容量为 j 的背包，价值总和最大是多少。

  2. 一维 dp 数组的递推公式

    不放物品 i：背包容量为 j，里面不放物品 i 的最大价值是 dp[i - 1][j]

    放物品 i：背包空出物品 i 的容量后，背包容量为 j - weight[i]，dp[i - 1][j - weight[i]]为背包容量 j - weight[i] 且不放物品 i 的最大价值，那么 dp[i - 1][j - weight[i]] + value[i](物品的价值)，就是背包放物品 i 得到的最大价值。

    递推公式为：dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i])

  3. dp 数组如何初始化

    关于初始化，一定要和 dp 数组的定义吻合，否则到递推公式的时候就会越来越乱。

    dp[i][0] = 0, dp[0][j] = dp[0][j - weight[0]] + value[0]

  4. 遍历顺序

    既可以先遍历物品再遍历背包，也可以先遍历背包再遍历物品。

  5. 举例推导 dp 数组

    用物品 0，遍历背包：0 15 30 45 60

    用物品 1，遍历背包：0 15 30 45 60

    用物品 2，遍历背包：0 15 30 45 60

    因为物品 0 的性价比最高，而且在完全背包中，每一类物品都有无限个，所以有无限个物品 0，既然物品 0 性价比最高，当然优先放物品 0。

图论

算法
#Algorithm #LeetCode
LeetCode Notes
https://www.renkelin.vip/2025/02/15/Algorithm-note/
Author
Kolin
Posted on
February 15, 2025
Licensed under