Решение LeetCode 48. Повернуть изображение,
Вот учебник, который может помочь вам с небольшой сложной проблемой из LeetCode и решением в Swift. Развлекайся!
Предпосылки:
- Некоторый опыт программирования
Сложность: легкая| Обычный | Испытывающий
Проблема
Поворачиваем следующую матрицу:
Что становится следующим:
Способ 1: Простое вращение
Поверните углы
Индекс углов может быть получен из размера матрицы. Здесь мы описываем позицию как координату, а затем вывод в Swift (где size = matrix.count).
вверху слева = [0,0] = матрица [0][0]
вверху справа = [0,3–1] = матрица[0][размер — 1]
внизу справа = [3–1, 3–1] = матрица [размер-1][размер-1]
внизу слева = [3–1, 0] = матрица [размер-1] [0]
поэтому мы можем вращать эти значения следующим образом — поскольку нам нужно вращать это по часовой стрелке, мы неизбежно сотрем одно из нужных нам значений. Чтобы избежать этого, мы сохраняем одно из значений как временное значение.
пусть темп = матрица [0] [0]
// вверху слева == внизу слева
матрица[0][0] = матрица [строк — 1][0]
// внизу слева == внизу справа
матрица[строки — 1][0] = матрица[3–1][3–1]
// внизу справа == вверху справа
матрица[3–1][3–1] = матрица[0][3–1]
// вверху справа == вверху слева (что теперь изменилось)
матрица[0][3–1] = температура
Поворот углов, обобщенный
У нас может быть матрица любого размера n*n.
Мы видим, что теперь есть внешний и внутренний кубы, которые нужно вращать.
Здесь у нас будет два цикла для завершения вращения (matrix.count/2).
Первый цикл будет 0, а первый 1.
Это означает, что верхний левый угол внешнего цикла будет матрицей [0][0], а верхний левый угол внутреннего цикла будет матрицей[1][1]. Это дает нам подсказку — мы можем использовать цикл для определения любого угла в матрице.
пусть temp = матрица [цикл] [цикл]
пусть строки = matrix.count
// вверху слева == внизу слева
матрица[цикл][цикл] = матрица [строки — 1-цикл][цикл]
// внизу слева == внизу справа
матрица[строки — 1][цикл] = матрица[строки–1-цикл][строки–1-цикл]
// внизу справа == вверху справа
матрица[строки–1-цикл][строки–1-цикл] = матрица[цикл][строки–1-цикл]
// вверху справа == вверху слева (что теперь изменилось)
матрица[цикл][строки–1] = температура
Теперь это работает и для внутреннего куба (второй цикл, названный здесь 1).
Теперь мы можем обработать углы — но как насчет сторон?
Поверните середину
Середина кольца будет вращаться, перемещаясь в соответствующее место справа от квадрата. Мы можем повернуть два левых
пусть строки = matrix.count
пусть цикл = 0
матрица [цикл] [цикл + 1] = матрица [цикл + 2] [цикл]
матрица [цикл] [цикл + 2] = матрица [цикл + 1] [цикл]
поэтому матрица [цикл] [цикл + … до количества средних элементов] = матрица [цикл + … до количества средних элементов] [цикл]
Для любой матрицы будет число циклов
Четные матрицы =n / 2 цикла
Нечетные матрицы = n / 2 цикла + 1 (поскольку внутренний цикл будет одним целым числом)
Внешний цикл — количество циклов равно 0.
Внутренний цикл — количество циклов равно 1.
Способ 2: вращение со свопами
Есть возможность просто поменять местами определенные элементы в кубе:
Для эффективности мы меняем строки местами по мере продвижения:
Для каждой строки в матрице поменяйте местами квадрат с его обратным (если он есть).
Затем переверните строку матрицы, которая дает правильно упорядоченную строку.
Вывод
Это сложная проблема, но, безусловно, ее можно решить, потратив некоторое время на ее обдумывание и проникновение в суть проблемы. В равной степени практика работы с массивами может действительно помочь нам, когда мы решаем сложную задачу, подобную этой!
