旋转图像- leetcode

Question

如果我问一些愚蠢的事情(我对编码很陌生)，我很抱歉，但是我没有找到一个清晰的解释来解释我的怀疑。我在leetcode上遇到了以下问题：

给出一个表示图像的nxn2D矩阵，将图像旋转90度(顺时针方向)。你必须原地旋转图像，这意味着你必须直接修改输入的2D矩阵。不要分配另一个2D矩阵并进行旋转。例如:输入:矩阵=[1，2，3，4，5，6，7，8，9，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修改列表，不返回结果。

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

给你一个列表。反转列表中元素的顺序.

# 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]);
        }
    }
}