python - 破解编码面试，第 6 版，1.7

Question

给定一个由 nxn 矩阵表示的图像，其中图像中的每个像素为 4 个字节，编写一个将图像旋转 90 度的方法。 (到位)

我做了一个低效的解决方案，即将每一行复制到一个临时文件，然后执行交换，占用了 o(N) 空间，下面的实际解决方案更好，但我不明白。

def rotate_matrix(matrix):
    '''rotates a matrix 90 degrees clockwise'''
    n = len(matrix)
    for layer in range(n // 2):
        first, last = layer, n - layer - 1
        for i in range(first, last):
            # save top
            top = matrix[layer][i]

            # left -> top
            matrix[layer][i] = matrix[-i - 1][layer]

            # bottom -> left
            matrix[-i - 1][layer] = matrix[-layer - 1][-i - 1]

            # right -> bottom
            matrix[-layer - 1][-i - 1] = matrix[i][- layer - 1]

            # top -> right
            matrix[i][- layer - 1] = top
    return matrix

上面的代码是Python的解决方案，

我不明白 for 循环，为什么它在范围 n//2 和从第一层到 n-layer-1。

另外，为什么题目提到4个字节好像是无用的信息。

谢谢!

Answer 1

重要的是要考虑 n 是奇数还是偶数，因为必须以微妙不同的方式解决问题。不过，在任何一种情况下，正方形都可以分解为象限。

n 是奇数:

正方形被分解成四个矩形象限。在双 for 循环的每次迭代中，正好旋转 4 个元素，每个象限一个。中间元素永远不会被访问，因为它在旋转中保持在中间。

+-------+---+ 
| x   x | x | 
+---+---+   | 
| x | x | x | 
|   +---+---+ 
| x | x   x | 
+---+-------+

n 是偶数大小写:

矩阵被分解成 4 个正方形象限。同样，在双 for 循环的每次迭代中，正好旋转 4 个元素，每个象限一个。在偶数情况下，每个元素都必须移动(即没有完美的中心元素)。

+-------+-------+
| x   x | x   x |
|       |       |
| x   x | x   x |
+-------+-------+
| x   x | x   x |
|       |       |
| x   x | x   x |
+-------+-------+

n//2 和 n - layer - 1 只是变相的下限和上限函数。 n 是奇数情况需要下限和上限。这些值用于在其中一个象限上设置迭代。然后，对于 一个 象限中存在的许多元素，4 次交换发生在适当的位置(在 top 临时值的帮助下)。