48. 旋转图像

矩阵 - 图1
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]
矩阵 - 图2
示例 2：
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]] 输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

  • n == matrix.length == matrix[i].length
  • 1 <= n <= 20
  • -1000 <= matrix[i][j] <= 1000

参考
https://leetcode-cn.com/problems/delete-middle-node-lcci/solution/mian-shi-ti-0203-shan-chu-zhong-jian-jie-97ju/

498. 对角线遍历

矩阵 - 图3
给你一个大小为 m x n 的矩阵 mat ，请以对角线遍历的顺序，用一个数组返回这个矩阵中的所有元素。

示例 1：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,4,7,5,3,6,8,9]
示例 2：
输入：mat = [[1,2],[3,4]] 输出：[1,2,3,4]

提示：

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 104
  • 1 <= m * n <= 104
  • -105 <= mat[i][j] <= 105

1886. 判断矩阵经轮转后是否一致

矩阵 - 图4
给你两个大小为 n x n 的二进制矩阵 mat 和 target 。现 以 90 度顺时针轮转 矩阵 mat 中的元素 若干次 ，如果能够使 mat 与 target 一致，返回 true ；否则，返回false 。

示例 1：
输入：mat = [[0,1],[1,0]], target = [[1,0],[0,1]] 输出：true 解释：顺时针轮转 90 度一次可以使 mat 和 target 一致。
矩阵 - 图5矩阵 - 图6
示例 2：
输入：mat = [[0,1],[1,1]], target = [[1,0],[0,1]] 输出：false 解释：无法通过轮转矩阵中的元素使 equal 与 target 一致。
示例 3：
输入：mat = [[0,0,0],[0,1,0],[1,1,1]], target = [[1,1,1],[0,1,0],[0,0,0]] 输出：true 解释：顺时针轮转 90 度两次可以使 mat 和 target 一致。

提示：

  • n == mat.length == target.length
  • n == mat[i].length == target[i].length
  • 1 <= n <= 10
  • mat[i][j] 和 target[i][j] 不是 0 就是 1
  1. from copy import deepcopy
  2. class Solution:
  3.     def findRotation(self, mat: List[List[int]], target: List[List[int]]) -> bool:
  4.         def ger_rotate(matrix):
  5.             temp = deepcopy(matrix)
  6.             n = len(matrix[0])
  7.             for i in range(len(matrix)):
  8.                 for j in range(len(matrix[0])):
  9.                     temp[j][n-i-1] = matrix[i][j]
  10.             return temp
  11.         if mat == target:
  12.             return True
  13.         temp = deepcopy(mat)
  14.         for i in range(3):
  15.             temp = ger_rotate(temp)
  16.             if temp == target:
  17.                 return True
  18.         return False

1582. 二进制矩阵中的特殊位置

给你一个大小为 rows x cols 的矩阵 mat，其中 mat[i][j] 是 0 或 1，请返回 矩阵 mat 中特殊位置的数目 。
特殊位置 定义：如果 mat[i][j] == 1 并且第 i 行和第 j 列中的所有其他元素均为 0（行和列的下标均 从 0 开始 ），则位置 (i, j) 被称为特殊位置。

示例 1：
输入：mat = [[1,0,0], [0,0,1], [1,0,0]] 输出：1 解释：(1,2) 是一个特殊位置，因为 mat[1][2] == 1 且所处的行和列上所有其他元素都是 0
示例 2：
输入：mat = [[1,0,0], [0,1,0], [0,0,1]] 输出：3 解释：(0,0), (1,1) 和 (2,2) 都是特殊位置
示例 3：
输入：mat = [[0,0,0,1], [1,0,0,0], [0,1,1,0], [0,0,0,0]] 输出：2
示例 4：
输入：mat = [[0,0,0,0,0], [1,0,0,0,0], [0,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1]] 输出：3

