Разговор о тесте на собеседовании - рекурсивное мышление и реальный бой

В этой статье вы узнаете

зачем писать эту статью

"Рекурсивный" алгоритм следует рассматривать как один из самых классических алгоритмов для программиста, и чем больше вы думаете о нем, тем более он хаотичен. Реализация многих сложных алгоритмов также использует рекурсию, например, поиск в глубину, обход бинарного дерева и т.д.
На собеседованиях часто задают контент, связанный с рекурсией (глубокое копирование, форматирование объектов, выравнивание массива, пошаговые вопросы и т. д.).
В последнее время в проекте есть спрос, деление, но не только рибейты шешерам, но и рибейты финалистам, а только 4-уровневое распределение (также используется рекурсия, о чем будет рассказано в статье)

Об авторе: koala, сосредоточив внимание на совместном использовании полного стека технологий Node.js, от JavaScript до Node.js, до серверной базы данных, я желаю вам стать отличным старшим инженером Node.js. [Руководство по развитию программиста] Автор, блог Github с открытым исходным кодомGitHub.com/koala-co Nth…

Что такое рекурсивный алгоритм

维基百科: 递归используется в самом определении функции. Функция с таким определением называется рекурсией. Звучит так, как будто это приведет к бесконечному повторению, но пока оно правильно определено, этого не произойдет. В общем случае определение рекурсивной функции состоит из двух частей. Во-первых, должна быть хотя бы одна нижняя строка, то есть простая строка, дальше этой,递归.

Мое собственное простое понимание рекурсии:自己调用自己，有递有归，注意界限值.

Интересная картина:

Идеи рекурсивного алгоритма и меры предосторожности

Когда использовать рекурсию?

Взгляните на небольшой пример, который произошел во время 11-го праздника, и погрузитесь в рекурсию. Я пошел на вокзал, чтобы встать в очередь, чтобы забрать билеты во время ноябрьских праздников.В очереди было много людей.В это время всегда находились какие-то друзья, которые говорили, что уже слишком поздно прыгать в очередь, чтобы забрать билеты, чем дальше, тем больше хочется знать, где я сейчас нахожусь (посылка: никто не будет лезть в очередь за билетами), что делать с рекурсивным мышлением?

удовлетворять рекурсивному условию

Задача должна удовлетворять только следующему3Условие может быть решено рекурсией.

Решение проблемы можно разложить на решения нескольких подзадач.

В чем заключается подзадача? Это вопрос меньшего размера данных. Например, в предыдущем примере, где вы хотите узнать, где вы находитесь в рейтинге, вам нужно знать, в какой строке вы находитесь, что можно разложить на подвопрос о том, в какой строке все находятся.

Подзадачи после этой проблемы декомпозируются, за исключением того, что масштаб данных другой, идеи решения точно такие же

Например, в предыдущем примере вы хотите знать, где вы находитесь в рейтинге, вы хотите узнать, в какой строке вы находитесь, и люди в первом ряду, чтобы узнать, в какой строке вы находитесь,точно так жеиз.

Существует рекурсивное условие завершения

Например, в упомянутом выше примере, где вы хотите узнать, где вы находитесь в первом ряду, людям в первом ряду не нужно продолжать спрашивать кого-либо еще, в каком ряду они находятся, то естьf(1) = 1, это условие завершения рекурсии, и процесс «возврата» начнется, когда условие завершения будет найдено.

Как написать рекурсивный код? (Выполните указанные выше условия после подтверждения использования рекурсии)

Запомните два самых важных момента:

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

Пример анализа очередей за билетами (`单分支层层递归`)

Разобрана подзадача примера стояния в очереди за билетами.Если я хочу узнать, в каком ряду моя позиция, я спрошу у человека впереди.Положение человека впереди плюс один - это позиция человека в текущей команде. Человек перед вами хочет знать. Продолжить. Вы нашли формулу рекурсии?

f(n) = f(n-1) + 1
//f(n) 为我所在的当前层
//f(n-1) 为我前面的人所在的当前层
// +1 为我前面层与我所在层

Давайте посмотрим на другой пример ходьбы по лестнице (`多分支并列递归`)

Узнайте, как анализировать и писать рекурсивный код, и объясните это на самом классическом примере шагов ходьбы.

