Этот блог относится к «Javascript-версии структуры данных и алгоритма» Учителя Инь Гохуэй.
задний план
На самом деле, строго говоря, матрицу нельзя рассматривать как типичную структуру данных.
Причина, по которой матрица помещена в эту серию, заключается в том, что матрица очень часто появляется в интервью и письменных тестах.
Сегодня мы будем использовать js для реализации еще двух классических алгоритмических задач, связанных с матрицами, на LeetCode.
Определение матрицы не должно быть незнакомо студентам, изучавшим курс «Линейная алгебра» в колледже.Если некоторые студенты не понимают, они могут самостоятельно проверить энциклопедию Baidu.
Не много ерунды, давайте сразу к вопросу.
Спиральная матрица
LeetCode Вопрос 54Оригинальный титульный адрес
Сложность вопроса: средняя
Описание темы
Учитывая матрицу m x n элементов (m строк, n столбцов), вернуть все элементы в матрице в порядке спирали по часовой стрелке.
Пример 1:
输入: [ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] 输出: [1,2,3,6,9,8,7,4,5]
Пример 2:
输入: [ [1, 2, 3, 4], [5, 6, 7, 8], [9,10,11,12] ] 输出: [1,2,3,4,8,12,11,10,9,5,6,7]
Понимание темы
Вопрос требует, чтобы мы обходили каждый элемент по часовой стрелке снаружи внутрь и возвращали их по порядку.
Согласно этой картинке, мы должны четко понимать требования вопроса.Порядок возврата элементов, требуемых вопросом, на картинке от 1 до 16.
Анализ мыслей
Мы можем заметить:
Будь то матрица несколько × несколько, нам нужно пройти по внешнему кругу, прежде чем перейти к обходу соседних с ним элементов внутреннего круга.
Как показано на рисунке выше, мы рассматриваем 1-12 как первый круг, а 13-16 как второй круг, и второй круг будет пройден после того, как будет пройден весь первый круг.
Если есть матрица с более высоким порядком (больше кругов), то также будет обход третьего и четвертого круга.
Таким образом, мы можем думать об обходе каждого круга как о шаге, и повторение этого шага даст нужный нам результат.
Я полагаю, что некоторые студенты догадались, что мы должны решить эту задачу рекурсивно.
Далее, давайте посмотрим, как реализован код.
Код
arr => {
// map函数用来完成当前矩阵最外一圈的遍历
// @param1{Array}二维数组 arr 表示当前矩阵
// @param2{Array}一维数组 result 用来保存遍历结果
let map = (arr, result) => {
// 矩阵的高度即行数
let n = arr.length
// 遍历矩阵的每一行
for(let i = 0; i < n; i++){
// 若第一行 按顺序插入
if(i === 0){
result = result.concat(arr[i])
} else if (i === n-1){
// 若最后一行 倒序插入
result = result.concat(arr[i].reverse())
} else {
// 若中间行 插入该行最后一个元素 并将该元素从矩阵中删除
result.push(arr[i].pop())
}
}
// 将已经遍历的第一行和最后一行从矩阵中删除
arr.pop()
arr.shift()
// 遍历插入最左侧一列 此时删除首位两行后矩阵高度已变为n-2
for(let j = n - 3; j >= 0; j--){
// 避免arr[j]长度为空时插入undefined
if(arr[j].length){
result.push(arr[j].shift())
}
}
// 截止条件 矩阵有元素就继续递归
if(arr.length){
// 把已将遍历元素删除的矩阵进行递归
return map(arr, result)
}else{
return result
}
}
// 将初始矩阵传入, 保存结果的数组初始为空
return map(arr, [])
}думать
Некоторым учащимся может быть не совсем понятно, как мы думали о решении таких задач с помощью рекурсии.
Здесь, основываясь на личном опыте, я резюмирую три общих условия выполнения рекурсии:
- Операция может быть разбита на небольшие шаги, которые обрабатывают один и тот же процесс.
- Формат входных данных одинаков для каждого шага
- Неизвестное количество запусков
в этой теме
- Сначала разобьем обход по спирали по часовой стрелке на обход каждого круга
- Сначала мы получаем двумерный массив (матрицу), а после того, как каждый обход завершает круг, передаем новую матрицу, которая удаляет элементы самого внешнего круга, который также является двумерным массивом.
- Рекурсивно до тех пор, пока матрица не станет пустой (ширина и высота входящей матрицы не определяются)
Три условия рекурсии соблюдены.
Если вы столкнетесь с подобными проблемами в будущем, вы можете обратиться к этим трем пунктам, чтобы определить, можно ли использовать рекурсию.
Повернуть изображение
LeetCode Вопрос 48Оригинальный титульный адрес
Уровень сложности: средний
Описание темы
给定一个 n × n 的二维矩阵表示一个图像。 将图像顺时针旋转 90 度。
проиллюстрировать: Вам нужно повернуть изображение на месте, что означает, что вам нужно напрямую изменить входную 2D-матрицу.
Пожалуйста, не используйте другую матрицу для поворота изображения.
Пример 1:
Данная матрица =
[
[1,2,3],
[4,5,6],
[7,8,9]
],
Поверните входную матрицу на месте, чтобы она стала:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Пример 2:
Данная матрица =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
]
Поверните входную матрицу на месте, чтобы она стала:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
Понимание темы
Название понятно: поверните матрицу прямо по часовой стрелке, что чем-то похоже на функцию, которую мы обычно используем для поворота изображения на 90 градусов по часовой стрелке.
И причина, по которой эта задача называется «поворот изображения», заключается именно в том, что методом реализации этой задачи является принцип функции поворота изображения.
Анализ мыслей
На первый взгляд, эта проблема очень проста, нам нужно только создать новую матрицу (двумерный массив), а затем пройтись по каждому элементу исходной матрицы.
Столбцы добавляются в каждую строку новой матрицы в порядке снизу вверх.
Но сложность этого вопроса в том, что он требует от нас «повернуть изображение на месте», а значит, мы не можем создать новое двумерное число
Сгруппировать (матрицу), а затем добавить в нее данные, мы можем иметь дело только с исходной матрицей, тогда, если мы имеем дело с исходной матрицей, мы можем только поменять местами положения чисел
Другого пути нет.
Как его обменять?
Взяв пример 1 в качестве примера, сначала мы используем ось средней строки, чтобы сделать матрицу осесимметричной.
Затем используем диагональ 753 как ось осесимметричного
На этом этапе мы получаем желаемый результат, а затем реализуем его с помощью кода.
Код
arr => {
// 获取矩阵阶数
let n = arr.length
let temp
// 垂直翻转 考虑n的奇偶
for(let i = 0; i < Math.floor(n / 2); i++){
for(let j = 0; j< n; j++){
temp = arr[i][j]
arr[i][j] = arr[n -1 -i][j]
arr[n -1 -i][j] = temp
}
}
// 沿对角线反转
for(let p = 0;p < n - 1; p++){
for(let q = p + 1; q < n; q++){
temp = arr[p][q]
arr[p][q] = arr[q][p]
arr[q][p] = temp
}
}
return arr
}Суммировать
На LeetCode также есть много тем, связанных с матрицами. Вы можете попробовать его. Если у вас есть какие-либо вопросы о моем методе, вы можете прийти в область комментариев для обсуждения. Больше обменов мнениями приведет к прогрессу. Я надеюсь, что вы станет мастером как можно скорее.