leetcode 48. 旋转图像

目录

1. 解题思路
2. 代码

https://leetcode-cn.com/problems/rotate-image/

解题思路

由外到内依次移动，每次之移动一个元素，所以空间复杂度是 O(1) 。

移动顺序是从左上角开始，每次开始移动一直要把对应的四个位置轮换一边才结束，再执行第二个位置。

例子：

求下一个位置的函数：

def next_xy(x, y, s):
     return y, s - 1 - x

代码

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        def next_xy(x, y, s):
            return y, s - 1 - x
        n = len(matrix)
        i = 0
        for i in range(n):
            l = n - i * 2
            if l < 2: break
            for j in range(l-1):
                x, y = 0, j
                t = matrix[x+i][y+i]
                for k in range(4):
                    nx, ny = next_xy(x, y, l)
                    print(x, y, nx, ny)
                    print(t, matrix[nx+i][ny+i])
                    tt = matrix[nx+i][ny+i]
                    matrix[nx+i][ny+i] = t 
                    x, y, t = nx, ny, tt