LeetCode每日练习-数组（48、54、498）

48-旋转图像

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

• 方法：找规律

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        # 要求不使用额外的空间
        # 先上下进行 行反转 然后进行 对角线元素反转
        # 1、行反转时，只改变行值,例如: matrix[0][0], matrix[2][0] = matrix[2][0], matrix[0][0]
        row = len(matrix)       # 行数
        col = len(matrix[0])    # 列数
        for i in range(row//2):
            for j in range(col):
                matrix[i][j], matrix[row-i-1][j] = matrix[row-i-1][j], matrix[i][j]
        # print(matrix)
         # 2、对角线反转时，行和列交换，例如: matrix[0][1], matrix[1][0] = matrix[1][0], matrix[0][1]
        for i in range(row):
            # 注意只需要转换一个下三角或者上三角元素
            for j in range(i):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # print(matrix)
        return matrix

54-螺旋矩阵

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

• 方法：模拟算法，注意边界的判断和处理

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        # 上下左右四个位置
        up, down, left, right = 0, len(matrix)-1, 0, len(matrix[0])-1
        res = []
        while True:
            # 1、向右走， 遍历一行
            for i in range(left, right+1):
                res.append(matrix[up][i])
            # 更新行数
            up += 1 
            if up > down:
                break
            # 2、向下走，遍历一列
            for i in range(up, down+1):
                res.append(matrix[i][right])
            # 更新列数
            right -= 1
            if right < left:
                break
            # 3、向左走，遍历一行
            for i in range(right, left-1, -1):
                res.append(matrix[down][i])
            # 更新行数
            down -= 1
            if down < up:
                break
            # 4、向上走，遍历一列
            for i in range(down, up-1, -1):
                res.append(matrix[i][left])
            # 更新列数
            left += 1
            if left > right:
                break
        return res

498-对角线遍历

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

• 方法：找规律

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        row = len(mat)       # 行数
        col = len(mat[0])    # 列数
        count = row * col
        x, y = 0, 0
        res = []
        for i in range(count):
            res.append(mat[x][y])
            # 如果行和列的和为 偶数，则遍历方向为 右上 ↗
            if (x + y) % 2 == 0:
                # 到了最后一行，向下走
                if y == col - 1:
                    x += 1
                # 到了第一行，向右走
                elif x == 0:
                    y += 1
                # 沿 右上对角线 遍历元素
                else:
                    x -= 1
                    y += 1
            # 如果行和列的和为 奇数，则遍历方向为 左下 ↙
            else:
                # 到了最后一行，向右走
                if x == row - 1:
                    y += 1
                # 到了第一列，向下走
                elif y == 0:
                    x += 1
                # 沿 左上对角线 遍历元素
                else:
                    x += 1
                    y -= 1
        return res