提示：

  • rows == mat.length
  • cols == mat[i].length
  • 1 <= rows, cols <= 100
  • mat[i][j] 是 0 或 1
  1. from collections import defaultdict
  2. class Solution:
  3.     def numSpecial(self, mat: List[List[int]]) -> int:
  4.         row_set = defaultdict(int)
  5.         col_set = defaultdict(int)
  6.         temp = []
  7.         for i in range(len(mat)):
  8.             for j in range(len(mat[0])):
  9.                 if mat[i][j] == 1:
  10.                     temp.append((i,j))
  11.                     row_set[i] += 1
  12.                     col_set[j] += 1
  13.         ans = 0
  14.         for i, j in temp:
  15.             if row_set[i] > 1 or col_set[j] > 1:
  16.                 continue
  17.             ans += 1
  18.         return ans

1572. 矩阵对角线元素的和

给你一个正方形矩阵 mat，请你返回矩阵对角线元素的和。
请你返回在矩阵主对角线上的元素和副对角线上且不在主对角线上元素的和。

示例 1：
矩阵 - 图7
输入：mat = [[1,2,3], [4,5,6], [7,8,9]] 输出：25 解释：对角线的和为：1 + 5 + 9 + 3 + 7 = 25 请注意，元素 mat[1][1] = 5 只会被计算一次。
示例 2：
输入：mat = [[1,1,1,1], [1,1,1,1], [1,1,1,1], [1,1,1,1]] 输出：8
示例 3：
输入：mat = [[5]] 输出：5

提示：

  • n == mat.length == mat[i].length
  • 1 <= n <= 100
  • 1 <= mat[i][j] <= 100

通过次数23,075
提交次数28,770

自己的写法

  1. class Solution:
  2.     def diagonalSum(self, mat: List[List[int]]) -> int:
  3.         used = set()
  4.         i = 0
  5.         j = 0
  6.         ans = 0
  7.         while i < len(mat):
  8.             if (i,j) not in used:
  9.                 ans+= mat[i][j]
  10.                 used.add((i,j))
  11.             i += 1
  12.             j += 1
  13.         row = 0
  14.         col = len(mat) - 1
  15.         while col > -1:
  16.             if (row, col) not in used:
  17.                 ans += mat[row][col]
  18.                 used.add((row, col))
  19.             row += 1
  20.             col -= 1
  21.         return ans
  1. class Solution:
  2.     def diagonalSum(self, mat: List[List[int]]) -> int:
  3.         n,ans = len(mat),0
  4.         for i in range(n):
  5.             ans += mat[i][i]
  6.             mat[i][i] = 0
  7.             ans += mat[i][n-i-1]
  9.         return ans
  11. 作者：Jam007
  12. 链接：https://leetcode-cn.com/problems/matrix-diagonal-sum/solution/si-lu-jian-dan-xing-neng-gao-xiao-by-jam-wcup/
  13. 来源：力扣（LeetCode）
  14. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

1275. 找出井字棋的获胜者

A 和 B 在一个 3 x 3 的网格上玩井字棋。
井字棋游戏的规则如下：

  • 玩家轮流将棋子放在空方格 (“ “) 上。
  • 第一个玩家 A 总是用 “X” 作为棋子，而第二个玩家 B 总是用 “O” 作为棋子。
  • “X” 和 “O” 只能放在空方格中，而不能放在已经被占用的方格上。
  • 只要有 3 个相同的（非空）棋子排成一条直线（行、列、对角线）时，游戏结束。
  • 如果所有方块都放满棋子（不为空），游戏也会结束。
  • 游戏结束后，棋子无法再进行任何移动。

给你一个数组 moves，其中每个元素是大小为 2 的另一个数组（元素分别对应网格的行和列），它按照 A 和 B 的行动顺序（先 A 后 B）记录了两人各自的棋子位置。
如果游戏存在获胜者（A 或 B），就返回该游戏的获胜者；如果游戏以平局结束，则返回 “Draw”；如果仍会有行动（游戏未结束），则返回 “Pending”。
你可以假设 moves 都 有效（遵循井字棋规则），网格最初是空的，A 将先行动。

