Поговорим о фронтенд-алгоритме интервью — рекурсия

внешний интерфейс опрос
Поговорим о фронтенд-алгоритме интервью — рекурсия

Статья впервые опубликована на:GitHub.com/US TB-Вуд, умри, о ты…

написать впереди

Теперь конкуренция становится все более жестким, сегодня я буду говорить о идее алгоритма, которая выглядит очень часто в интерфейс-интервью - «Рекурсиция».

Вот некоторые распространенные вопросы на собеседовании:

  1. Если на лестнице n ступенек, то за один раз можно пройти 1 или 2 ступени.Сколько существует способов пройти эти n ступенек (реализация динамического программирования)❓
  2. Как показано на рисунке ниже: Робот расположен в верхнем левом углу сетки m x n (начальная точка отмечена как «Старт» на рисунке ниже). Робот может двигаться вниз или вправо только на один шаг за раз. Робот пытается достичь правого нижнего угла сетки (помеченного «Готово» на изображении ниже). Теперь учтите, что в сетке есть препятствия. Итак, сколько разных путей будет из верхнего левого угла в нижний правый угол❓

  1. В M элементах❓

Вы можете сначала подумать, как ответить на вопрос выше 🤔, а затем прочитать следующий контент с ответом.

Как написать рекурсивный код ❓

Рекурсивные идеи очень распространены в предварительных интервью.В дополнение к некоторым из вышеперечисленных тем рекурсивные идеи используются в обходе бинарных деревьев и последовательностей Фибоначчи до среднего и последующего порядка. Простое понимание рекурсии:позвони себе. Итак, как писать рекурсивный код❓ На мой взгляд:

В основном есть два ключевых шага:

  • Напишите рекурсивную формулу
  • найти условие завершения

Рассмотрим простой пример: как найти сумму 1+2+3+4+...+n? Думаю, все знают, как написать метод цикла for:

function sum(n) {
    var total = 0
    for (int i = 1; i <= n; i++) {
    	total = total + i
    }
    return total
}

Как перейти на рекурсивное письмо?

Шаг 1: Напишите рекурсивную формулу

Внимательное наблюдение обнаружит, что на самом деле это отношение между n и n-1 и n-2.

sum(n) = sum(n-1) + n
···
···
···
sum(100) = sum(99) + 100
sum(99) = sum(98) + 99
···
···
···
sum(5) = sum(4) + 5
sum(4) = sum(3) + 4
sum(3) = sum(2) + 3
sum(2) = sum(1) + 2
sum(1) = 1

Преобразование приведенного выше в рекурсивную формулу

function sum(n) {
    return sum(n-1) + n
}

Шаг 2: Найдите условие завершения

Выписывается рекурсивная формула, затем рекурсивный код выполнен более чем наполовину. Теперь давайте посмотрим, каково условие завершения вышеупомянутой задачи, то есть sum(1) = 1;

В сочетании с рекурсивной формулой и условием завершения рекурсивный код для суммирования 1+2+3+4+...+n выглядит следующим образом:

function sum(n) {
    if( n ===1 ) return 1
    return sum(n-1) + n
}

Вопрос интервью 1: вопрос о лестнице

Если на лестнице n ступенек, вы можете пройти 1 или 2 ступени за раз.Сколько путей вы сможете пройти, пройдя эти n ступеней❓

Согласно нашей идее выше, сначала напишите рекурсивную формулу. Так как же найти рекурсивную формулу для этой задачи? Предполагая, что есть 3 шага, у нас может быть 3 хода:

1 1 1
1 2
2 1

Первый — идти по одному шагу за раз. Второй - 1 шаг для первого шага и 2 шага для второго шага. Третий - сделать 2 шага для первого шага и 1 шаг для второго шага.

Запишите рекурсивную формулу:

А если n шагов? Если мы хорошенько об этом подумаем, то обнаружим, что есть два типа шагов для первого шага: первый — сделать один шаг на первом шаге, а второй — сделать два шага на втором шаге. Следовательно, способы ходьбы из n шагов можно разделить на: n-1 способов ходьбы после прохождения 1 шага плюс n-2 способа ходьбы после прохождения 2 шагов, что выражается рекурсивной формулой:

