Не могу обнаружить ошибку в моем коде матрицы поворота

Question

Я знаю, что есть простой способ использовать транспонирование для поворота квадратной матрицы на 90 градусов, но я пишу решение, как будто я не знаю этого (другими словами, я хочу сделать обмен).Общая идея ниже - поменять слой за слоем.offset представляет, какой слой (наружу внутрь) заменяется.

Вот алгоритм (обратите внимание, что он заключен в class, потому что это Leetcode вещь):

class Solution:
    def rotate(self, matrix):
        for start in range(len(matrix)//2):
            end = len(matrix) - start - 1

            # swap all 4 coordinates:
            for offset in range(start, end): 
                # swap top_left over top_right
                temp, matrix[start+offset][end] = matrix[start+offset][end], matrix[start][start+offset]

                # swap top_right -> bottom_right 
                temp, matrix[end][end-offset] = matrix[end][end-offset], temp

                # swap bottom_right -> bottom_left
                temp, matrix[end-offset][start] = matrix[end-offset][start], temp

                # swap bottom_left -> top_left 
                matrix[start][start+offset] = temp

---

Это работает для некоторых руктесты с небольшими матрицами, а также входные тесты меньшего размера в представлении Leetcode.Однако он не работает на следующем входе:

[[ 2,  29,  20,  26,  16,  28],
 [12,  27,   9,  25,  13,  21],
 [32,  33,  32,   2,  28,  14],
 [13,  14,  32,  27,  22,  26],
 [33,   1,  20,   7,  21,   7],
 [ 4,  24,   1,   6,  32,  34]]

Ожидаемый вывод:

[[ 4,  33,  13,  32,  12,   2],
 [24,   1,  14,  33,  27,  29],
 [ 1,  20,  32,  32,   9,  20],
 [ 6,   7,  27,   2,  25,  26],
 [32,  21,  22,  28,  13,  16],
 [34,   7,  26,  14,  21,  28]]

Мой вывод:

[[ 4,  33,  13,  32,  12,   2],
 [24,   1,   7,  33,  27,  29],
 [ 1,  20,  32,   2,  14,  20],
 [ 6,  28,  32,  27,  25,  26],
 [32,  21,  22,   9,  13,  16],
 [34,   7,  26,  14,  21,  28]]

---

Эта матрица просто большаядостаточно там, где становится утомительно проходить алгоритм вручную, как я делал для небольших входных случаев для отладки.Где ошибка в моей реализации?

Answer 1

Ваши (случайные) тестовые данные сложно отслеживать и отлаживать.Было бы лучше использовать читаемый набор.

Также кажется, что реализация делает чрезмерные перестановки.

Достаточно запомнить значение ячейки, циклически сдвинуть ячейки данных, извлечь запомненное значение.

Вот простая реализация поворота с матом, заполненным последовательными числами:

n = 5
nm = n - 1
mat = []
for i in range(n):
    a = [x for x in range(n*i, n*i+n)]
    mat.append(a)

for i in range(n):
   (print(mat[i]))

for row in range((n + 1)//2):
    for col in range(n//2):
        t = mat[row] [col]
        mat[row][col] = mat[nm-col][row]
        mat[nm-col][row] = mat[nm-row][nm-col]
        mat[nm-row][nm - col] = mat[col][nm-row]
        mat[col][nm-row] = t    

print("")
for i in range(n):
   (print(mat[i]))

[0, 1, 2, 3, 4]
[5, 6, 7, 8, 9]
[10, 11, 12, 13, 14]
[15, 16, 17, 18, 19]
[20, 21, 22, 23, 24]

[20, 15, 10, 5, 0]
[21, 16, 11, 6, 1]
[22, 17, 12, 7, 2]
[23, 18, 13, 8, 3]
[24, 19, 14, 9, 4]

Answer 2

Ваш offset выключен , попробуйте

for offset in range(0, end-start):

Answer 3

Для того чтобы сделать это вращение, значение i-й строки и j-го столбца входной матрицы должно быть сделано равным j-й строке i-го столбца выходной матрицы (транспонировать) и (затемшаг) столбцы следует поменять местами.На вашем месте я бы определил пустую матрицу и (скажем, TRANSPOSE, имеет тот же размер, что и входная матрица), определил бы 2 для циклов (i в диапазоне len (матрица) и j в диапазоне len (матрица). Внутри второйцикл Я бы написал

TRANSPOSE[i][j] = matrix[j][i]

Теперь у меня есть матрица, которую вы хотите с обратными столбцами. Теперь нам нужно повернуть столбцы, чтобы получить то, что вы хотите, поэтому я бы определил другой для циклов с теми же переменными и диапазоном,и нам нужна еще одна пустая матрица с тем же размером, или мы можем использовать входную матрицу снова, давайте использовать входную матрицу в этом случае.

matrix[i][j] = TRANSPOSE[i][len(matrix) - j - 1]

и вернуть matrix