Предварительный письменный тест и серия интервью по восхождению на яму --- алгоритм

интервью внешний интерфейс алгоритм JavaScript

Обновление 20.08.2018 Добавлены связанные понятия и содержимое двоичного дерева.

18.08.2018 Обновлена ​​ошибка, указанная в области комментариев, спасибо за отзыв (￣▽￣)"

Наконец, связанный с алгоритмом. На самом деле я лично понимаю, что требования к алгоритмам на фронтенд-позициях гораздо ниже, чем на других ИТ-позициях. Но Xiaobai, после обучения в крупных компаниях, таких как Ant Financial и NetEase, я все еще чувствую, что необходимо освоить некоторые основные алгоритмы и идеи. Затем подведите итог тому, с чем вы столкнулись и узнали об алгоритмах, чтобы вы могли подготовиться к собеседованию в любое время.

Портал серии:

1. Приключения осеннего набора ВКонтакте (1)

2. Приключения осеннего набора ВКонтакте (2)

3. Приключения осеннего набора ВКонтакте (3)

4. Приключения осеннего набора ВКонтакте (4)

5. Дополнительная часть: предварительное собеседование и алгоритм письменного тестирования Алгоритм

Сортировать

Сам метод сортировки массива JS может соответствовать многим сценариям в повседневных бизнес-операциях, поэтому я думаю, что именно поэтому базовое собеседование позволит вам напрямую написать快速排序, потому что кажется, что другие методы сортировки не имеют особого смысла в JS.

Но в интервью Pinduoduo интервьюер все же попросил меня писать от руки选择排序 冒泡排序и快速排序псевдокод. Так как есть шанс обобщить, просто напишите все заново, от базовой сортировки до расширенной сортировки.

Основной алгоритм сортировки

Основная идея базовой сортировки очень похожа, и метод, используемый для перестановки, в основном представляет собой набор вложенных циклов for: внешний цикл перебирает каждый элемент массива, а внутренний цикл используется для сравнения элементов.

Пузырьковая сортировка

Самый глупый, самый простой и самый классический метод, какой бы язык вы ни изучали, когда дело доходит до сортировки, первый контакт — это он. Основная идея слишком классическая, поэтому множественное число ей не нужно.Давайте непосредственно проиллюстрируем процесс на примере:

E A D B H

После одной перестановки становится

A E D B H

Первые два элемента меняются местами, а следующим становится:

A D E B H

Поменяйте местами второе и третье, продолжайте:

A D B E H

Третий и четвертый элементы меняются местами, и, наконец, второй и третий элементы снова меняются местами, в результате получается окончательная последовательность:

A B D E H

Хорошо, на самом деле базовое мышление — это сравнение одного за другим, затем реализуйте его:

function bubleSort(arr) {
    var len = arr.length;
    for (let outer = len ; outer >= 2; outer--) {
        for(let inner = 0; inner <=outer - 1; inner++) {
            if(arr[inner] > arr[inner + 1]) {
                let temp = arr[inner];
                arr[inner] = arr[inner + 1];
                arr[inner + 1] = temp;
            }
        }
    }
    return arr;
}

Здесь следует отметить две вещи:

  1. Внешний цикл начинает уменьшаться от максимального значения, потому что внутренний слой сравнивается попарно, поэтому самый внешний слой>=2остановиться, когда
  2. Внутренний слой представляет собой попарное сравнение, начиная с 0, сравниваяinnerиinner+1, поэтому критическое состояниеinner<outer -1

При сравнении обменов это самая классическая стратегия обмена в компьютерах с использованием временных переменных.tempСохраните значение, но интервьюер спросил меня,Есть ли простой способ сделать это в ES6?Да, следующим образом:

arr2 = [1,2,3,4];
[arr2[0],arr2[1]] = [arr2[1],arr2[0]]  //ES6解构赋值
console.log(arr2)  // [2, 1, 3, 4]

Таким образом, поддельную сортировку только что можно оптимизировать следующим образом:

