LeetCode 100题-1

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

# 递归快速幂算法
# https://zhuanlan.zhihu.com/p/95902286
# 7的10次方 = 10个7相乘 = (5个7相乘)的平方 = 7的平方的平方再乘以7
# 发现乘法的次数越来越少


# 非递归快速幂算法
# 结合二进制的思想 7^10=7^(1010)=7^(1000)*7(0010)
def qpow(a, n):
    ans = 1
    while n:
        if n&1:        //如果n的当前末位为1
            ans *= a  //ans乘上当前的a
        a *= a        //因为右移所以a先自乘
        n >>= 1       //n往右移一位
    return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

# 二分查找
left, right = 1, INT_MAX
while left <= right:
    mid = left + ((right - left) >> 1)    #>>1相当于除以2
    if 。。。:
        ans = mid
        if mid == INT_MAX:
            break
        left = mid + 1
    else:
        right = mid - 1

1
2
3

a = 6
'{0:.2f}'.format(a)    #输出 6.00
'{0:b}'.format(a)    #输出 '110'

1
2

int(二进制表示, 2)    #将二进制转为十进制
bin(十进制)[2:]    #将十进制转为二进制

1
2
3
4
5
6
7

x = 10    #'1010'
y = 11    #'1011'
# result = 21    #'10101'
while y:
    a = x^y
    b = (x&y) << 1
    x, y = a, b

1
2
3
4
5
6

def countOnes(x: int) -> int:
    ones = 0
    while x > 0:
        x &= (x - 1)    #相邻两个数的二进制表示做逻辑与运算可以去掉最后面的1
        ones += 1
    return ones

1
2
3
4
5
6
7
8

def recursively_check(current_node=head):
    if current_node is not None:
        if not recursively_check(current_node.next):    #层层深入到尾节点
            return False
        if self.front_pointer.val != current_node.val:    #比较前后两个节点的值
            return False
        self.front_pointer = self.front_pointer.next    #前节点向前移动
    return True    #return到第二个if那里

1
2
3
4
5
6
7
8
9

inorder(node){
    inorder(node.left)
    """
    中间这里可以进行节点的存储 restorelist.append(node.val)
    或者
    控制链表节点的指向
    """
    inorder(node.right)
}

1
2
3
4
5

if mid * mid <= x:
    ans = mid
    l = mid + 1
else:
    r = mid - 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

from typing import List


class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # 使用哈希表存储已遍历过的数字及其下标
        # key: 数字值, value: 该数字的下标
        hashmap = {}

        # 遍历数组
        for i, num in enumerate(nums):
            # 计算需要的另一个数
            complement = target - num

            # 检查 complement 是否已经在哈希表中
            if complement in hashmap:
                # 找到了！返回另一个数的下标和当前下标
                return [hashmap[complement], i]

            # 没找到，将当前数字和下标存入哈希表
            hashmap[num] = i

        # 无解（题目保证有唯一解，所以不会走到这里）
        return []


# 测试用例
assert Solution().twoSum([2, 7, 11, 15], 9) == [0, 1]
assert Solution().twoSum([3, 2, 4], 6) == [1, 2]
assert Solution().twoSum([3, 3], 6) == [0, 1]
# 手动推导 [2, 7, 11, 15], target=9：
#   i=0, num=2, complement=7, hashmap={}, 7不在，存入 {2:0}
#   i=1, num=7, complement=2, hashmap={2:0}, 2在！返回 [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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

from typing import List
from collections import defaultdict


class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        # 使用字典存储分组结果
        # key: 排序后的字符串（作为字母异位词的"签名"）
        # value: 具有相同签名的字符串列表
        groups = defaultdict(list)

        # 遍历每个字符串
        for s in strs:
            # 1. 将字符串转换为列表并排序，得到标准形式
            # 例如: "eat" -> ['e', 'a', 't'] -> "aet"
            #      "tea" -> ['t', 'e', 'a'] -> "aet"
            # 两者排序后都是 "aet"，说明它们是字母异位词
            key = ''.join(sorted(s))

            # 2. 将当前字符串加入对应的分组
            groups[key].append(s)

        # 3. 返回所有分组（字典的值列表）
        return list(groups.values())


# 测试用例
assert Solution().groupAnagrams(["eat", "tea", "tan", "ate", "nat", "bat"]) == [["bat"], ["nat", "tan"], ["ate", "eat", "tea"]]
assert Solution().groupAnagrams([""]) == [[""]]
assert Solution().groupAnagrams(["a"]) == [["a"]]

# 手动推导 ["eat", "tea", "tan", "ate", "nat", "bat"]：
#   "eat"  -> 排序为 "aet" -> groups["aet"] = ["eat"]
#   "tea"  -> 排序为 "aet" -> groups["aet"] = ["eat", "tea"]
#   "tan"  -> 排序为 "ant" -> groups["ant"] = ["tan"]
#   "ate"  -> 排序为 "aet" -> groups["aet"] = ["eat", "tea", "ate"]
#   "nat"  -> 排序为 "ant" -> groups["ant"] = ["tan", "nat"]
#   "bat"  -> 排序为 "abt" -> groups["abt"] = ["bat"]
# 结果: [["eat", "tea", "ate"], ["tan", "nat"], ["bat"]]

 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

from typing import List


