日拱两卒（九）

19#

旋转图像。

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

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

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

18#

螺旋矩阵。

螺旋顺序输出。

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

5
        dx = [0, 1, 0, -1]
6
        dy = [1, 0, -1, 0]
7
        d = 0
8

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

14
        while cnt < n * m:
15
            ans.append(matrix[x][y])
16
            cnt += 1
17
            visited[x][y] = True
18
            tx, ty = x + dx[d], y + dy[d]
19
            if tx >= n or tx < 0 or ty >= m or ty < 0 or visited[tx][ty]:
20
                d = (d + 1) % 4
21
            tx, ty = x + dx[d], y + dy[d]
22
            x, y = tx, ty
23

24

25
        return ans

17#

矩阵置零。

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

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

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

以为会有很巧妙的做法。

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

1
class Solution:
2
    def setZeroes(self, matrix: List[List[int]]) -> None:
3
        n, m = len(matrix), len(matrix[0])
4
        first_row_zero, first_col_zero = 0, 0
5
        for j in range(m):
6
            first_row_zero = first_row_zero or not matrix[0][j]
7
        for i in range(n):
8
            first_col_zero = first_col_zero or not matrix[i][0]
9
        for i in range(1, n):
10
            for j in range(1, m):
11
                if not matrix[i][j]:
12
                    matrix[0][j], matrix[i][0] = 0, 0
13
        for i in range(1, n):
14
            for j in range(1, m):
15
                if not matrix[0][j] or not matrix[i][0]:
16
                    matrix[i][j] = 0
17
        if first_row_zero:
18
            for j in range(m):
19
                matrix[0][j] = 0
20
        if first_col_zero:
21
            for row in matrix:
22
                row[0] = 0