function bubleSort(arr) {
    var len = arr.length;
    for (let outer = len ; outer >= 2; outer--) {
        for(let inner = 0; inner <=outer - 1; inner++) {
            if(arr[inner] > arr[inner + 1]) {
                [arr[inner],arr[inner+1]] = [arr[inner+1],arr[inner]]
            }
        }
    }
    return arr;
}

сортировка выбором

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

С предзнаменованием только что, я не думаю, что есть необходимость демонстрировать, это очень просто: внешний цикл начинается с 0 доlength-1, а потом внутреннее сравнение, самую маленькую отпусти голову, а ты иди:

function selectSort(arr) {
    var len = arr.length;
    for(let i = 0 ;i < len - 1; i++) {
        for(let j = i ; j<len; j++) {
            if(arr[j] < arr[i]) {
                [arr[i],arr[j]] = [arr[j],arr[i]];
            }
        }
    }
    return arr
}

Просто несколько слов:

  • внешний циклiУказывает количество раундов,arr[i]Означает самую переднюю (маленькую) позицию в текущем раунде;
  • внутренний слой изiНачните, считайте в обратном порядке по очереди, найдите меньшее, чем начало, и поменяйтесь местами.

Готово, закругляйтесь! !

Сортировка вставками

Суть сортировки вставками — идея игральных карт:Я просто думаю, что играю в покер, беру один, неважно, куда его положить, беру другой, который меньше первого, кладу слева, продолжаю брать, может быть средний номер, просто вставьте его в середину....

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

  • Сначала возьмите первую запись, которая будет отсортирована как упорядоченный сегмент.
  • От второго до последнего сравните его с предыдущим упорядоченным сегментом по очереди, чтобы определить позицию вставки.
function insertSort(arr) {
    for(let i = 1; i < arr.length; i++) {  //外循环从1开始，默认arr[0]是有序段
        for(let j = i; j > 0; j--) {  //j = i,将arr[j]依次插入有序段中
            if(arr[j] < arr[j-1]) {
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
            } else {
                break;
            }
        }
    }
    return arr;
}

Анализ: обратите внимание, что в двух циклах здесьiиjЗначение:

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

временная сложность

На первый взгляд кажется, что скорость сортировки вставками не медленная, но нужно знать: когда последовательность просто обратная, каждую вставку нужно менять местами снова и снова, эта скорость такая же, как при пузырьковой сортировке, а время сложность O(n²); Конечно, повезло, фронт упорядочен, тогда временная сложность всего O(n), просто вставьте это напрямую.

Алгоритм сортировки Средняя временная сложность наихудшая временная сложность космическая сложность Это стабильно
Пузырьковая сортировка O(n²) O(n²) O(1) да
сортировка выбором O(n²) O(n²) O(1) нет
сортировка прямой вставкой O(n²) O(n²) O(1) да

Ну как быстро запомнить эту таблицу? Метод написан в началеОсновной алгоритм сортировки. Как упоминалось в начале, основная идея состоит в том, чтобы вложить два слоя циклов, первый раз для нахождения элемента O(n), второй раз для нахождения позиции O(n), поэтому временная сложность этих методов может быть так легко запомнить. !

Расширенные алгоритмы сортировки

Если вся сортировка похожа на базовый метод, описанный выше, это будет катастрофическим для обработки больших объемов данных, брат, просто позвольте вам сортировать, вы используете O (n²). Итак, эти продвинутые алгоритмы сортировки больших данных могут значительно снизить сложность.

быстрая сортировка

Быстрая сортировка можно сказать самый важный алгоритм сортировки для фронтенда.Нет никого.Когда интервьюер спрашивает про алгоритм сортировки,вероятность быстрой сортировки может быть больше 80%(я посчитал вслепую... Верьте или нет).

Так что же такое быстрая сортировка?