class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        # 如果数组为空，直接返回0
        if not nums:
            return 0

        # 1. 将所有数字存入哈希集合，实现 O(1) 的查找
        num_set = set(nums)
        longest_streak = 0

        # 2. 遍历数组中的每一个数字
        for num in num_set:
            # 3. 只有当 num-1 不在集合中时，num 才是序列的起点
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                # 4. 向后查找连续的数字
                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1

                # 5. 更新最大长度
                longest_streak = max(longest_streak, current_streak)

        return longest_streak


assert Solution().longestConsecutive([100, 4, 200, 1, 3, 2]) == 4
assert Solution().longestConsecutive([0, 3, 7, 2, 5, 8, 4, 6, 0, 1]) == 9
assert Solution().longestConsecutive([]) == 0
assert Solution().longestConsecutive([1]) == 1
assert Solution().longestConsecutive([1, 2, 0, 1]) == 3
# 存入集合：num_set = {100, 4, 200, 1, 3, 2}。
# 遍历过程：
#   遇到 100：检查 99 是否在集合中？不在。说明 100 是起点。向后找 101（不在），序列长度为 1。
#   遇到 4：检查 3 是否在集合中？在。说明 4 不是起点，跳过。
#   遇到 200：检查 199 是否在集合中？不在。说明 200 是起点。向后找 201（不在），序列长度为 1。
#   遇到 1：检查 0 是否在集合中？不在。说明 1 是起点。向后找 2（在）、3（在）、4（在）、5（不在）。序列长度为 4。
#   遇到 3：检查 2 是否在集合中？在。跳过。
#   遇到 2：检查 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
42
43
44

from typing import List


