Я работал над своими навыками работы с алгоритмами и недавно наткнулся на упражнение, которое, хотя и было простым, оказалось одновременно забавным и обманчиво сложным. Нам дан массив, состоящий из n массивов. Каждый массив, в свою очередь, также имеет длину n:
[[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]]
Наша задача - взять матрицу и распечатать ее содержимое, начиная с первого номера, а затем продолжать делать это по спирали по часовой стрелке до тех пор, пока печатать больше нечего.
С текущей матрицей результат должен быть 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10.
Как подойти?
Лучший способ подойти к этой проблеме - распознать ряд закономерностей:
- Сначала нам нужно получить горизонтальный ряд целиком.
- Затем нам нужно получить последний элемент каждой оставшейся строки.
- Затем нам нужно получить остальные элементы нижнего ряда в обратном порядке.
- Затем нам нужно получить первый элемент из оставшихся строк снизу вверх.
- Наконец, мы используем рекурсию, чтобы повторить все, ЕСЛИ есть какие-либо оставшиеся элементы, пока мы не получим их все.
Следующее изображение может помочь визуализировать шаблоны. Мы начинаем с 1 и проходим матрицу:
Хорошо, приступим к работе
Шаг 0: давайте построим скелет функции
Это в значительной степени говорит само за себя. Нам просто нужно написать функцию, которая будет служить основой для нашей работы:
// Wel'll use this variable to fill with the numbers we're going to take from our matrix:
let endResult = [];
unrollMatrix = (array) => {
// This is our condition to check for any remaining elements and break out of recursion and give us the end result
if(array.length === 0) {
console.log(endResult.join(', '));
return;
}
// 1.- Get the top row
// 2.- Get the last element of all remaining rows
// 3.- Get what's left of the bottom row in reverse
// 4.- Get the first element of any remaining rows
// 5.- Make the function call itself over whatever's left of our original matrix
}
Довольно простые вещи. Флажок вверху означает: «Продолжайте работать, пока ничего не будет, а когда это произойдет, распечатайте все числа в виде простого списка строк».
Шаг 1. Получите верхний ряд:
Это очень просто. Все, что нам нужно сделать, это сдвинуть, а затем поместить нашу матрицу в массив endResult. Используя оператор распространения, мы обязательно «экранируем» массив и получаем голые числа. Помните, что мы работаем с массивом массивов, и если бы мы опускали оператор распространения, мы бы получили первую строку в виде массива:
endResult.push(...array.shift());
Важно следить за тем, что происходит, поэтому имейте в виду, что и endResult, и наша исходная матрица содержат значения, отличные от тех, с которыми мы начали, поэтому на данном этапе endResult представляет собой массив:
endResult: Array(4) [ 1, 2, 3, 4 ]
В то время как наша исходная матрица «потеряла» первую строку, когда мы ее сдвинули:
matrix: Array(3) [[5, 6, 7, 8],
[9, 10, 11, 12],
[13, 14, 15, 16]];
Шаг 2. Получите последний элемент всех оставшихся строк
Пока нам удалось получить первую строку, и теперь нам нужна «правая часть» нашей матрицы. Это означает 8, 12 и 16. Для этого нам нужно написать быстрый цикл, чтобы перебирать все оставшиеся массивы, получать их последний элемент и передавать его в нашу переменную endResult:
for(piece of array){
endResult.push(piece.pop());
}
КТО, что здесь происходит? Не бойтесь, это просто более лаконичный способ написания цикла for. Он был введен в ES2015 и отбрасывает любые счетчики и условия для итерации по объекту. Проверьте эту статью MDN для более подробного изучения.
Вернемся к нашему примеру, мы собираемся перебирать объект arr, и на каждой итерации его компоненты будут называться «кусок». Итак, для каждого «кусочка» в нашей исходной матрице мы собираемся вытолкнуть их последний элемент и вставить его в нашу переменную endResult.
Проверка хода выполнения: наша переменная endResult должна выглядеть так:
endResult: Array(7) [ 1, 2, 3, 4, 8, 12, 16 ]
И наша исходная матрица должна выглядеть так:
matrix: Array(3) [[5, 6, 7],
[9, 10, 11],
[13, 14, 15,]];
Шаг 3. Получите то, что осталось от нижнего ряда, в обратном порядке
Мы на полпути! Теперь нам нужно получить нижнюю строку в обратном порядке, что означает 15, 14 и 13. Все, что нам нужно сделать, это вызвать нашу матрицу с помощью оператора распространения, вытащить последний элемент и вставить его в наш endResult в обратном порядке:
endResult.push(...array.pop().reverse());
Довольно просто. Это похоже на первый шаг, только на этот раз мы используем pop (), чтобы получить последний элемент вместо первого, а затем нажимаем его с помощью reverse ().
Проверка выполнения: endResult теперь должен выглядеть так:
endResult: Array(10) [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13 ]
И наша матрица должна выглядеть так:
matrix: Array(2) [[5, 6, 7],
[9, 10, 11]];
Шаг 4. Получите первый элемент из оставшихся строк.
Мы почти там! На этом последнем шаге нам нужно получить первый элемент каждого оставшегося массива снизу вверх, что в нашем случае будет 9, 5. Для этого нам просто нужно отобразить наши массивы, вызвать для них shift () и вставьте их в endResult в обратном порядке:
endResult.push(...array.map(arr => arr.shift()).reverse());
Наша функция почти готова, и теперь endResult должен выглядеть так:
endResult: Array(12) [ 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5 ]
И наша матрица должна выглядеть так:
matrix: Array(2) [[6, 7],
[10, 11]];
Теперь все, что нам нужно сделать, это сделать так, чтобы функция вызывала себя поверх всего, что осталось от нашей исходной матрицы:
unrollMatrix(array);
И готово! Если ваше условие выхода работает нормально, вы должны получить ожидаемый результат:
1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10
Есть куда расти
То, что наша функция работает, не означает, что мы закончили. Нам нужно контролировать нашу временную сложность, и пока наша функция состоит из четырех основных операций. Давайте посмотрим на них и посмотрим, что можно улучшить:
endResult.push(...array.shift());
Это О (1), у нас все хорошо.
for(piece of array){
endResult.push(piece.pop());
}
Это О (п), мы хороши, но не совсем.
endResult.push(...array.pop().reverse());
Это O (1), так что у нас все хорошо.
endResult.push(...array.map(arr => arr.shift()).reverse());
И, наконец, этот тоже O (1), так что у нас все еще хорошо.
Так что по большей части наша функция хороша. Если бы у нас не было альтернативы, временная сложность O (n) вполне подойдет, но если есть место для перехода от O (n) к O (1), то мы должны попытаться сделать это во что бы то ни стало:
endResult.push(...array.map(arr => arr.pop()))
Просто избавившись от цикла for, нам удалось упростить внутреннюю работу нашей функции и тем самым снизить нашу временную сложность до O (1). Мы могли бы сделать это с самого начала, но я считаю, что отслеживание нашей временной сложности не менее важно, чем обеспечение работы нашей функции. Имейте в виду, что системы масштабируемы, поэтому то, что они хорошо работают на нашем компьютере, не означает, что они будут нормально работать с большим набором данных в реальной среде.
Окончательный код
const matrix = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 10, 11, 12], [13, 14, 15, 16]];let endResult = [];unrollMatrix = (array) => {// This is our condition to check for any remaining elements and break out of recursion and give us the end result if(array.length === 0) { console.log(endResult.join(', ')); return; } // 1.- Get the top row endResult.push(...array.shift());// 2.- Get the last element of all remaining rows endResult.push(...array.map(arr => arr.pop()));// 3.- Get what's left of the bottom row in reverse endResult.push(...array.pop().reverse());// 4.- Get the first element of any remaining rows endResult.push(...array.map(arr => arr.shift()).reverse());// 5.- Make the function call itself over whatever's left of our original matrix unrollMatrix(array); }unrollMatrix(matrix); // 1, 2, 3, 4, 8, 12, 16, 15, 14, 13, 9, 5, 6, 7, 11, 10