Quicksort — один из самых быстрых алгоритмов сортировки для обработки больших данных. Это алгоритм «разделяй и властвуй», который рекурсивно разбивает данные на отдельные подпоследовательности, содержащие по очереди более мелкие и более крупные элементы. Алгоритм продолжает повторять этот шаг, пока все данные не будут в порядке.

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

  1. Выберите элемент данных, чтобы разделить список на две подпоследовательности;
  2. Измените порядок списка, поместив все элементы меньше базового значения перед базовым значением, а все элементы больше базового значения после базового значения;
  3. Повторите шаги 1 и 2 для подпоследовательности меньших элементов и подпоследовательности более крупных элементов соответственно.

function quickSort(arr) {
    if(arr.length <= 1) {
        return arr;  //递归出口
    }
    var left = [],
        right = [],
        current = arr.splice(0,1); //注意splice后，数组长度少了一个
    for(let i = 0; i < arr.length; i++) {
        if(arr[i] < current) {
            left.push(arr[i])  //放在左边
        } else {
            right.push(arr[i]) //放在右边
        }
    }
    return quickSort(left).concat(current,quickSort(right)); //递归
}

Сортировка холмов

Сортировка по Хиллу — это усовершенствованный алгоритм сортировки вставками, но его основная идея отличается от алгоритма вставки: он сравнивает элементы, которые находятся далеко, а не соседние элементы. Текст слишком скучный, давайте посмотрим на анимацию ниже:

Перед реализацией давайте посмотрим, как только что была написана сортировка вставками:

function insertSort(arr) {
    for(let i = 1; i < arr.length - 1; i++) {  //外循环从1开始，默认arr[0]是有序段
        for(let j = i; j > 0; j--) {  //j = i,将arr[j]依次插入有序段中
            if(arr[j] < arr[j-1]) {
                [arr[j],arr[j-1]] = [arr[j-1],arr[j]];
            } else {
                continue;
            }
        }
    }
    return arr;
}

Теперь разница в том, что на основе вышеизложенного пусть размер шага сравним по 3, 2 и 1, что эквивалентно трем слоям циклов и вложенности.

insertSort(arr,[3,2,1]);
function shellSort(arr,gap) {
    console.log(arr)//为了方便观察过程，使用时去除
    for(let i = 0; i<gap.length; i++) {  //最外层循环，一次取不同的步长，步长需要预先给出
        let n = gap[i]; //步长为n
        for(let j = i + n; j < arr.length; j++) { //接下类和插入排序一样，j循环依次取后面的数
            for(let k = j; k > 0; k-=n) { //k循环进行比较，和直接插入的唯一区别是1变为了n
                if(arr[k] < arr[k-n]) {
                    [arr[k],arr[k-n]] = [arr[k-n],arr[k]];
                    console.log(`当前序列为[${arr}] \n 交换了${arr[k]}和${arr[k-n]}`)//为了观察过程
                } else {
                    continue;
                }
            }
        }
    }
    return arr;
}

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

запустить его

var arr = [3, 2, 45, 6, 55, 23, 5, 4, 8, 9, 19, 0];
var gap = [3,2,1];
console.log(shellSort(arr,gap))

Результат выглядит следующим образом:

(12) [3, 2, 45, 6, 55, 23, 5, 4, 8, 9, 19, 0] //初始值
当前序列为[3,2,23,6,55,45,5,4,8,9,19,0] 
 交换了45和23
当前序列为[3,2,23,5,55,45,6,4,8,9,19,0] 
 交换了6和5
当前序列为[3,2,23,5,4,45,6,55,8,9,19,0] 
 交换了55和4
当前序列为[3,2,23,5,4,8,6,55,45,9,19,0] 
 交换了45和8
当前序列为[3,2,8,5,4,23,6,55,45,9,19,0] 
 交换了23和8
当前序列为[3,2,8,5,4,23,6,19,45,9,55,0] 
 交换了55和19
当前序列为[3,2,8,5,4,23,6,19,0,9,55,45] 
 交换了45和0
当前序列为[3,2,8,5,4,0,6,19,23,9,55,45] 
 交换了23和0
当前序列为[3,2,0,5,4,8,6,19,23,9,55,45] 
 交换了8和0
当前序列为[0,2,3,5,4,8,6,19,23,9,55,45] 
 交换了3和0