class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        使用双指针原地移动零元素

        思路：
        - left 指针指向已处理区域的最后一个非零元素
        - right 指针向后扫描，寻找非零元素
        - 找到后与 left+1 位置交换，left 右移
        - 这样所有非零元素会被移动到数组前面，保持相对顺序
        """
        left = 0  # left 指针：已处理区域的边界（不含零）

        for right in range(len(nums)):
            # 当 right 指向非零元素时，将其移动到 left 位置
            if nums[right] != 0:
                # 交换元素（如果 left 和 right 指向同一位置则无操作）
                nums[left], nums[right] = nums[right], nums[left]
                left += 1  # left 右移，指向下一个待填充位置


# 测试用例
nums1 = [0, 1, 0, 3, 12]
Solution().moveZeroes(nums1)
assert nums1 == [1, 3, 12, 0, 0]

nums2 = [0]
Solution().moveZeroes(nums2)
assert nums2 == [0]

nums3 = [1, 0, 0, 2, 3]
Solution().moveZeroes(nums3)
assert nums3 == [1, 2, 3, 0, 0]

# 手动推导 [0, 1, 0, 3, 12]：
#   left = 0, right = 0: nums[0] = 0，跳过
#   left = 0, right = 1: nums[1] = 1 != 0，交换 nums[0] 和 nums[1] -> [1, 0, 0, 3, 12]，left = 1
#   left = 1, right = 2: nums[2] = 0，跳过
#   left = 1, right = 3: nums[3] = 3 != 0，交换 nums[1] 和 nums[3] -> [1, 3, 0, 0, 12]，left = 2
#   left = 2, right = 4: nums[4] = 12 != 0，交换 nums[2] 和 nums[4] -> [1, 3, 12, 0, 0]，left = 3
# 最终：[1, 3, 12, 0, 0]

 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

from typing import List


class Solution:
    def maxArea(self, height: List[int]) -> int:
        """
        使用双指针求最大容器容量

        思路：
        - 容器的容量 = 两端中较短的那一条 * 两端之间的距离
        - 初始时左右指针分别在两端
        - 移动较短的那一端，因为容量受限于较短的边
        - 不断更新最大容量
        """
        left = 0
        right = len(height) - 1
        max_area = 0

        while left < right:
            # 计算当前容器的容量
            # 高度取两端中的较小值，宽度是两端的距离
            current_height = min(height[left], height[right])
            current_width = right - left
            max_area = max(max_area, current_height * current_width)

            # 移动较短的那一端，以寻找更大的容量
            if height[left] < height[right]:
                left += 1
            else:
                right -= 1

        return max_area


# 测试用例
assert Solution().maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]) == 49
assert Solution().maxArea([1, 1]) == 1
assert Solution().maxArea([4, 3, 2, 1, 4]) == 16

# 手动推导 [1, 8, 6, 2, 5, 4, 8, 3, 7]：
#   left=0, right=8: 高度=min(1,7)=1，容量=1*8=8，移动left（1较小）
#   left=1, right=8: 高度=min(8,7)=7，容量=7*7=49（最大），移动right（7较小）
#   left=1, right=7: 高度=min(8,3)=3，容量=3*6=18，移动right（3较小）
#   left=1, right=6: 高度=min(8,8)=8，容量=8*5=40，移动right（相等，移动任意）
#   left=1, right=5: 高度=min(8,4)=4，容量=4*4=16...
#   最终最大容量为 49

 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

from typing import List


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        """
        使用排序 + 双指针找出所有不重复的三数之和为零的三元组

        思路：
        1. 先对数组排序
        2. 固定一个数 nums[i]，然后在右侧使用双指针找两数之和等于 -nums[i]
        3. 通过排序和跳过重复值来避免重复三元组
        """
        nums.sort()  # 排序
        result = []

        for i in range(len(nums) - 2):
            # 跳过重复的 nums[i]，避免重复三元组
            if i > 0 and nums[i] == nums[i - 1]:
                continue

            # 如果最小的三数之和都大于 0，则不可能有三数之和为 0
            if nums[i] + nums[i + 1] + nums[i + 2] > 0:
                break

            # 如果 nums[i] 加上最大的两个数还小于 0，直接跳过
            if nums[i] + nums[-2] + nums[-1] < 0:
                continue

            # 双指针查找剩余两数之和等于 -nums[i]
            left = i + 1
            right = len(nums) - 1

            while left < right:
                total = nums[i] + nums[left] + nums[right]

                if total == 0:
                    result.append([nums[i], nums[left], nums[right]])

                    # 跳过重复的 nums[left]
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    # 跳过重复的 nums[right]
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1

                    left += 1
                    right -= 1

                elif total < 0:
                    left += 1  # 总和太小，增大 left
                else:
                    right -= 1  # 总和太大，减小 right

        return result


# 测试用例
assert Solution().threeSum([-1, 0, 1, 2, -1, -4]) == [[-1, -1, 2], [-1, 0, 1]]
assert Solution().threeSum([0, 1, 1]) == []
assert Solution().threeSum([0, 0, 0]) == [[0, 0, 0]]
assert Solution().threeSum([-2, 0, 0, 2, 2]) == [[-2, 0, 2]]

# 手动推导 [-1, 0, 1, 2, -1, -4] 排序后 [-4, -1, -1, 0, 1, 2]：
#   i=0, nums[i]=-4:
#       left=1, right=5: total=-4+(-1)+2=-3 < 0, left++
#       left=2, right=5: total=-4+(-1)+2=-3 < 0, left++
#       left=3, right=5: total=-4+0+2=-2 < 0, left++
#       left=4, right=5: total=-4+1+2=-1 < 0, left++ -> left=5 退出
#   i=1, nums[i]=-1:
#       left=2, right=5: total=-1+(-1)+2=0, 找到 [-1,-1,2]
#       left=3, right=4: total=-1+0+1=0, 找到 [-1,0,1]
#   i=2, nums[i]=-1，与前一个相同，跳过
#   结果：[[-1,-1,2], [-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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        """
        使用单调栈（或双指针）计算能接的雨水总量

        方法一：单调栈
        思路：
        - 用栈存储高度的索引
        - 当遇到比栈顶高的高度时，说明可以形成凹槽
        - 计算凹槽能接的雨水量
        """
        stack = []  # 存储索引
        water = 0

        for i in range(len(height)):
            # 当栈不为空且当前高度大于栈顶高度时，处理凹槽
            while stack and height[i] > height[stack[-1]]:
                h = height[stack.pop()]  # 凹槽底部高度

                # 如果栈为空，说明没有左边界，无法接雨水
                if not stack:
                    break

                # 左边界是栈中新的栈顶，右边界是当前索引
                left = stack[-1]
                right = i
                curr_height = min(height[left], height[right]) - h

                # 计算雨水量：高度差 * 宽度
                water += curr_height * (right - left - 1)

            stack.append(i)

        return water

    def trap_two_pointers(self, height: List[int]) -> int:
        """
        方法二：双指针
        思路：
        - 每个位置能接的雨水，由其左边最高和右边最高中的较小值决定
        - 使用双指针从两端向中间遍历
        - 时间 O(n)，空间 O(1)
        """
        if not height:
            return 0

        left = 0
        right = len(height) - 1
        left_max = height[left]
        right_max = height[right]
        water = 0

        while left < right:
            # 更新左右两侧的最大高度
            if height[left] > left_max:
                left_max = height[left]
            if height[right] > right_max:
                right_max = height[right]

            # 从较矮的一侧计算雨水
            if height[left] < height[right]:
                # 左边较矮，当前位置能接的雨水 = 左边最大高度 - 当前高度
                water += left_max - height[left]
                left += 1
            else:
                # 右边较矮或相等
                water += right_max - height[right]
                right -= 1

        return water


# 测试用例
assert Solution().trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]) == 6
assert Solution().trap([4, 2, 0, 3, 2, 5]) == 9
assert Solution().trap([]) == 0
assert Solution().trap([1, 0, 1]) == 1
assert Solution().trap([3, 0, 2, 0, 4]) == 7

# 手动推导 [0,1,0,2,1,0,1,3,2,1,2,1]（方法一单调栈）：
#   i=0: stack=[0]
#   i=1: height[1]=1 > height[0]=0，弹出0，stack空，无法接水，入栈1
#   i=2: height[2]=0 < height[1]=1，stack=[1,2]
#   i=3: height[3]=2 > height[2]=0，弹出2，left=1，curr_height=min(1,2)-0=1，water+=1*(3-1-1)=1
#       继续：height[3]=2 > height[1]=1，弹出1，stack空，无法接水，入栈3
#   i=4: height[4]=1 < height[3]=2，stack=[3,4]
#   i=5: height[5]=0 < height[4]=1，stack=[3,4,5]
#   i=6: height[6]=1 > height[5]=0，弹出5，left=3，curr_height=min(2,1)-0=1，water+=1*(6-3-1)=2，总计3
#       继续：height[6]=1 == height[4]=1，弹出4，left=3，curr_height=min(2,2)-1=0，water不变
#       继续：height[6]=1 < height[3]=2，入栈6，stack=[3,6]
#   ...以此类推，最终water=6

 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

from typing import List


class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        """
        使用滑动窗口求无重复字符的最长子串长度

        思路：
        - 维护一个窗口 [left, right]，窗口内没有重复字符
        - 用哈希集合记录窗口内出现过的字符
        - right 向右扩展窗口，遇到重复字符时 left 向右收缩窗口
        - 每次更新最大长度
        """
        char_set = set()  # 窗口内的字符集合
        left = 0
        max_len = 0

        for right in range(len(s)):
            # 如果当前字符已在窗口中，不断移动 left 收缩窗口
            while s[right] in char_set:
                char_set.remove(s[left])
                left += 1

            # 将当前字符加入窗口
            char_set.add(s[right])

            # 更新最大长度
            max_len = max(max_len, right - left + 1)

        return max_len


# 测试用例
assert Solution().lengthOfLongestSubstring("abcabcbb") == 3
assert Solution().lengthOfLongestSubstring("bbbbb") == 1
assert Solution().lengthOfLongestSubstring("pwwkew") == 3
assert Solution().lengthOfLongestSubstring("") == 0
assert Solution().lengthOfLongestSubstring(" ") == 1

# 手动推导 "abcabcbb"：
#   right=0, s[0]='a': set={}, 'a'不在，加入 -> set={'a'}, max_len=1
#   right=1, s[1]='b': 'b'不在，加入 -> set={'a','b'}, max_len=2
#   right=2, s[2]='c': 'c'不在，加入 -> set={'a','b','c'}, max_len=3
#   right=3, s[3]='a': 'a'在，移除s[left]=s[0]='a', left=1 -> set={'b','c'}, 'a'不在了，加入 -> set={'a','b','c'}, max_len=3
#   right=4, s[4]='b': 'b'在，移除s[left]=s[1]='b', left=2 -> set={'a','c'}, 'b'不在了，加入 -> set={'a','b','c'}, max_len=3
#   right=5, s[5]='c': 'c'在，移除s[left]=s[2]='c', left=3 -> set={'a','b'}, 'c'不在了，加入 -> set={'a','b','c'}, max_len=3
#   right=6, s[6]='b': 'b'在，移除s[left]=s[3]='a', left=4 -> set={'b','c'}, 'b'还在，移除s[4]='b', left=5 -> set={'c'}, 'b'不在了，加入 -> set={'b','c'}, max_len=3
#   right=7, s[7]='b': 'b'在，移除s[left]=s[5]='c', left=6 -> set={'b'}, 'b'还在，移除s[6]='b', left=7 -> set={}, 'b'不在了，加入 -> set={'b'}, max_len=3
# 结果：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
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

from typing import List
from collections import Counter


class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        """
        使用滑动窗口找到 s 中所有 p 的异位词的起始索引

        思路：
        - 异位词 = 字符组成相同，顺序不同
        - 维护一个长度为 len(p) 的滑动窗口
        - 比较窗口内字符的频率与 p 的字符频率是否一致
        - 用计数器记录差异，避免每次都比较整个频率表
        """
        if len(s) < len(p):
            return []

        result = []
        p_len = len(p)

        # 统计 p 中每个字符的出现次数
        p_count = [0] * 26
        # 统计窗口中每个字符的出现次数
        window_count = [0] * 26

        for ch in p:
            p_count[ord(ch) - ord('a')] += 1

        # 初始化窗口：先填入前 p_len 个字符
        for i in range(p_len):
            window_count[ord(s[i]) - ord('a')] += 1

        # 检查初始窗口是否匹配
        if window_count == p_count:
            result.append(0)

        # 滑动窗口：每次右移一位
        for i in range(p_len, len(s)):
            # 窗口右端加入新字符
            window_count[ord(s[i]) - ord('a')] += 1
            # 窗口左端移除旧字符
            window_count[ord(s[i - p_len]) - ord('a')] -= 1

            # 检查当前窗口是否匹配
            if window_count == p_count:
                result.append(i - p_len + 1)

        return result


# 测试用例
assert Solution().findAnagrams("cbaebabacd", "abc") == [0, 6]
assert Solution().findAnagrams("abab", "ab") == [0, 1, 2]
assert Solution().findAnagrams("a", "ab") == []
assert Solution().findAnagrams("aa", "bb") == []

# 手动推导 s="cbaebabacd", p="abc"：
#   p_count = [1,1,1,0,...]（a:1, b:1, c:1）
#   初始窗口 s[0:3]="cba" -> window_count = [1,1,1,0,...]，匹配！result=[0]
#   i=3: 加入'e'，移除'c' -> 窗口"bae" -> [1,1,0,0,1,...]，不匹配
#   i=4: 加入'b'，移除'b' -> 窗口"aeb" -> [1,1,0,0,1,...]，不匹配
#   i=5: 加入'a'，移除'a' -> 窗口"eba" -> [1,1,0,0,1,...]，不匹配
#   i=6: 加入'b'，移除'e' -> 窗口"bab" -> [1,2,0,...]，不匹配
#   i=7: 加入'a'，移除'b' -> 窗口"aba" -> [2,1,0,...]，不匹配
#   i=8: 加入'c'，移除'a' -> 窗口"bac" -> [1,1,1,...]，匹配！result=[0,6]
#   i=9: 加入'd'，移除'b' -> 窗口"acd" -> [1,0,1,1,...]，不匹配
# 结果：[0, 6]

 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

from typing import List
from collections import defaultdict


class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        """
        使用前缀和 + 哈希表统计和为 k 的子数组个数

        思路：
        - 前缀和：prefix[i] 表示 nums[0..i-1] 的元素之和
        - 子数组 nums[i..j] 的和 = prefix[j+1] - prefix[i]
        - 如果 prefix[j+1] - prefix[i] = k，则 prefix[i] = prefix[j+1] - k
        - 用哈希表记录每个前缀和出现的次数
        - 对于每个位置，计算 prefix - k 是否在哈希表中，即有多少个子数组以当前位置结尾
        """
        # 哈希表：key=前缀和，value=该前缀和出现的次数
        prefix_count = defaultdict(int)

        # 前缀和为 0 初始化为 1（表示空数组的前缀和）
        prefix_count[0] = 1

        prefix = 0  # 当前前缀和
        result = 0  # 满足条件的子数组个数

        for num in nums:
            prefix += num  # 更新前缀和

            # 如果 prefix - k 存在于哈希表中，说明存在子数组和为 k
            # 这些子数组以当前位置结尾
            result += prefix_count[prefix - k]

            # 将当前前缀和加入哈希表
            prefix_count[prefix] += 1

        return result


# 测试用例
assert Solution().subarraySum([1, 1, 1], 2) == 2
assert Solution().subarraySum([1, 2, 3], 3) == 2
assert Solution().subarraySum([1], 0) == 0
assert Solution().subarraySum([1, -1, 1, -1], 0) == 6
assert Solution().subarraySum([0, 0, 0, 0], 0) == 10

# 手动推导 nums=[1,1,1], k=2：
#   prefix=0, prefix_count={0:1}
#   num=1: prefix=1, prefix-2=-1不在，result=0，prefix_count={0:1,1:1}
#   num=1: prefix=2, prefix-2=0在！result+=1（{0:1}表示有空数组可配合），prefix_count={0:1,1:1,2:1}
#   num=1: prefix=3, prefix-2=1在！result+=1（{1:1}表示[1]），prefix_count={0:1,1:1,2:1,3:1}
#   结果：2
#   满足条件的子数组：[1,1]（索引0-1）和[1,1]（索引1-2）

1
2
3
4
5
6

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

 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

from typing import List
from collections import deque


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """
        使用单调递减队列求滑动窗口最大值

        思路：
        - 维护一个单调递减的双端队列
        - 队列中存储数组元素的索引（不是值）
        - 队首元素始终是当前窗口的最大值
        - 入队时：移除所有小于当前元素的索引（它们不可能成为最大值）
        - 出队时：如果队首索引已超出窗口范围，则移除
        - 时间复杂度：O(n)，每个元素最多入队出队一次
        """
        if not nums or k == 0:
            return []

        result = []
        deque_max = deque()  # 存储索引，值单调递减

        for i in range(len(nums)):
            # 1. 入队：移除队列中所有小于当前元素的索引
            #    这些元素永远不会成为窗口最大值
            while deque_max and nums[deque_max[-1]] < nums[i]:
                deque_max.pop()

            # 2. 将当前索引加入队列
            deque_max.append(i)

            # 3. 出队：移除队首超出窗口范围的索引
            if deque_max[0] <= i - k:
                deque_max.popleft()

            # 4. 当窗口形成后（i >= k-1），记录当前窗口最大值
            if i >= k - 1:
                result.append(nums[deque_max[0]])

        return result


# 测试用例
assert Solution().maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]
assert Solution().maxSlidingWindow([1], 1) == [1]
assert Solution().maxSlidingWindow([1, -1], 1) == [1, -1]
assert Solution().maxSlidingWindow([9, 11], 2) == [11]
assert Solution().maxSlidingWindow([4, 2, 12, 12, 12, 12, 12, 12], 3) == [12, 12, 12, 12, 12, 12]

# 手动推导 nums=[1,3,-1,-3,5,3,6,7], k=3：
#   i=0: deque=[0] (值3) -> 窗口未形成
#   i=1: nums[1]=3 > nums[0]=1，移除0；deque=[1]。窗口未形成
#   i=2: nums[2]=-1 < 3，保留；deque=[1,2]。窗口[1,3,-1]，最大值=3 -> result=[3]
#   i=3: nums[3]=-3 < -1，保留；deque=[1,2,3]。窗口[3,-1,-3]，最大值=3 -> result=[3,3]
#   i=4: nums[4]=5 > -1 和 -3，移除2,3；deque=[4]。窗口[-1,-3,5]，最大值=5 -> result=[3,3,5]
#   i=5: nums[5]=3 < 5，保留；deque=[4,5]。窗口[-3,5,3]，最大值=5 -> result=[3,3,5,5]
#   i=6: nums[6]=6 > 5,3，移除5,4；deque=[6]。窗口[5,3,6]，最大值=6 -> result=[3,3,5,5,6]
#   i=7: nums[7]=7 > 6，移除6；deque=[7]。窗口[3,6,7]，最大值=7 -> result=[3,3,5,5,6,7]

 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

from typing import List
from collections import defaultdict


class Solution:
    def minWindow(self, s: str, t: str) -> str:
        """
        使用滑动窗口找到 s 中包含 t 所有字符的最小子串

        思路：
        - 维护一个滑动窗口 [left, right]
        - 用两个哈希表：need（t的字符需求）和 window（窗口中的字符计数）
        - 用 valid 变量记录当前窗口中满足条件的字符种类数
        - 扩大窗口：right 右移，增加窗口中的字符
        - 收缩窗口：当 valid == len(need) 时，尝试 left 右移收缩
        - 记录过程中的最小窗口
        """
        # 统计 t 中每个字符的需求次数
        need = defaultdict(int)
        for ch in t:
            need[ch] += 1

        # 窗口中字符的计数
        window = defaultdict(int)

        # 满足条件的字符种类数
        valid = 0

        # 滑动窗口边界
        left = 0
        min_len = float('inf')  # 最小窗口长度
        min_start = 0  # 最小窗口起始位置

        for right in range(len(s)):
            # 1. 扩大窗口：将 s[right] 加入窗口
            ch = s[right]
            if ch in need:
                window[ch] += 1
                if window[ch] == need[ch]:
                    valid += 1

            # 2. 收缩窗口：当窗口满足条件时，尝试左移 left
            while valid == len(need):
                # 更新最小窗口
                if right - left + 1 < min_len:
                    min_len = right - left + 1
                    min_start = left

                # 3. 尝试移出 s[left]
                left_ch = s[left]
                if left_ch in need:
                    if window[left_ch] == need[left_ch]:
                        valid -= 1  # 移除后不再满足条件
                    window[left_ch] -= 1

                left += 1

        # 返回结果（如果没找到，返回空字符串）
        return "" if min_len == float('inf') else s[min_start:min_start + min_len]


# 测试用例
assert Solution().minWindow("ADOBECODEBANC", "ABC") == "BANC"
assert Solution().minWindow("a", "a") == "a"
assert Solution().minWindow("a", "aa") == ""
assert Solution().minWindow("ab", "b") == "b"
assert Solution().minWindow("bbaa", "ab") == "baa"

# 手动推导 s="ADOBECODEBANC", t="ABC"：
#   need = {'A':1, 'B':1, 'C':1}, valid=0
#   right=0, s[0]='A' in need: window['A']=1, valid=1
#   right=1, s[1]='D' not in need
#   right=2, s[2]='O' not in need
#   right=3, s[3]='B' in need: window['B']=1, valid=2
#   right=4, s[4]='E' not in need
#   right=5, s[5]='C' in need: window['C']=1, valid=3 (满足条件！)
#   开始收缩窗口：
#     left=0, s[0]='A': window['A']=1==need['A']，valid--，window['A']=0，left=1
#     valid=2，不再等于len(need)，停止收缩
#   当前窗口 "DOBEC" (left=1, right=5)，长度=5
#   继续...
#   最终最小窗口为 "BANC"

 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

from typing import List


class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        """
        使用动态规划（Kadane 算法）求最大子数组和

        思路：
        - 遍历数组，维护两个变量：
          - current_sum：以当前元素结尾的最大子数组和
          - max_sum：全局最大子数组和
        - 对于每个元素，要么将它加入之前的子数组，要么从它开始新子数组
        - 选择两者中较大的那个：current_sum = max(num, current_sum + num)
        - 时间 O(n)，空间 O(1)
        """
        current_sum = nums[0]  # 以当前元素结尾的最大子数组和
        max_sum = nums[0]      # 全局最大子数组和

        for i in range(1, len(nums)):
            # 要么把 nums[i] 加入之前的子数组，要么从 nums[i] 重新开始
            current_sum = max(nums[i], current_sum + nums[i])
            # 更新全局最大值
            max_sum = max(max_sum, current_sum)

        return max_sum


# 测试用例
assert Solution().maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) == 6
assert Solution().maxSubArray([1]) == 1
assert Solution().maxSubArray([5, 4, -1, 7, 8]) == 23
assert Solution().maxSubArray([-1]) == -1
assert Solution().maxSubArray([-2, -1]) == -1

# 手动推导 nums=[-2,1,-3,4,-1,2,1,-5,4]：
#   i=1, num=1:  current_sum = max(1, -2+1) = max(1, -1) = 1,  max_sum = max(-2, 1) = 1
#   i=2, num=-3: current_sum = max(-3, 1-3) = max(-3, -2) = -2, max_sum = max(1, -2) = 1
#   i=3, num=4:  current_sum = max(4, -2+4) = max(4, 2) = 4,   max_sum = max(1, 4) = 4
#   i=4, num=-1: current_sum = max(-1, 4-1) = max(-1, 3) = 3,  max_sum = max(4, 3) = 4
#   i=5, num=2:  current_sum = max(2, 3+2) = max(2, 5) = 5,    max_sum = max(4, 5) = 5
#   i=6, num=1:  current_sum = max(1, 5+1) = max(1, 6) = 6,    max_sum = max(5, 6) = 6
#   i=7, num=-5: current_sum = max(-5, 6-5) = max(-5, 1) = 1,  max_sum = max(6, 1) = 6
#   i=8, num=4:  current_sum = max(4, 1+4) = max(4, 5) = 5,    max_sum = max(6, 5) = 6
# 结果：6，对应子数组 [4,-1,2,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
40
41
42
43
44
45
46
47
48
49
50
51
52

from typing import List


class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        """
        使用排序 + 遍历合并重叠区间

        思路：
        - 先按区间左端点排序
        - 遍历每个区间，与结果中最后一个区间比较：
          - 如果当前区间的左端点 <= 上一个区间的右端点，说明重叠，合并（取右端点较大值）
          - 否则不重叠，直接加入结果
        - 时间 O(n log n)，空间 O(n)
        """
        if not intervals:
            return []

        # 按左端点排序
        intervals.sort(key=lambda x: x[0])

        result = [intervals[0]]

        for i in range(1, len(intervals)):
            current = intervals[i]
            last = result[-1]

            # 当前区间的左端点 <= 上一个区间的右端点，说明重叠
            if current[0] <= last[1]:
                # 合并：右端点取较大值
                last[1] = max(last[1], current[1])
            else:
                # 不重叠，直接加入结果
                result.append(current)

        return result


# 测试用例
assert Solution().merge([[1, 3], [2, 6], [8, 10], [15, 18]]) == [[1, 6], [8, 10], [15, 18]]
assert Solution().merge([[1, 4], [4, 5]]) == [[1, 5]]
assert Solution().merge([[4, 7], [1, 4]]) == [[1, 7]]
assert Solution().merge([[1, 4], [0, 4]]) == [[0, 4]]
assert Solution().merge([[1, 4], [2, 3]]) == [[1, 4]]

# 手动推导 [[1,3],[2,6],[8,10],[15,18]]：
#   排序后：[[1,3],[2,6],[8,10],[15,18]]
#   result = [[1,3]]
#   i=1, [2,6]: 2 <= 3，重叠，合并 -> last[1] = max(3,6) = 6 -> result = [[1,6]]
#   i=2, [8,10]: 8 > 6，不重叠，加入 -> result = [[1,6],[8,10]]
#   i=3, [15,18]: 15 > 10，不重叠，加入 -> result = [[1,6],[8,10],[15,18]]
# 结果：[[1,6],[8,10],[15,18]]

 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

from typing import List


class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        """
        使用数组翻转实现原地轮转

        思路（三次翻转法）：
        - 向右轮转 k 位，等价于把后 k 个元素移到前面
        - 步骤：
          1. 先翻转整个数组
          2. 再翻转前 k 个元素
          3. 再翻转后 n-k 个元素
        - 例如 [1,2,3,4,5,6,7], k=3：
          1. 翻转全部：[7,6,5,4,3,2,1]
          2. 翻转前3个：[5,6,7,4,3,2,1]
          3. 翻转后4个：[5,6,7,1,2,3,4]
        - 时间 O(n)，空间 O(1)
        """
        n = len(nums)
        k = k % n  # k 可能大于 n，取模

        def reverse(left, right):
            """翻转 nums[left..right]"""
            while left < right:
                nums[left], nums[right] = nums[right], nums[left]
                left += 1
                right -= 1

        # 1. 翻转整个数组
        reverse(0, n - 1)
        # 2. 翻转前 k 个元素
        reverse(0, k - 1)
        # 3. 翻转后 n-k 个元素
        reverse(k, n - 1)


# 测试用例
nums1 = [1, 2, 3, 4, 5, 6, 7]
Solution().rotate(nums1, 3)
assert nums1 == [5, 6, 7, 1, 2, 3, 4]

nums2 = [-1, -100, 3, 99]
Solution().rotate(nums2, 2)
assert nums2 == [3, 99, -1, -100]

nums3 = [1, 2]
Solution().rotate(nums3, 3)
assert nums3 == [2, 1]

nums4 = [1]
Solution().rotate(nums4, 0)
assert nums4 == [1]

# 手动推导 nums=[1,2,3,4,5,6,7], k=3：
#   k = 3 % 7 = 3
#   第1步，翻转全部 [1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]
#   第2步，翻转前3个 [7,6,5,4,3,2,1] -> [5,6,7,4,3,2,1]
#   第3步，翻转后4个 [5,6,7,4,3,2,1] -> [5,6,7,1,2,3,4]
# 结果：[5,6,7,1,2,3,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
42
43
44
45
46
47
48
49
50
51
52
53
54

from typing import List


class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        """
        使用前缀乘积 + 后缀乘积求解

        思路：
        - answer[i] = i 左边所有元素的乘积 * i 右边所有元素的乘积
        - 第一遍从左到右：计算每个位置左边所有元素的乘积
        - 第二遍从右到左：计算每个位置右边所有元素的乘积，同时更新 answer
        - 用一个变量 right_product 代替后缀乘积数组，实现 O(1) 额外空间
        - 时间 O(n)，空间 O(1)（输出数组不计入）
        """
        n = len(nums)
        answer = [1] * n

        # 第一遍：计算每个位置左侧所有元素的乘积
        # answer[i] 存储 nums[0] * nums[1] * ... * nums[i-1]
        left_product = 1
        for i in range(n):
            answer[i] = left_product
            left_product *= nums[i]

        # 第二遍：从右到左，乘以每个位置右侧所有元素的乘积
        right_product = 1
        for i in range(n - 1, -1, -1):
            answer[i] *= right_product
            right_product *= nums[i]

        return answer


# 测试用例
assert Solution().productExceptSelf([1, 2, 3, 4]) == [24, 12, 8, 6]
assert Solution().productExceptSelf([-1, 1, 0, -3, 3]) == [0, 0, 9, 0, 0]
assert Solution().productExceptSelf([2, 3]) == [3, 2]
assert Solution().productExceptSelf([1, 2, 3]) == [6, 3, 2]

# 手动推导 nums=[1,2,3,4]：
#   第一遍（从左到右，计算左侧乘积）：
#     i=0: answer[0] = 1 (左侧无元素),      left_product = 1*1 = 1
#     i=1: answer[1] = 1 (左侧为1),          left_product = 1*2 = 2
#     i=2: answer[2] = 2 (左侧为1*2),        left_product = 2*3 = 6
#     i=3: answer[3] = 6 (左侧为1*2*3),      left_product = 6*4 = 24
#     answer = [1, 1, 2, 6]
#   第二遍（从右到左，乘以右侧乘积）：
#     i=3: answer[3] = 6 * 1 = 6,            right_product = 1*4 = 4
#     i=2: answer[2] = 2 * 4 = 8,            right_product = 4*3 = 12
#     i=1: answer[1] = 1 * 12 = 12,          right_product = 12*2 = 24
#     i=0: answer[0] = 1 * 24 = 24,          right_product = 24*1 = 24
#     answer = [24, 12, 8, 6]
# 结果：[24, 12, 8, 6]

 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

from typing import List


class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        """
        使用原地哈希（标记法）求缺失的第一个正数

        思路：
        - 长度为 n 的数组，缺失的第一个正数一定在 [1, n+1] 范围内
        - 利用数组本身做哈希表：让值 i 出现在索引 i-1 的位置
        - 遍历数组，将每个在 [1, n] 范围内的数放到它应该在的位置
        - 再次遍历，第一个不满足 nums[i] == i+1 的位置，答案就是 i+1
        - 如果所有位置都满足，则答案为 n+1
        - 时间 O(n)，空间 O(1)
        """
        n = len(nums)

        for i in range(n):
            # 将 nums[i] 放到正确的位置 nums[i]-1
            # 条件：nums[i] 在 [1, n] 范围内，且目标位置的值不等于当前值（避免重复导致死循环）
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                # 交换 nums[i] 和 nums[nums[i]-1]
                correct_idx = nums[i] - 1
                nums[i], nums[correct_idx] = nums[correct_idx], nums[i]

        # 找到第一个不在正确位置上的数
        for i in range(n):
            if nums[i] != i + 1:
                return i + 1

        # 所有位置都正确，缺失的是 n+1
        return n + 1


# 测试用例
assert Solution().firstMissingPositive([1, 2, 0]) == 3
assert Solution().firstMissingPositive([3, 4, -1, 1]) == 2
assert Solution().firstMissingPositive([7, 8, 9, 11, 12]) == 1
assert Solution().firstMissingPositive([1]) == 2
assert Solution().firstMissingPositive([2, 1]) == 3
assert Solution().firstMissingPositive([1, 1]) == 2

# 手动推导 nums=[3,4,-1,1]，n=4：
#   i=0, nums[0]=3: 1<=3<=4 且 nums[2]=-1!=3，交换 -> [-1,4,3,1]
#     此时 nums[0]=-1，不在 [1,4] 内，停止
#   i=1, nums[1]=4: 1<=4<=4 且 nums[3]=1!=4，交换 -> [-1,1,3,4]
#     此时 nums[1]=1: 1<=1<=4 且 nums[0]=-1!=1，交换 -> [1,-1,3,4]
#     此时 nums[1]=-1，不在 [1,4] 内，停止
#   i=2, nums[2]=3: nums[2]=3，nums[2]==2+1，已在正确位置
#   i=3, nums[3]=4: nums[3]=4，nums[3]==3+1，已在正确位置
#   数组变为 [1,-1,3,4]
#   检查：nums[0]=1=0+1 ✓, nums[1]=-1≠1+1 ✗
#   返回 2
# 结果：2

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73

from typing import List


class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        """
        使用原地标记法实现矩阵置零

        思路：
        - 使用第一行和第一列作为标记数组
        - 遍历矩阵，如果某个元素为0，则将其所在行和列的标记位置零
        - 用两个变量记录第一行和第一列是否需要置零
        - 时间 O(mn)，空间 O(1)
        """
        if not matrix or not matrix[0]:
            return

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

        # 1. 检查第一行和第一列是否需要置零
        row_zero = any(matrix[0][j] == 0 for j in range(n))
        col_zero = any(matrix[i][0] == 0 for i in range(m))

        # 2. 遍历除第一行第一列外的所有元素，标记需要置零的行和列
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == 0:
                    matrix[i][0] = 0
                    matrix[0][j] = 0

        # 3. 根据标记，将需要置零的行置零（不包括第一列）
        for i in range(1, m):
            if matrix[i][0] == 0:
                for j in range(1, n):
                    matrix[i][j] = 0

        # 4. 根据标记，将需要置零的列置零（不包括第一行）
        for j in range(1, n):
            if matrix[0][j] == 0:
                for i in range(1, m):
                    matrix[i][j] = 0

        # 5. 处理第一行和第一列
        if row_zero:
            for j in range(n):
                matrix[0][j] = 0
        if col_zero:
            for i in range(m):
                matrix[i][0] = 0


# 测试用例
matrix1 = [[1, 1, 1], [1, 0, 1], [1, 1, 1]]
Solution().setZeroes(matrix1)
assert matrix1 == [[1, 0, 1], [0, 0, 0], [1, 0, 1]]

matrix2 = [[0, 1, 2, 0], [3, 4, 5, 2], [1, 3, 1, 5]]
Solution().setZeroes(matrix2)
assert matrix2 == [[0, 0, 0, 0], [0, 4, 5, 0], [0, 3, 1, 0]]

matrix3 = [[1]]
Solution().setZeroes(matrix3)
assert matrix3 == [[1]]

matrix4 = [[0]]
Solution().setZeroes(matrix4)
assert matrix4 == [[0]]

# 手动推导 matrix = [[1,1,1],[1,0,1],[1,1,1]]：
#   row_zero = False, col_zero = False
#   遍历发现 matrix[1][1]=0，标记 matrix[1][0]=0, matrix[0][1]=0
#   根据标记置零行和列，最后 row_zero/col_zero 为 False 不需要额外处理
# 结果：[[1,0,1],[0,0,0],[1,0,1]]