示例 1：
输入：moves = [[0,0],[2,0],[1,1],[2,1],[2,2]] 输出：“A” 解释：“A” 获胜，他总是先走。 “X “ “X “ “X “ “X “ “X “ “ “ -> “ “ -> “ X “ -> “ X “ -> “ X “ “ “ “O “ “O “ “OO “ “OOX“
示例 2：
输入：moves = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]] 输出：“B” 解释：“B” 获胜。 “X “ “X “ “XX “ “XXO” “XXO” “XXO“ “ “ -> “ O “ -> “ O “ -> “ O “ -> “XO “ -> “XO “ “ “ “ “ “ “ “ “ “ “ “O “
示例 3：
输入：moves = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2],[2,2]] 输出：“Draw” 输出：由于没有办法再行动，游戏以平局结束。 “XXO” “OOX” “XOX”
示例 4：
输入：moves = [[0,0],[1,1]] 输出：“Pending” 解释：游戏还没有结束。 “X “ “ O “ “ “

提示：

  • 1 <= moves.length <= 9
  • moves[i].length == 2
  • 0 <= moves[i][j] <= 2
  • moves 里没有重复的元素。
  • moves 遵循井字棋的规则。

通过次数9,146
提交次数16,754

  1. from collections import defaultdict
  4. class Solution:
  5.     def tictactoe(self, moves: List[List[int]]) -> str:
  6.         if len(moves) > 9:
  7.             return "Pending"
  8.         line_left = 0
  9.         line_right = 0
  10.         row_maps = defaultdict(int)
  11.         col_maps = defaultdict(int)
  12.         used = set()
  13.         for i, n in enumerate(moves):
  14.             if i % 2 == 0:
  15.                 qi_zi = 1
  16.             else:
  17.                 qi_zi = -1
  18.             row = n[0]
  19.             col = n[1]
  20.             wei_zhi = (row, col)
  21.             if wei_zhi in used:
  22.                 continue
  23.             used.add(wei_zhi)
  24.             row_maps[row] += qi_zi
  25.             col_maps[col] += qi_zi
  26.             if wei_zhi in [(0, 0), (1, 1), (2, 2)]:
  27.                 line_left += qi_zi
  28.             if wei_zhi in [(0, 2), (1, 1), (2, 0)]:
  29.                 line_right += qi_zi
  30.         if line_left == 3:
  31.             return 'A'
  32.         if line_left == -3:
  33.             return 'B'
  34.         if line_right == 3:
  35.             return 'A'
  36.         if line_right == -3:
  37.             return 'B'
  38.         for i in row_maps.values():
  39.             if i == 3:
  40.                 return 'A'
  41.             if i == -3:
  42.                 return 'B'
  43.         for i in col_maps.values():
  44.             if i == 3:
  45.                 return 'A'
  46.             if i == -3:
  47.                 return 'B'
  48.         if len(used) == 9:
  49.             return "Draw"
  50.         else:
  51.             return 'Pending'

1030. 距离顺序排列矩阵单元格

给定四个整数 row , cols , rCenter 和 cCenter 。有一个 rows x cols 的矩阵，你在单元格上的坐标是 (rCenter, cCenter) 。
返回矩阵中的所有单元格的坐标，并按与 (rCenter, cCenter) 的 距离 从最小到最大的顺序排。你可以按 任何 满足此条件的顺序返回答案。
单元格(r1, c1) 和 (r2, c2) 之间的距离为|r1 - r2| + |c1 - c2|。

示例 1：
输入：rows = 1, cols = 2, rCenter = 0, cCenter = 0 输出：[[0,0],[0,1]] 解释：从 (r0, c0) 到其他单元格的距离为：[0,1]
示例 2：
输入：rows = 2, cols = 2, rCenter = 0, cCenter = 1 输出：[[0,1],[0,0],[1,1],[1,0]] 解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2] [[0,1],[1,1],[0,0],[1,0]] 也会被视作正确答案。
示例 3：
输入：rows = 2, cols = 3, rCenter = 1, cCenter = 2 输出：[[1,2],[0,2],[1,1],[0,1],[1,0],[0,0]] 解释：从 (r0, c0) 到其他单元格的距离为：[0,1,1,2,2,3] 其他满足题目要求的答案也会被视为正确，例如 [[1,2],[1,1],[0,2],[1,0],[0,1],[0,0]]。

