LeetCode in Python 48. Rotate Image/Matrix (旋转图像/矩阵)

旋转图像/矩阵的重点是寻找旋转前后对应位置的坐标关系。

示例:

图1 旋转图像/矩阵的输入输出示意图 

代码: 

class Solution:
    def rotate(self, matrix):
        n = len(matrix)
        for i in range(n // 2):
            for j in range(i, n - 1 - i):
                topleft = matrix[i][j]
                matrix[i][j] = matrix[n - 1 - j][i]
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
                matrix[j][n - 1 - i] = topleft

解释:

1)外层循环控制需要转的大圈圈数,内层循环控制每一圈需要转的小圈圈数,大小圈数的解释见图2,例如n=4,需要循环n // 2 = 2大圈,其中黄色循环箭头为第一大圈,绿色循环箭头为第二大圈。对于第一大圈,5->11->16->15->5为一小圈,同理1->10->12->13->1、9->7->14->2->9各为一小圈。

2)对于如何确定旋转前后位置坐标的对应关系,笔者是通过先确定再确定内层的方法,例如对于第一圈,固定i=0,然后观察大圈位置变化确定对应关系,接着改变i,观察内层圈数与i的对应关系进而修改对应坐标变化,如若先固定外层大圈循环,位置坐标变化应为:

matrix[0][j] = matrix[n - 1 - j][0]
matrix[n - 1 - j][0] = matrix[n - 1 - 0][n - 1 - j]
matrix[n - 1 - 0][n - 1 - j] = matrix[j][n - 1 - 0]
matrix[j][n - 1 - 0] = topleft

接着改变圈数,进入内层大圈循环,修改坐标变化:

matrix[i][j] = matrix[n - 1 - j][i]
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j]
matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i]
matrix[j][n - 1 - i] = topleft

3)为了使算法空间复杂度为O(1),只需将每一次循环的左上角元素保存下来,接着采用逆向循环的顺序调整元素,最后将左上角元素归位即可,如此便无需重新开辟一个O(n^{2}) 空间来保存原始矩阵。

另外:求助(请各位读者帮我康康下面的方法具体如何修改,坐标变化还存在一些问题,谢谢大家捏)

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
        l, r = 0, len(matrix) - 1
        while l < r:
            for i in range(r):
                top, bot = l, r
                topleft = matrix[top][l + i]
                matrix[top][l + i] = matrix[bot - i][l]
                matrix[bot - i][l] = matrix[bot][r - i]
                matrix[bot][r - i] = matrix[top + i][r]
                matrix[top + i][r] = topleft
            l += 1
            r -= 1

上一篇:ESP32与SD卡交互实现:文件读写实战与初始化详解及引脚定义


下一篇:【k8s】(六)kubernetes1.29.4离线部署之-加入Node节点