function climbStairs(n) {
    return climbStairs(n - 1) + climbStairs(n - 2)
}

Найдите условие завершения:

climbStairs(n) = climbStairs(n-1) + climbStairs(n-2)
climbStairs(n-1) = climbStairs(n-2) + climbStairs(n-3)
···
···
···
climbStairs(5) = climbStairs(4) + climbStairs(3)
climbStairs(4) = climbStairs(3) + climbStairs(2)
climbStairs(3) = climbStairs(2) + climbStairs(1)
climbStairs(2) = 2
climbStairs(1) = 1

Из приведенного выше вывода видно, что условие завершения:

climbStairs(2) = 2
climbStairs(1) = 1

Таким образом, код для решения подъема по лестнице выглядит следующим образом:

function climbStairs(n) {
  if (n == 1) return 1
  if (n == 2) return 2
  return climbStairs(n-1) + climbStairs(n-2)
}

Конечно, вы можете сделать операцию запоминания по вышеуказанной теме, и производительность будет намного лучше:

var calculated = []

function climbStairs(n) {

    if(n == 1) {
        return 1
    }else if (n == 2) {
        return 2
    }else {
        if(!calculated[n-1]){
            calculated[n-1] = climbStairs(n-1)
        }

        if(!calculated[n-2]){
            calculated[n-2] = climbStairs(n-2)
        }
        return calculated[n-1] + calculated[n-2]
    }

}

После решения задачи о подъеме по лестнице задумайтесь над решением задачи последовательности Фибоначчи, и некоторые найдут, что это та же самая задача и идея :)

Вопрос интервью 2: Внедрение глубокого копирования

Как использовать рекурсивное мышление для достижения глубокого копирования❓ Если вы хотите реализовать глубокое копирование, вам необходимо рассмотреть возможность копирования атрибутов объекта и атрибутов атрибутов.В этом случае очень удобно использовать рекурсивное мышление для решения проблема, и определить атрибуты, когда копия подходит Тип значения, если это объект, функция deeplClone вызывается рекурсивно, в противном случае значение свойства возвращается напрямую:

var deepCopy = function(obj) {
    if (typeof obj !== 'object') return;
    // // 根据obj的类型判断是新建一个数组还是对象
    var newObj = obj instanceof Array ? [] : {};
    for (var key in obj) {
        if (obj.hasOwnProperty(key)) {
            newObj[key] = typeof obj[key] === 'object' ? deepCopy(obj[key]) : obj[key];
        }
    }
    return newObj;
}

Вопрос из интервью 3: Как сгладить массив

Как использовать рекурсию для выравнивания массива❓, то есть как сгладить [1, [2], [3, [4, [5]]]], чтобы получить [1,2,3,4,5]❓

const flatten = (arr) => {
  let result = [];
  arr.forEach((item, i, arr) => {
    // 若为数组,递归调用 faltten,并将结果与result合并
    if (Array.isArray(item)) {
      result = result.concat(flatten(item));
    } else {
      result.push(arr[i])
    }
  })
  return result;
};
const arr = [1, [2, [3, 4, 5]]];
console.log(flatten(arr)); // [1, 2, 3, 4, 5]

Суммировать

Ключ к написанию рекурсивного кода — найти рекурсивную формулу и условия завершения и, наконец, преобразовать их в код. Однако рекурсивный код проще. Но есть и много недостатков, например, производительность не очень эффективна, в настоящее время для оптимизации производительности необходимы некоторые операции, такие как запоминание. Легко вызвать такие проблемы, как переполнение стека, поэтому мы должны обращать на это внимание при написании кода.

Можете обратить внимание на мой паблик-аккаунт «Muchen Classmate», фермера на гусиной фабрике, который обычно записывает какие-то банальные мелочи, технологии, жизнь, инсайты и срастается.

Категории