48. 旋转图像 [medium]

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

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明：

你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

给定 matrix = 
[
  [1,2,3],
  [4,5,6],
  [7,8,9]
],

原地旋转输入矩阵，使其变为:
[
  [7,4,1],
  [8,5,2],
  [9,6,3]
]

示例 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]
]

通过次数86,331 | 提交次数125,254

Second Try

2020-07-28

看题解后仔细观察，发现还可以通过转置transpose和对不同列进行逆序交换reverse来进行转换。

转置是绕着右下方向的对角线进行旋转，本来觉得非常简单可以不假思索，结果最大的问题竟然是写转置小程序，贡献了两个bug.

一是认为遍历了i/j, 任何i/j的匹配都会被识别到，因此在替换的时候只写matrix[i][j] = matrix[j][i],没想到要及时考虑matrix[j][i]，不然被覆盖了。如果是额外一个矩阵进行复制倒没有问题。
二是对所有的列位置j进行遍历for j in range(n), 没有想到由于对称的作用，在从上到下遍历到左下角的时候其实已经被替换过一次了，结果又是混乱。需要只考虑对右上三角进行遍历，也即for j in range(i + 1, n)。其实如果是额外一个矩阵进行转置复制也没有问题，但这里面要求是in-place,就要考虑互相重复替换的问题了。

不过转置+逆转的思路，总归比first try里面每个元素绕着4个角进行轮换要来得思路清晰。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        n = len(matrix)
        # transpose 
        for i in range(n):
            # 又傻逼了，for j in range(n)的结果是之前换过的又被重复替换了
            # for j in range(n):
            for j in range(i + 1, n):
                # 傻逼了,替换只替换了一半，没考虑两个位置都需要互换
                # matrix[i][j] = matrix[j][i]
                matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
        # reverse column 
        for i in range(n):
            for j in range(n // 2):
                nexj = n - 1 - j 
                matrix[i][j], matrix[i][nexj] = matrix[i][nexj], matrix[i][j]

执行用时：56 ms, 在所有 Python3 提交中击败了5.97%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了6.67%的用户

First Try

2020-07-28

直接做还是没想出来怎么原地替换，看了题解发现可以一圈一圈的替换，每一圈从4个角开始，然后四个角同层的其他元素。仔细观察就有规律了，是一种收尾相接的轮换。

i,j位置的元素，在替换后的新位置可以通过new_pos直接获得。剩下的就是慢慢凑出无bug的写法了，一边写一遍调整，每一圈对应的4个元素需要替换4次来完成一个环。

class Solution:
    def rotate(self, matrix: List[List[int]]) -> None:
        """
        Do not return anything, modify matrix in-place instead.
        """
    
        size = len(matrix)
        def new_pos(i, j):  # 每个矩形元素在更换后的新位置
            return j, size - 1 - i 
        # 观察4个角的替换，然后同层元素的替换，每次替换矩形最外围一圈，然后再进入下一圈
        i = 0 
        while i < size // 2:
            for j in range(i, size - 1 - i):
                idx, jdx = i, j
                reserve = matrix[idx][jdx]
                for _ in range(4):  # 每个矩形4个角，与size无关
                    nidx, njdx = new_pos(idx, jdx)
                    # print('swift', idx, jdx, "->", nidx, njdx)
                    new_reserve = matrix[nidx][njdx] 
                    matrix[nidx][njdx] = reserve 
                    reserve = new_reserve
                    idx, jdx = nidx, njdx
                # print(i, j, matrix) 
            i += 1 

执行用时：48 ms, 在所有 Python3 提交中击败了19.38%的用户
内存消耗：13.7 MB, 在所有 Python3 提交中击败了6.67%的用户

48. 旋转图像 [medium]​

Second Try​

First Try​

48. 旋转图像 [medium]

Second Try

First Try