旋转图像 - Leetcode

Question

如果我问了一些愚蠢的问题（我对编码还很陌生），我很抱歉，但我没有找到对我的疑问的明确解释。我在leetcode上遇到了以下问题：

给定一个 n x n 2D 矩阵来表示图像，将图像旋转 90 度（顺时针）。您必须就地旋转图像，这意味着您必须直接修改输入的二维矩阵。不要分配另一个二维矩阵并进行旋转。 例子： 输入：矩阵 = [[1,2,3],[4,5,6],[7,8,9]] 输出：[[7,4,1],[8,5,2],[9,6,3]]

我的解决方案是：

class Solution:
    def rotate(self, matrix):
        l = len(matrix)

        clockwise_nums = [matrix[j][i] for i in range(l) for j in range(l - 1, -1, -1)]

        final_array = [clockwise_nums[i:i + l] for i in range(0, len(clockwise_nums), l)]

        return final_array

纯粹的执行（矩阵旋转）有效，但这不被接受，因为它不就位。但我实在不明白这意味着什么。 您认为我的方法离这里很远，我应该尝试一些不同的东西吗？或者有没有办法调整我的解决方案（很高兴我想出了一种旋转矩阵的方法）？ 此外，任何有关就地算法的提示将不胜感激。 非常感谢！

Answer 1

要理解“就地操作”和“返回新数组”之间的区别，想象一个更简单的问题：

您将获得一份清单。为列表的每个元素加 1。

# returning a new array
def add_one_copy(l):
  return [x + 1 for x in l]

# in-place
def add_one_inplace(l):
  for i in range(len(l)):
    l[i] = l[i] + 1

在 python 交互式解释器中测试这两个函数突出了差异：

>>> a = [1, 2, 3]
>>> add_one_copy(a)
[2, 3, 4]
>>> a
[1, 2, 3]
>>> add_one_inplace(a)
>>> a
[2, 3, 4]

add_one_copy

返回结果，但不修改

a

。

add_one_inplace

不返回结果，但修改列表。 python函数

sorted

和

list.sort

之间有同样的区别：

>>> a = [3,4,2,1]
>>> sorted(a)
[1, 2, 3, 4]
>>> a
[3, 4, 2, 1]
>>> a.sort()
>>> a
[1, 2, 3, 4]

sorted

返回结果，但不修改列表。

.sort

修改列表并且不返回结果。

现在，您要解决的问题比只是向每个元素加 1 稍微复杂一些。就地解决旋转问题时的困难在于您要在矩阵中移动元素；这样做时，您必须小心不要覆盖您仍然需要的元素的值。想象一个稍微难一点的问题：

您将获得一份清单。反转列表中元素的顺序。

# returning a copy
def reverse_copy(l):
  return [l[len(l) - i - 1] for i in range(len(l))]

# in-place attempt, fall head-first in the trap, this is not working
def reverse_inplace_wrong(l):
  for i in range(len(l)):
    l[i] = l[len(l) - i - 1]

# in-place, correct
def reverse_inplace(l):
  for i in range(len(l)//2):
    tmp = l[len(l) - i - 1]
    l[len(l) - i - 1] = l[i]
    l[i] = tmp

测试：

>>> a = [1,2,3,4,5,6,7]
>>> reverse_copy(a)
[7, 6, 5, 4, 3, 2, 1]
>>> a
[1, 2, 3, 4, 5, 6, 7]
>>> reverse_inplace_wrong(a)
>>> a
[7, 6, 5, 4, 5, 6, 7]
>>> a = [1,2,3,4,5,6,7]
>>> reverse_inplace(a)
>>> a
[7, 6, 5, 4, 3, 2, 1]

当反转列表时，我发现位置

i

的元素应该转到位置

len(l) - i - 1

。旋转矩阵时，你必须弄清楚位置

(i,j)

的元素应该去哪里。而且你一定要小心，不要重复我在

reverse_inplace_wrong

中犯的错误。

Answer 2

为了解决这个问题，我们还可以使用Python内置的

reverse()

，这不会是一个大问题：

class Solution:
    def rotate(self, A):
        A.reverse()
        for row in range(len(A)):
            for col in range(row):
                A[row][col], A[col][row] = A[col][row], A[row][col]

Answer 3

如果你了解 C++，你可以看看我的解决方案。

我使用矩阵转置的逻辑解决了它。转置后，我将同一行中的第一列值与最后一列交换。然后是第二列和倒数第二列，依此类推。

void swapValues(int &valueOne, int &valueTwo) {
    int tempValue = valueOne;
    valueOne = valueTwo;
    valueTwo = tempValue;
}
    
void rotate(vector<vector<int> >& matrix) {
    int n = matrix.size();
    int halfN = n / 2;

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            if(i != j && j > i) {
                swapValues(matrix[i][j], matrix[j][i]);
            }
        }

        for (int j=0; j<halfN; j++) {
            swapValues(matrix[i][j], matrix[i][n-1-j]);
        }
    }
}

Answer 4

class Solution:
    def rotate(self, matrix):
        rotate_mat = []
        for l in range(len(matrix)):
            mat = [i[l] for i in matrix][::-1]
            rotate_mat.append(mat)
        return rotate_mat

Answer 5

我正在用 Javascript 解决同样的问题。

我使用了转置矩阵然后反转每一行的逻辑。

转置矩阵：

• 这里的想法是将每个元素矩阵[i][j]与其对应的元素矩阵[j][i]交换。这有效地反映了矩阵在其主对角线上的情况。

• 我们迭代矩阵的上三角形（即，其中 i <= j), swapping elements as described above.

反转每一行：

• 转置后，矩阵旋转了90度，但不是完全旋转。为了完成旋转，我们需要水平翻转矩阵。

• 我们通过反转转置矩阵的每一行来实现这一点。

代码

function rotate(matrix) {
    const n = matrix.length;
    
    for(let i = 0; i < n; i++) {
        for(let j = i; j < n; j++) {
            [matrix[i][j], matrix[j][i]] = [matrix[j][i], matrix[i][j]];
        }
    }
    
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n / 2; j++) {
            // Swap matrix[i][j] with matrix[i][n - 1 - j]
            [matrix[i][j], matrix[i][n - 1 - j]] = [matrix[i][n - 1 - j], matrix[i][j]];
        }
    }
    
    
};