вопрос: Предположим, что есть n ступеней, каждый раз, когда вы можете подняться на одну или две ступени, сколько существует способов пройти эти n ступенек? Решить программированием.

В соответствии с ключевыми моментами, упомянутыми выше, сначала найдитерекурсивная формула: В соответствии с первым шагом его можно разделить на две категории: первая категория — это первый шаг и один шаг, а вторая категория — это первый шаг и два шага. Таким образом, метод ходьбы из n шагов = (метод ходьбы из n-1 шагов после прохождения 1 шага) + (метод ходьбы из n-2 шагов после прохождения 2 шагов). Написана рекурсивная формула:

f(n) = f(n-1)+f(n-2)

С рекурсивной формулой второй шаг имеет рекурсивную формулу, и рекурсивный код в основном завершен наполовину. Давайте еще раз посмотрим на условие завершения. Когда есть шаг, нам не нужно продолжать рекурсию, есть только один путь. такf(1)=1. Достаточно ли этого рекурсивного условия завершения? мы можем использоватьn=2，n=3Поэкспериментируйте с такими маленькими числами.

n=2час,f(2)=f(1)+f(0). Если есть только одно рекурсивное условие завершенияf(1)=1,Тотf(2)не может быть решен. Итак, кромеf(1)=1В дополнение к этому рекурсивному условию завершения существуют такжеf(0)=1, что указывает на то, что есть способ пройти 0 шагов, но это, похоже, не соответствует нормальному логическому мышлению. Итак, мы можем положитьf(2)=2В качестве условия прекращения это означает пройти 2 шага, есть два способа пройти, один шаг или два шага.

Итак, условие рекурсивного завершенияf(1)=1，f(2)=2. В это время вы можете взятьn=3，n=4Проверим, что это условие завершения является достаточным и корректным.

Мы объединяем рекурсивное условие завершения с рекурсивной формулой, которую мы только что ввели:

f(1) = 1;
f(2) = 2;
f(n) = f(n-1)+f(n-2);

Наконец, согласно окончательной рекурсивной формуле, преобразованной в код,

function walk(n){
    if(n === 1) return 1;
    if(n === 2) return 2;
    return f(n-1) + f(n-2)
}

Соображения при написании рекурсивного кода

Два примера упомянуты выше (приход на станцию в очередь за билетами 11-го и прохождение шагов), согласно этим двум примерам (причины выбора этих двух примеров, проблема стояния в очереди на вокзале 11-го числа). забрать билеты - задача одноветвевой рекурсии, а задача прохождения шагов) Многоветвевая параллельная рекурсия, два примера刚刚好), давайте поговорим о рекурсии подробнее.

1. Взрывной стек

На одиннадцатый день идите на станцию, чтобы встать в очередь за билетами.Предполагая, что это непобедимая длинная очередь, в очереди может быть 1000 человек (хе-хе, обратите внимание, что это предположение).В это время, если размер стека 1 КБ. Когда рекурсия не учитывает взрыв стека, код выглядит следующим образом:

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

Вызовы функций используют стек для хранения временных переменных. Структура данных стека先进后出, каждый раз, когда вызывается функция, временная переменная инкапсулируется как栈帧запихивать в内存栈, и извлекает стек только тогда, когда выполнение функции завершается и возвращается. Системный стек или пространство стека виртуальной машины, как правило, невелико. Если данные, подлежащие рекурсивному решению, очень велики, уровень вызова глубокий и они все время помещаются в стек, существует риск переполнения стека.

Напишите такой код для этого гипотетического无敌长队Обязательно будет взрыв стека, модифицируйте код

// 全局变量，表示递归的深度。
let depth = 0;

function f(n) {
  ++depth；
  if (depth > 1000) throw exception;
  
  if (n == 1) return 1;
  return f(n-1) + 1;
}

После изменения кода добавляется ограничение на количество рекурсий, чтобы предотвратить взрыв стека.Это хороший способ предотвратить взрыв стека.Однако обратите внимание, что ограничение на количество рекурсий обычно не ограничивается 1000, обычно 5 раз, 10 раз К счастью, 1000 раз, нет гарантии, что другие переменные не будут храниться в стеке и не могут быть рассчитаны заранее , также может возникнуть проблема взрыва стека.

Напоминание: если глубина рекурсии относительно мала, вы можете ограничить количество рекурсий, чтобы предотвратить взрыв стека.1000Глубина, или рассмотреть другие способы ее достижения.

