Готовясь к собеседованию, я немного потренировал свои навыки работы с алгоритмами на LeetCode и других сайтах. Продолжайте читать, чтобы ознакомиться с пошаговым руководством по моему JavaScript-решению проблемы с переворачиванием изображения на LeetCode (инструкции от LeetCode приведены ниже).

Проблема

Учитывая двоичную матрицу A, мы хотим перевернуть изображение по горизонтали, затем инвертировать его и вернуть полученное изображение.

Переворот изображения по горизонтали означает, что каждая строка изображения перевернута. Например, поворот [1, 1, 0] по горизонтали приводит к [0, 1, 1].

Инвертирование изображения означает, что каждый 0 заменяется на 1, а каждый 1 заменяется на 0. Например, инвертирование [0, 1, 1] приводит к [1, 0, 0].

Пример 1:

Input: [[1,1,0],[1,0,1],[0,0,0]]
Output: [[1,0,0],[0,1,0],[1,1,1]]
Explanation: First reverse each row: [[0,1,1],[1,0,1],[0,0,0]].
Then, invert the image: [[1,0,0],[0,1,0],[1,1,1]]

Пример 2:

Input: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
Output: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
Explanation: First reverse each row: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]].
Then invert the image: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]

Примечания:

  • 1 <= A.length = A[0].length <= 20
  • 0 <= A[i][j] <= 1

Решение

А теперь приступим! В объяснении решения я буду использовать первый пример ввода, предоставленный LeetCode, чтобы продемонстрировать, что происходит с помощью функции: [[1,1,0], [1,0,1], [0,0,0]] .

Мы возьмем A (исходный массив) и преобразуем его значения для возврата, поэтому нам не нужно будет создавать новый массив для нашего результата. Чтобы добраться до нашего решения, мы должны сначала перевернуть изображение по горизонтали, что потребует изменения порядка элементов в массиве A.

Наше решение будет состоять из вложенных циклов for для итерации по массиву массивов, поэтому для экономии дополнительных вычислений каждый раз, когда мы проходим через наш внутренний цикл, давайте объявим переменную длины, чтобы сохранить длину массива в A. Потому что мы знаем, что каждый массив в A будет иметь одинаковую длину из-за структуры матрицы, мы можем просто найти длину первого массива в A, не беспокоясь о правильной работе цикла.

Затем давайте создадим наш внешний цикл для перемещения через A, который в данном случае будет иметь 3 итерации: 1 [1,1,0], 2 [1,0, 1], 3 [0,0,0]. Поскольку A - это массив массивов, мы также должны пройти через каждый из внутренних массивов, чтобы мы могли коснуться каждого отдельного элемента. Вот код, который у нас есть на данный момент, оставляя место во внешнем цикле для последующего внутреннего цикла.

var flipAndInvertImage = function(A) {
    const length = A[0].length;
    for (let i = 0; i < A.length; i++) {
              ...
    }
};

Мы будем выполнять все преобразования в нашем внутреннем цикле. Начиная с индекса 0, мы будем перебирать каждый массив в A до тех пор, пока индекс не станет равным или больше половины длины любого из массивов, поскольку индекс будет увеличиваться с каждым проходом. Перебирая только половину каждого массива, мы можем избежать многократного преобразования одних и тех же элементов.

Чтобы помочь нам преобразовать A, мы создадим временную переменную под названием curr, чтобы сохранить значения в текущем элементе внутреннего цикла, A [i] [j]. В цикле [[1,1,0], [1,0,1], [0,0,0]] curr коснется первых двух элементов, 0 и 1, каждого массива в A. Ведение журнала консоли значение curr в цикле дает нам (по порядку): 1, 1, 1, 0, 0, 0.

А теперь приступим к преобразованию! Мы собираемся начать с замены значения A [i] [j] на противоположное (0, если 1, и наоборот) текущего значения в A [i] [length -1 -j]. Элемент, который мы сейчас зацикливаем, теперь перевернут по горизонтали И инвертирован. Например, наш первый массив в A изначально был [1,1,0]. Пока при j = 0 массив равен [1, 1, 0], потому что 1 был перевернут на противоположное 0, то есть 1. Если мы продолжим, при j = 1 массив будет [1,0,1 ], потому что мы переворачиваем элемент с самим собой и инвертируем его, меняя 1 на его противоположность, 0. Нам просто нужно сделать еще одну вещь, чтобы завершить преобразование. Поскольку значение в A [i] [length -1 -j] находится в A [i] [j], у нас будет значение в A [i] [length -1 -j], равное исходному значению curr, предварительное преобразование. Теперь первый массив равен [1,0,0].

После возврата преобразованного массива A за пределы обоих циклов у нас есть готовое решение, и теперь все тесты должны быть пройдены! Время выполнения этого решения - O (n²).

Вы можете найти проблему на LeetCode здесь!

Спасибо за чтение!