当前序列为[0,2,3,5,4,8,6,9,23,19,55,45] 
 交换了19和9
当前序列为[0,2,3,4,5,8,6,9,23,19,55,45] 
 交换了5和4
当前序列为[0,2,3,4,5,6,8,9,23,19,55,45] 
 交换了8和6
当前序列为[0,2,3,4,5,6,8,9,19,23,55,45] 
 交换了23和19
当前序列为[0,2,3,4,5,6,8,9,19,23,45,55] 
 交换了55和45

Сводка по временной сложности

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

Алгоритм сортировки Средняя временная сложность наихудшая временная сложность космическая сложность Это стабильно
Пузырьковая сортировка O(n²) O(n²) O(1) да
сортировка выбором O(n²) O(n²) O(1) нет
сортировка прямой вставкой O(n²) O(n²) O(1) да
быстрая сортировка O(nlogn) O(n²) O(logn) нет
Сортировка холмов O(nlogn) O(n^s) O(1) нет
Это стабильно

Если не принимать во внимание стабильность, быстрая сортировка кажется почти идеальным методом, но, к сожалению, он нестабилен. Так что же такое стабильность?

С точки зрения непрофессионалаЕсть два одинаковых числа A и B. До сортировки A находится перед B, а после сортировки B бежит впереди A. В этой ситуации мы называем это нестабильностью сортировки., что может произойти, если быстрая сортировка сортирует одни и те же числа.