2. Двойной счет

Для примера выполнения шагов мы вывели рекурсивную формулу и реализацию кода ранее. Напишите еще раз сюда:

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

Вот о чем идет речь при повторном вычислении.Может быть вы этого не понимаете.Если вы рисуете схему многократного вызова функции,то должны понимать.

Глядя на вызовы функций на рисунке, вы обнаружите, что многие функции вызываются несколько раз, напримерf(3),рассчитатьf(5)время вычислитьf(4)иf(3), вычислятьf(4)также рассчитать, когдаf(3)иf(2), этоf(3)Это повторялось много раз, решение. Мы можем использовать структуру данных (примечание: эта структура данных может иметь много видов, например, js может использоватьset,weakMap, даже с массивами. В java тоже есть много видов хеш-таблиц.Думающие детские ботинки могут подумать,какая из них лучше.О примере с глубоким копированием я также расскажу позже) для хранения решенных.f(k), при повторном вызове оценивается, существует ли он в структуре данных.Если есть значение, возвращаемое непосредственно из хеш-таблицы, нет необходимости повторять вычисление, что позволяет избежать проблемы повторного вычисления. Конкретный код выглядит следующим образом:

let mapData =new Map();
function walk(n){
    if(n === 1) return 1;
    if(n === 2) return 2;
    // 值的判断和存储
    if(mapData.get(n)){
        return mapData.get(n);
    }
    let value = walk(n-1) + walk(n-2);
    mapData.set(n,value);
    return value;
}

3. Циркулярные ссылки

Циклическая ссылка относится к повторяющемуся контенту в рекурсивном контенте. Например, реализуйте глубокую копию для следующего:

const target = {
    field1: 1,
    field2: undefined,
    field3: {
        child: 'child'
    },
    field4: [2, 4, 8]
};
target.target = target;

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

Немного о рекурсивных алгоритмах

