59. Spiral Matrix II

https://leetcode.com/problems/spiral-matrix-ii/

solution

• 循环不变量，矩阵四条边都使用同一种左闭右开或左闭右闭的形式。新建一个数组用于更新数据，不必in-place

• 以下采用了左闭右闭的形式

# value递进，坐标变换: https://algo.monster/liteproblems/59

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        row_start, row_end = 0, n - 1
        col_start, col_end = 0, n - 1
        num = 1
        res = [[0 for _ in range(n)] for _ in range(n)]

        while row_end >= row_start and col_end >= col_start:
            for i in range(col_start, col_end + 1):
                res[row_start][i] = num
                num += 1
            row_start +=  1

            for i in range(row_start, row_end + 1):
                res[i][col_end] = num
                num += 1
            col_end -= 1

            for i in range(col_end, col_start - 1, -1):
                res[row_end][i] = num
                num += 1
            row_end -= 1

            for i in range(row_end, row_start - 1, -1):
                res[i][col_start] = num
                num += 1
            col_start += 1
        return res

时间复杂度：O(n^2) 空间复杂度：O(1)

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]
        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]

        row = col = 0
        dir_idx = 0

        for value in range(1, 1 + n*n):
            matrix[row][col] = value
            next_row = row + dirs[dir_idx][0]
            next_col = col + dirs[dir_idx][1]

            if next_row < 0 or next_row >= n or next_col < 0 or next_col >= n or matrix[next_row][next_col]:
                dir_idx = (dir_idx + 1) % 4
                next_row = row + dirs[dir_idx][0]
                next_col = col + dirs[dir_idx][1]

            row, col = next_row, next_col
        return matrix

follow up

剑指offer 29: 顺时针打印矩阵

# 一直取第一行，取完之后进行逆时针旋转

class Solution:
    def printMatrix(self, matrix):
        result = []
        while(matrix):
            result += matrix.pop(0)
            if not matrix or not matrix[0]:
                break
            matrix = self.turn(matrix)
        return result

    def turn(self,matrix):
        num_r = len(matrix)
        num_c = len(matrix[0])
        new_mat = []
        for i in range(num_c-1, -1, -1):
            new_mat2 = []
            for j in range(num_r):
                new_mat2.append(matrix[j][i])
            new_mat.append(new_mat2)
        return new_mat

时间复杂度：O() 空间复杂度：O()

48. Rotate Image

• 行先倒过来，两两替换元素。注意控制index避免重复

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        matrix.reverse()  # 注意inplace, 用matrix=matrix[::-1]不对

        for i in range(len(matrix)):
            for j in range(i, len(matrix)):
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]

时间复杂度：O(n^2) 空间复杂度：O(1)

6. Zigzag Conversion

• 模拟，每次到首或尾就转换方向，模拟题需要耐心的想一想

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s

        rows = [''] * numRows
        k = 0
        direction = - 1

        for c in s:
            rows[k] += c
            if k == 0 or k == numRows - 1:
                direction *= -1
            k += direction

        return ''.join(rows)

时间复杂度：O() 空间复杂度：O()

54. Spiral Matrix

# direct_index的做法根据index增量也不错：https://algo.monster/liteproblems/54

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

        res = []
        i_start = 0
        i_end = m - 1
        j_start = 0
        j_end = n - 1

        while i_start <= i_end and j_start <= j_end:

            for j in range(j_start, j_end+1):
                res.append(matrix[i_start][j])
            i_start += 1

            for i in range(i_start, i_end+1):
                res.append(matrix[i][j_end])
            j_end -= 1

            for j in range(j_end, j_start-1, -1):
                res.append(matrix[i_end][j])
            i_end -= 1

            for i in range(i_end, i_start-1, -1):
                res.append(matrix[i][j_start])
            j_start += 1

        return res[:m*n]  # 注意最后的处理

498. Diagonal Traverse

• 根据同一level, 行加列的index和相同

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:

        counter = collections.defaultdict(list)
        m = len(mat)
        n = len(mat[0])

        for i in range(m):
            for j in range(n):
                counter[i+j].append(mat[i][j])

        res = []
        for x in range(m + n - 1):
            x_list = counter[x]
            if x % 2 == 0:
                x_list.reverse()
            res += x_list
        return res

1424. Diagonal Traverse II

class Solution:
    def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
        res = collections.defaultdict(list)
        for i in range(len(nums)):
            for j in range(len(nums[i])):
                res[i + j].append(nums[i][j])

        res_list = [i[::-1] for i in res.values()]
        return sum(res_list, [])  # 拉平