提示：

  • 1 <= rows, cols <= 100
  • 0 <= rCenter < rows
  • 0 <= cCenter < cols
from collections import deque


class Solution:
    def allCellsDistOrder(self, rows: int, cols: int, rCenter: int, cCenter: int) -> List[List[int]]:
        q = deque([])
        q.append((rCenter, cCenter))
        ans = []
        visited = set()
        visited.add((rCenter, cCenter))
        while q:
            r, c = q.popleft()
            ans.append([r,c])
            for x, y in [[-1, 0], [1,0], [0,1],[0,-1]]:
                new_r = r + x
                new_c = c + y
                temp = (r + x, c + y)
                if 0 <= new_r < rows and 0 <= new_c < cols and temp not in visited:
                    visited.add(temp)
                    q.append(temp)
        return ans

54. 螺旋矩阵

矩阵 - 图8
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]] 输出：[1,2,3,6,9,8,7,4,5]
矩阵 - 图9
示例 2：
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] 输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

通过次数236,494
提交次数487,588

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ans = []
        up = 0
        right = len(matrix[0]) - 1
        left = 0
        down = len(matrix) - 1
        while True:
            for i in range(left, right + 1):
                ans.append(matrix[up][i])
            up += 1
            if up > down: break

            for i in range(up, down + 1):
                ans.append(matrix[i][right])
            right -= 1
            if left > right: break

            for i in range(right, left - 1, -1):
                ans.append(matrix[down][i])
            down -=1
            if up > down: break

            for i in range(down, up - 1, -1):
                ans.append(matrix[i][left])
            left += 1
            if left > right: break
        return ans

59. 螺旋矩阵 II

矩阵 - 图10
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：
输入：n = 3 输出：[[1,2,3],[8,9,4],[7,6,5]]
示例 2：
输入：n = 1 输出：[[1]]

提示：

  • 1 <= n <= 20
class Solution:
    def generateMatrix(self, n) -> List[int]:
        ans = [[0] * n for _ in range(n)]
        up = 0
        right = n - 1
        left = 0
        down = n - 1
        max_num = n * n
        temp = 0
        while True:
            for i in range(left, right + 1):
                temp +=1
                ans[up][i] = temp
            up += 1
            if temp >= max_num: break

            for i in range(up, down + 1):
                temp += 1
                ans[i][right] = temp
            right -= 1
            if temp >= max_num: break

            for i in range(right, left - 1, -1):
                temp += 1
                ans[down][i] = temp
            down -=1
            if temp >= max_num: break

            for i in range(down, up - 1, -1):
                temp += 1
                ans[i][left] = temp
            left += 1
            if temp >= max_num: break
        return ans

73. 矩阵置零

矩阵 - 图11
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]] 输出：[[1,0,1],[0,0,0],[1,0,1]]
矩阵 - 图12
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]] 输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：

  • m == matrix.length
  • n == matrix[0].length
  • 1 <= m, n <= 200
  • -231 <= matrix[i][j] <= 231 - 1

进阶：

  • 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
  • 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
  • 你能想出一个仅使用常量空间的解决方案吗？

通过次数168,984
提交次数275,069

通过map提前找出需要置为0的矩阵

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        row_map = {}
        col_map = {}
        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0:
                    row_map[i] = 1
                    col_map[j] = 1
        # 对行进行置0
        for j in range(len(matrix[0])):
            for k in row_map.keys():
                matrix[k][j] = 0
        # 对列进行置0
        for i in range(len(matrix)):
            for k in col_map.keys():
                matrix[i][k] = 0

直接暴力

class Solution:
    def setZeroes(self, matrix: List[List[int]]) -> None:
        visited = set()
        m = len(matrix)
        n = len(matrix[0])

        def travel(matrix, i, j):
            for a in range(m):
                if matrix[a][j] != 0:
                    matrix[a][j] = 0
                    visited.add((a, j))
            for b in range(n):
                if matrix[i][b] != 0:
                    matrix[i][b] = 0
                    visited.add((i, b))

        for i in range(len(matrix)):
            for j in range(len(matrix[0])):
                if matrix[i][j] == 0 and (i, j) not in visited:
                    travel(matrix, i, j)