Три условия, которые выполняются при использовании рекурсивного алгоритма, упоминались ранее.После определения того, что условия выполняются, ключевые моменты при написании рекурсивного кода ((Напишите рекурсивную формулу и найдите условие завершения), этот ключевой момент упоминался в тексте три раза, пожалуйста, запомните его, и, наконец, переведен в код в соответствии с рекурсивной формулой и условиями завершения.

Рекурсивный код, не пытайтесь использовать наш мозг для декомпозиции каждого шага рекурсии слой за слоем, это только сделает вас более раздражительным, даже великие боги не могут этого сделать.

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

Сценарии использования рекурсивного алгоритма (несколько вопросов интервью, упомянутых в начале)

При написании следующих практических задач сценариев приложений,思想Как я уже сказал, повторите (Напишите рекурсивную формулу и найдите условие завершения)

1. Классическая ступенчатая задача

Проблема принятия шагов уже подробно обсуждалась ранее, поэтому я не буду здесь вдаваться в подробности, вы можете прочитать содержание выше.

2. Четыре уровня раздачи - найди лучших рефералов

Учитывая пользователя, как найти окончательную рекомендацию пользователяid, Он сказал, что четыре уровня распределения, условия прекращения были найдены, только найдены四级分销 . Код:

let deep = 0;
function findRootReferrerId(actorId) {
  deep++;
  let referrerId = select referrer_id from [table] where actor_id = actorId;
  if (deep === 4) return actorId; // 终止条件
  return findRootReferrerId(referrerId);
}

Хотя можно завершить код таким образом, необходимо отметить следующие предварительные условия:

нет в базе脏数据(Грязные данные могут быть сгенерированы путем ручной вставки данных непосредственно из теста. Например, A рекомендует B, а B рекомендует A, что приводит к бесконечному циклу и циклической ссылке).
При подтверждении того, что рекомендатель вставляет данные в таблицу, обязательно определите, существует ли уже предыдущая рекомендательная связь между ними.

3. Сглаживание массива

let a = [1,2,3, [1,2,[1.4], [1,2,3]]]

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

function flat(a=[],result=[]){
    a.forEach((item)=>{
        console.log(Object.prototype.toString.call(item))
        if(Object.prototype.toString.call(item)==='[object Array]'){
            result=result.concat(flat(item,[]));
        }else{
            result.push(item)
        }
    })
    return result;
}
console.log(flat(a)) // 输出结果 [ 1, 2, 3, 1, 2, 1.4, 1, 2, 3 ]

4. Форматирование объекта

Проблема форматирования объектов, это обычно данные возвращаемые из бэкенда во фронтенд, иногда нужно форматировать кейс и т.д.. В общем, уровень не слишком глубокий и не нуждается в рассмотрении.终止条件, подробности см. в коде

// 格式化对象 大写变为小写
let obj = {
    a: '1',
    b: {
        c: '2',
        D: {
            E: '3'
        }
    }
}
function keysLower(obj){
    let reg = new RegExp("([A-Z]+)", "g");
        for (let key in obj){
            if(Object.prototype.hasOwnProperty.call(obj,key)){
                let temp = obj[key];
                if(reg.test(key.toString())){
                    temp = obj[key.replace(reg,function(result){
                        return result.toLowerCase();
                    })]= obj[key];
                    delete obj[key];
                }
                if(Object.prototype.toString.call(temp)==='[object Object]'){
                    keysLower(temp);
                }
            }
        }
    return obj;
}
console.log(keysLower(obj));//输出结果 { a: '1', b: { c: '2', d: { e: '3' } } }

5. Реализуйте глубокую копию

const target = {
    field1: 1,
    field2: undefined,
    field3: {
        child: 'child'
    },
    field4: [2, 4, 8]
};
target.target = target;

Код реализован следующим образом:

function clone(target, map = new WeakMap()) {
    if (typeof target === 'object') {
        let cloneTarget = Array.isArray(target) ? [] : {};
        if (map.get(target)) {
            return map.get(target);
        }
        map.set(target, cloneTarget);
        for (const key in target) {
            cloneTarget[key] = clone(target[key], map);
        }
        return cloneTarget;
    } else {
        return target;
    }
};

Глубокое копирование также является распространенным примером рекурсии.

Что происходит с каждой копией:

Проверить карту на наличие клонированных объектов
Да, вернуться напрямую
Нет, сохранить текущий объект в качестве ключа и клонированный объект в качестве значения
продолжать клонировать

В этом коде мы использовалиweakMap, используемый для предотвращения взрыва стека из-за циклических ссылок.

слабые карты дополнительных знаний

Мы все знаем, что в js есть много структур хранения данных, почему мы используем weakMap вместо непосредственного использования Map для хранения?

Объект WeakMap также представляет собой набор пар ключ/значение, где на ключи слабо ссылаются. Его ключи должны быть объектами, а значения могут быть произвольными.

Концепция слабой ссылки по-прежнему часто используется при написании кода Java, но не так много друзей, которые могут использовать ее в JavaScript.Многие коды глубокого копирования в Интернете напрямую используются для хранения карт, чтобы предотвратить взрыв стека.弱引用, после прочтения этой статьи можно попробовать использовать WeakMap.

В компьютерном программировании слабая ссылка противоположна сильной ссылке и относится к ссылке, которая не может гарантировать, что объект, на который она ссылается, не будет утилизирован сборщиком мусора. Объект считается недоступным (или слабодоступным), если на него ссылаются только слабые ссылки, и поэтому его можно собрать в любое время.

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

Суммировать

Эта статья написана здесь.На самом деле, есть еще проблемы сложности, которые я хочу написать, но место ограничено.Я напишу статью о сложности в будущем, когда будет время. Эта статья посвящена повторению другой статьи, не люби мое нытье, при каких условиях использовать рекурсию (подумайте о преимуществах и недостатках использования рекурсии)? Как написать рекурсивный код? Соображения рекурсии? Не пытайтесь использовать человеческий мозг, чтобы понять сложную рекурсию. Изучив вышеперечисленные пункты, вам достаточно, чтобы ответить на большинство вопросов на собеседовании, хе-хе, обратите внимание на свои мысли (есть такжеweakMapМало знаний можно изучить подробно, а можно и развернуть в статью). Если у вас есть время, вы можете найти несколько рекурсивных задач для практики. До встречи в следующей статье!

Справочная статья

Завтра и вечером:nuggets.capable/post/684490…
код Тайный сад:nuggets.capable/post/684490…
Рекурсивное обучение для гиков

Присоединяйтесь к нам, чтобы учиться вместе! (Добавьте друга coder_qi в группу обмена интерфейсом, чтобы узнать)