/*
比如对(5，3A，6，3B ) 进行排序，排序之前相同的数3A与3B，A在B的前面，经过排序之后会变成  
	（3B，3A，5，6）
所以说快速排序是一个不稳定的排序
/*

Что означает стабильность? Личное понимание Для внешнего интерфейса, например, мы знакомы со сравнением виртуального DOM во фреймворке.<ul>Список визуализируется. Когда данные необходимо сравнить после изменения, нестабильная сортировка или операция изменят то, что не нужно изменять, что приведет к повторному рендерингу и потере производительности.

вспомогательная память
  • память временной сложности
    • Для всплытия, выбора и прямой сортировки требуется два цикла for, каждый из которых фокусируется только на одном элементе, а средняя временная сложность составляет O (n²) (O (n) для элементов один раз и O (n) для позиций один раз).
    • Fast, merge, hill и heap основаны на идее дихотомии, log — по основанию 2, а средняя временная сложность — O(nlogn) (один поиск элементов O(n), один поиск позиций O(logn ))
  • Память стабильности - "куча быстрого выбора" (быстрое жертвование стабильностью)

рекурсия

Рекурсия на самом деле вызывает сама себя.

Много раз мы чувствуем себя беспокойными или чувствуем себя «невообразимыми», главным образом потому, что мы честны с самими собой, потому что это поможет вам выполнить то, что вам нужно, вручную для рекурсии.

Рекурсивные шаги:

  • Ищем выход, рекурсия должна иметь выход, и выход заблокирован, чтобы не было бесконечного цикла
  • Рекурсивное условие, которое соответствует рекурсивному условию, вызывает само себя.

говорить дешево, покажи мне код!

Последовательность Фибоначчи, рекурсия в каждом языке будет начинаться с этого, но так как мы занимаемся фронтендом, то давайте сделаем что-то другое, начиная с глубокого клона объекта (deep clone)

Deep Clone: реализует глубокий клон объекта (объекта)

//所谓深度克隆，就是当对象的某个属性值为object或array的时候，要获得一份copy，而不是直接拿到引用值
function deepClone(origin,target) {  //origin是被克隆对象，target是我们获得copy
    var target = target || {}; //定义target
    for(var key in origin) {  //遍历原对象
        if(origin.hasOwnProperty(key)) {
            if(Array.isArray(origin[key])) { //如果是数组
                target[key] = [];
                deepClone(origin[key],target[key]) //递归
            } else if (typeof origin[key] === 'object' && origin[key] !== null) {
                target[key] = {};
                deepClone(origin[key],target[key]) //递归
            } else {
                target[key] = origin[key];
            }
        }
    }
    return target;
}

Можно сказать, что это часто встречающаяся проблема в письменном тесте/собеседовании по интерфейсу.Идея очень ясна:

  • Выход: возврат после обхода объекта
  • Рекурсивное условие: обнаруженное ссылочное значение Массив или объект

Остальное, просто оставьте JS, чтобы он справился сам, нам не нужно думать о внутренних слоях вложенности, думать слишком много

Практические примеры

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

Q1: Реализация плоского метода массива Array (письменный тест Netease Thunderfire & Fuxi Front-end Autumn Recruitment, 2018 г.)

Плоский метод Array не был реализован многими браузерами. Пожалуйста, напишите плоский метод для выравнивания вложенных массивов, например:

Array
var arr1 = [1, 2, [3, 4]];
arr1.flat(); 
// [1, 2, 3, 4]

Идея реализации этой задачи очень похожа на Deep Clone, которая реализована следующим образом:

Array.prototype.flat = function() {
    var arr = [];
    this.forEach((item,idx) => {
        if(Array.isArray(item)) {
            arr = arr.concat(item.flat()); //递归去处理数组元素
        } else {
            arr.push(item)   //非数组直接push进去
        }
    })
    return arr;   //递归出口
}

Хорошо, давайте проверим это:

arr = [[2],[[2,3],[2]],3,4]
arr.flat()
// [2, 2, 3, 2, 3, 4]

Новое решение таинственной силы

Друг в области комментариев предложил лучший способ, который очень прост и удобен и может удовлетворить ваши потребности всего одним предложением (но вы не думаете, что это немного смущает, чтобы ответить на «вопрос о программировании» NetEase, подобный этому Ну ~ хаха)

arr.prototype.flat = function() {
    this.toString().split(',').map(item=> +item )
}

Ну а после чуда поговорим о реализации:

  1. метод toString, объединяет массивы и возвращает строку'2,2,3,2,3,4'
  2. Метод split разбивает строку на массив['2','2','3','2','3','4']
  3. метод карты, который сопоставляет строку с числовым типом2,2,3,2,3,4

Q2 Реализуйте упрощенную версию co и автоматически запустите генератор

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

Например, реализовать следующие функции:

const co = require('co');
co(function *() {
    const url = 'http://jasonplacerholder.typecoder.com/posts/1';
    const response = yield fetch(url);
    const post = yield response.json();
    const title = post.title;
    console.log('Title: ',title);
})

Анатомия:

  • Первый шаг — найти выход, итератор, возвращаемый исполнителем, если состояниеdone, представляет собой конец, вы можете выйти
  • Рекурсивное условие: получить следующий итератор, рекурсивно, вызвать себя
function run(generat) {
    const iterator = generat();
    function autoRun(iteration) {
        if(iteration.done) {return iteration.value}  //出口
        const anotherPromise = iteration.value;
        anoterPromise.then(x => {
            return autoRun(iterator.next(x))  //递归条件
        })
    }
    return autoRun(iterator.next()) 
}

Q3. Подъем по лестнице

Существует лестница с общим количеством уровней M. В начале вы находитесь на первом уровне. Если вы можете подняться только на один или два уровня за раз, сколько существует способов подняться на M-й уровень?

анализировать: Эту задачу нужно рассматривать в обратном порядке, чтобы добраться до n ступеней, есть только два пути: с (n-1) уровня или (n-2) уровня. Таким образом, вы можете использовать идею рекурсии, чтобы подумать об этой проблеме.Предположим, что есть массив s[n], тогда s[1] = 1 (так как он находится на первом уровне в начале, есть только один метод ), s[2] = 1 (Только из s[1] другого пути нет).

Тогда мы можем вывести s[3] ~ s[n].

Продолжите симуляцию ниже, s[3] = s[1] + s[2], потому что только два шага можно сделать с первого уровня или один шаг можно сделать со второго уровня.

function cStairs(n) {
    if(n === 1 || n === 2) {
        return 1;
    } else {
        return cStairs(n-1) + cStairs(n-2)
    }
}

Хм, верно, на самом деле последовательность Фибоначчи не сработала.

Q4. Бинарный поиск

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

A: 0 ~ 100 猜一个数字
B: 50
A: 大了
B: 25
A: 对头，就是25

Таким образом, идея очень ясна. Есть два способа записи рекурсии и нерекурсии. Давайте сначала поговорим о рекурсивном методе:

  • Установите интервал, низкий и высокий
  • Найти выход: найти цель, вернуть цель;
  • В противном случае поиск, текущий порядок не найден, уменьшите интервал, а затем рекурсивно
function binaryFind(arr,target,low = 0,high = arr.length - 1) {
    const n = Math.floor((low+high) /2);
    const cur = arr[n];
    if(cur === target) {
        return `找到了${target},在第${n+1}个`;
    } else if(cur > target) {
        return binaryFind(arr,target,low, n-1);
    } else if (cur < target) {
        return binaryFind(arr,target,n+1,high);
    }
    return -1;
}

Затем используйте цикл для бинарного поиска.На самом деле идея в основном та же:

function binaryFind(arr, target) {
    var low = 0,
        high = arr.length - 1,
        mid;
    while (low <= high) {
        mid = Math.floor((low + high) / 2);
        if (target === arr[mid]) {
            return `找到了${target},在第${mid + 1}个`
        }
        if (target > arr[mid]) {
            low = mid + 1;
        } else if (target < arr[mid]) {
            high = mid - 1;
        }
    }
    return -1
}

Бинарные деревья и бинарные деревья поиска

Основные понятия деревьев

Основные понятия здесь подробно рассматриваться не будут, более подробные введения есть в основных материалах, здесь мы лишь кратко познакомим с основными понятиями и терминами, а затем с помощью JavaScript реализуем бинарное дерево и инкапсулируем его методы.

Как показано на рисунке, верхняя точка дерева называется корневым узлом. Если узел соединен с несколькими узлами, узел становится родительским узлом, а узлы под ним называются дочерними узлами. Узел может иметь 0, 1 или более узлов, узлы без дочерних узлов называются листовыми узлами.

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

бинарное дерево поиска

Бинарное дерево поиска представляет собой особый вид бинарного дерева.Относительно небольшие значения хранятся в левом узле, а большие значения хранятся в правом узле.Эта особенность делает поиск очень эффективным.Для числовых и нечисловых данные, такие как буквы и строки. Теперь реализуем бинарное дерево поиска через JS.

узел

Наименьший элемент бинарного дерева — это узел, поэтому сначала определите узел

function Node(data,left,right) {
    this.left = left;
    this.right = right;
    this.data = data;
    this.show = () => {return this.data}
}

Это наименьшая структурная единица бинарного дерева.

бинарное дерево

function BST() {
    this.root = null //初始化,root为null
}

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

  1. еслиBST.root === null, затем возьмите узел в качестве корневого узла
  2. еслиBST.root !==null, сравнить вставленный узел, если он меньше корневого узла, получить узел слева, иначе взять правый, снова сравнить, рекурсивно.

Здесь в дело вступает рекурсия, потому что всегда помещайте меньшую ветку на левую ветвь. Другими словами

Самый левый листовой узел — это наименьшее число, а самый правый листовой узел — это наибольшее число.

function insert(data) {
    var node = new Node(data,null,null);
    if(this.root === null) {
        this.root = node
    } else {
        var current = this.root;
        var parent;
        while(true) {
            parent = current;
            if(data < current.data) {
                current = current.left; //到左子树
                if(current === null) {  //如果左子树为空，说明可以将node插入在这里
                    parent.left = node;
                    break;  //跳出while循环
                }
            } else {
                current = current.right;
                if(current === null) {
                    parent.right = node;
                    break;
                }
            }
        }
    }
}

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

Затем запишите этот метод в BST:

function BST() {
    this.root = null;
    this.insert = insert;
}

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

var bst = new BST()；
bst.insert(10);
bst.insert(8);
bst.insert(2);
bst.insert(7);
bst.insert(5);

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

обход бинарного дерева

Мы знаем, что обход дерева в основном включает в себя

  • Предварительный обход (корень слева и справа)
  • Неупорядоченный обход (левый корень справа)
  • Постпорядковый обход (левый и правый корни)

Это просто для хорошей памяти, давайте сделаем обход со следующим графиком

Обход предварительного заказа: 56 22 10 30 81 77 92

Порядок обхода: 10 22 30 56 77 81 92

Обход после заказа: 10 30 22 77 92 81 56

Вот несколько найденных закономерностей:

  1. Предварительный обход, поскольку речь идет о корне, последний должен быть самым большим, первый должен быть корневым узлом;
  2. Для обхода по бинарному дереву поиска он должен идти от меньшего к большему; корневой узел56Левое (10/22/30) должно быть левым поддеревом, а правое (77/81/92) должно быть правым поддеревом.
  3. Обход после заказа, корневой узел должен быть в конце
Реализация обхода по порядку

Здесь снова используется предыдущая рекурсия, и требования обхода по порядку таковы:Левый! корень! правильно

function inOrder(node) {
    if(node !== null) {
        //如果不是null，就一直查找左变，因此递归
        inOrder(node.left);
        //递归结束，打印当前值
        console.log(node.show());
        //上一次递归已经把左边搞完了，右边
        inOrder(node.right);
    }
}

//在刚才已有bst的基础上执行命令
inOrder(bst.root);

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

2
5
7
8
10
Обход предварительного заказа и обход после заказа

Если только что рекурсивный процесс ясен, то это не может быть проще

function preOrder(node) {
    if(node !== null) {
        //根左右
        console.log(node.show());
        preOrder(node.left);
        preOrder(node.right);
    }
}

хорошо, куй железо, пока горячо, и напиши метод обхода пост-порядка вместе, следующим образом:

function postOrder(node) {
    if(node !== null) {
        //左右根
        postOrder(node.left);
        postOrder(node.right);
        console.log(node.show())
    }
}

Что ж, вы можете попробовать результаты, напечатанные двумя способами:

preOrder(bst.root);
postOrder(bst.root);

поиск по бинарному дереву

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

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

Как только у вас появится четкая идея, начните писать:

//最小值
function getMin(bst) {
    var current = bst.root;
    while(current.left !== null) {
        current = current.left;
    }
    return current.data;
}

//最大值
function getMax(bst) {
    var current = bst.root;
    while(current.right !== null) {
        current = current.right;
    }
    return current.data;
}

Максимальные и минимальные значения очень просты Давайте посмотрим, как пройти

function find(target,bst) {
    var current = bst.root;
    while(current !== null) {
        if(target === current.data) {
            return true;
        }
        else if(target > current.data) {
            current = current.right;
        } else if(target < current.data) {
            current = current.left;
        }
    }
    return -1;
}

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

Ух ты...

Я не ожидал, что сегодня так долго разбираться... гм... но эта статья уже достаточно длинная

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

  • регулярное выражение
    • Методы, связанные со строками
    • str.split()
    • str.replace()
    • str.match()
    • reg.test()
    • reg.exec()
  • метод массива
    • Отображение Array.map(), имеет возвращаемое значение, не изменяет сам массив
    • Обход Array.forEach(), без возвращаемого значения
    • Array.filter() фильтрует, возвращает true при возврате и не возвращает при false
    • Array.splice/slice/join и т. д.
    • для... обхода, очки знаний, связанные с итератором

Продолжение следует....

Контент будет продолжать обновляться, быстрее всего конечно на гитхабе, а потом он будет синхронизироваться с наггетсами,гитхаб-портал

использованная литература

  1. Сравнение временной сложности, пространственной сложности и устойчивости алгоритмов сортировки
  2. Запись обучения алгоритма — сортировка по Хиллу
  3. Быстрая сортировка проста для понимания
  4. Структуры данных и алгоритмы Javascript Описание
Категории