1135 words
6 minutes
日拱两卒（九）
2026-08-10
Leetcode

20#

旋转图像。

顺时针旋转90度。等价于沿副对角线对折，然后上下对折。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n, m = len(matrix), len(matrix[0])
        for i in range(n):
            for j in range(n - 1 - i):
                matrix[i][j], matrix[n - 1 - j][n - 1 - i] = matrix[n - 1 - j][n - 1 - i], matrix[i][j]


        for i in range(n // 2):
            for j in range(n):
                matrix[i][j], matrix[n - 1 - i][j] = matrix[n - 1 - i][j], matrix[i][j]

19#

螺旋矩阵。

螺旋顺序输出。

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ans = []


        dx = [0, 1, 0, -1]
        dy = [1, 0, -1, 0]
        d = 0


        x, y = 0, 0
        cnt = 0
        n, m = len(matrix), len(matrix[0])
        visited = [[False for _ in range(m)] for _ in range(n)]


        while cnt < n * m:
            ans.append(matrix[x][y])
            cnt += 1
            visited[x][y] = True
            tx, ty = x + dx[d], y + dy[d]
            if tx >= n or tx < 0 or ty >= m or ty < 0 or visited[tx][ty]:
                d = (d + 1) % 4
            tx, ty = x + dx[d], y + dy[d]
            x, y = tx, ty




        return ans

18#

矩阵置零。

如果一个元素为零，把它所在的一行和一列都变成零。

O(n + m)空间的做法很容易想到，记录每一行和每一列里是否有零。

这题的考察点很莫名其妙，题干说有无常数空间做法。

以为会有很巧妙的做法。

题解的方法也感觉没有很巧妙，就是把记录的东西放在每一行和每一列的第一个元素，再特殊处理第一行与第一列。

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        n, m = len(matrix), len(matrix[0])
        first_row_zero, first_col_zero = 0, 0
        for j in range(m):
            first_row_zero = first_row_zero or not matrix[0][j]
        for i in range(n):
            first_col_zero = first_col_zero or not matrix[i][0]
        for i in range(1, n):
            for j in range(1, m):
                if not matrix[i][j]:
                    matrix[0][j], matrix[i][0] = 0, 0
        for i in range(1, n):
            for j in range(1, m):
                if not matrix[0][j] or not matrix[i][0]:
                    matrix[i][j] = 0
        if first_row_zero:
            for j in range(m):
                matrix[0][j] = 0
        if first_col_zero:
            for row in matrix:
                row[0] = 0

17#

缺失的第一个正数。

把每个数换到对应的位置，最多n个位置。

class Solution:
    def firstMissingPositive(self, nums: List[int]) -> int:
        n = len(nums)
        for i in range(n):
            while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
                j = nums[i] - 1
                nums[i], nums[j] = nums[j], nums[i]


        for i in range(n):
            if nums[i] != i + 1:
                return i + 1


        return n + 1

16#

除了自身以外数组的乘积。

前缀积和后缀积。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        n = len(nums)
        pre = [1 for _ in range(n + 2)]
        suf = [1 for _ in range(n + 2)]
        for i in range(n):
            pre[i + 1] = pre[i] * nums[i]
        for i in range(n, 1, -1):
            suf[i] = suf[i + 1] * nums[i - 1]
        ans = []
        for i in range(1, n + 1, 1):
            ans.append(pre[i - 1] * suf[i + 1])
        return ans

15#

轮转数组。

向右K位。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        def reverse(l, r):
            i, j = l, r
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1
        n = len(nums)
        k %= n
        reverse(0, n - 1 - k)
        reverse(n - k, n - 1)
        reverse(0, n - 1)

14#

合并区间。

左端点排序完贪心。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x : (x[0], x[1]))


        ans = []
        l, r = intervals[0][0], intervals[0][1]
        i = 1
        n = len(intervals)
        while i < n:
            if intervals[i][0] > r:
                ans.append([l, r])
                l, r = intervals[i][0], intervals[i][1]
            else:
                r = max(r, intervals[i][1])
            i += 1
        ans.append([l, r])
        return ans

13#

最大子数组和。

数组里可能有负数。

把j那层循环优化成维护一个最小值。

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        s = [0 for _ in range(n + 1)]
        for i in range(n):
            s[i + 1] = s[i] + nums[i]
        pre_min = [1000000 for _ in range(n + 1)]
        pre_min[0] = s[0]
        ans = -1000000
        for i in range(1, n + 1):
            ans = max(ans, s[i] - pre_min[i - 1])
            pre_min[i] = min(pre_min[i - 1], s[i])
        return ans

12#

最小覆盖子串。

返回最短的子串，包含目标串的所有字母。

滑动窗口维护每个字母的出现次数，右端点固定了以后左端点就可以贪心往右走。

Python要求字典里的Key得初始化才能用，很麻烦。

for i in range(26):
    cnt[i] = 0
for i in range(32, 32 + 26):
    cnt[i] = 0

如果直接用cnt = {}需要写这种初始化代码，用defaultdict(int)会默认有初始值0。

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans = ""
        n = len(s)
        m = len(t)


        target = defaultdict(int)
        for i in range(m):
            target[ord(t[i]) - ord('A')] += 1


        # [l, r)
        l, r = 0, 0
        cnt = defaultdict(int)


        def check() -> bool:
            for c in target:
                if target[c] > cnt[c]:
                    return False
            return True


        while True:
            if r <= n - 1:
                r += 1
                cnt[ord(s[r - 1]) - ord('A')] += 1
            while check():
                if r - l < len(ans) or ans == "":
                    ans = s[l:r]
                cnt[ord(s[l]) - ord('A')] -= 1
                l += 1
            if r == n:
                break


        return ans

11#

滑动窗口最大值。

单调队列。

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


        ans = []
        q = deque()
        for r in range(n):
            l = r - k + 1
            while q and q[0] < l:
                q.popleft()
            while q and nums[q[-1]] <= nums[r]:
                q.pop()
            q.append(r)


            if l >= 0:
                ans.append(nums[q[0]])


        return ans
GPT.c
日拱两卒（八）
© 2026 Cabbage74. All Rights Reserved.