(https://www.udemy.com/course/js-algorithms-and-data-structures-masterclass/)
Типичная задача - найти анаграмы. Вместо использования цикла в цикле, заводим переменную obj, проходим циклом первое слово/массив, каждый элемент/буква - ключ в obj. Если такой ключ есть, увеличиваем значение на 1. Затем проходимся вторым циклом по второму слову/массиву - проверяем в obj наличие ключа (obj[arr2[i]]). Если его нет - возвращаем false, иначе отнимаем единицу.
###Multiple pointers
Типичная задача - найти пару элементу массива/букве в строке (например, найти первую пару значений массива, сумма которых = 0). Главное условие - массив должен быть отсортирован! Заводим 2 переменные - let left = 0 и let right = arr.length-1. Заводим цикл, в котором проверяем, чему равно сумма этих переменных. Если она больше искомого, сдвигаем right на 1 влево (массив отсортирован => следующее значение будет меньше). Если значение меньше искомого, сдвигаем left на один вправо. И так до тех пор, пока left меньше right. Если значение суммы совпало с искомым, возвращаем пару, если нет - возвращаем null. Основная идея - не заводить второй цикл, а двигаться по массиву, начиная от разных элементов, одновременно.
Типичная задача - найти подмассив заданной длины, сумма элементов которого будет максимальной в данном массиве. Основная идея - не заводить второй цикл и пересчитывать всю сумму заново, а двигаться "окном" - найти сумму заданного количества элементов, двигаться вправо, вычитая первый элемент и приплюсовывая следующий.
Типичная задача - найти индекс нужного значения в отсортированном массиве. Вместо того, чтобы идти по массиву от начала до конца, заводим 3 переменные - let start = 0, let end = arr.length-1 и let middle, которая равна количеству элементов, поделенное на 2, предполагая, что это и есть индекс искомого элемента. Если arr[middle] больше искомого, устанавливаем end = middle-1 (так как значение middle уже проверили), если меньше, то start = middle+1. Повторяем до тех пор, пока start < end.
Заводим 2 цикла. Сравниваем попарно элементы массива во втором цикле - 0 и 1, затем 1 и 2, затем 2 и 3, и т.д. Тот элемент, который больше, получает больший индекс. Дошли до конца -> запускаем следующую итерацию первого цикла и так до конца. Оптимизация - если за весь проход не было перестановок, выходим из цикла. Для этого заводим переменную boolean, которая по умолчанию = true. Если перестановка была, изменяем ее на false. Каждую итерацию первого цикла проверяем условие if ( boolean ) { break }
Заводим цикл, объявляем переменную min, равную i, которая по умолчанию считается индексом минимального значения массива. Заводим второй цикл, в котором проверяем, меньше ли следующий элемент, чем arr[min]. Если да, то значение min становится равно j. Таким образом находится наименьший элемент массива. На выходе из второго цикла проверяется, изменилось ли значение переменной min. Если да, то элементы arr[i] и arr[min] меняются местами.
Объявляем переменную currentValue. Заводим цикл (начиная с первого элемента (не нулевого!)), в котором присваиваем currentValue значение arr[i]. Исходим из того, что левая часть массива (до i) - уже отсортирована. Заводим второй цикл, в котором счетчик массива начинается со значения i-1. При этом должно выполняться условие, что текущее значение меньше currentValue (так как массив в левой части отсортирован, и если текущее значение больше, значит условие сортировки и так соблюдено и перемещать элемент никуда не нужно). Если currentValue меньше последнего в левой части - выполняем arr[j+1] = arr[j] - таким образом 'сдвигаем' отсортированный массив на 1 индекс для вставки в него currentValue - и идем дальше по второму циклу. Когда условие не выполнится, то в значении j у нас будет сохранен индекс элемента, значение которого меньше currentValue => выполняем arr[j+1]=currentValue - вставляем нужный элемент после него. После этого левая часть массива снова отсортирована, двигаемся по первому циклу дальше.
Делим массив на более мелкие до тех пор, пока в массиве не останется по 1 элементу (рекурсивно - ищем середину, вызываем себя же сначала для левой, потом для правой части. Выход из рекурсии - если длина массива === 1). Массив из 1 элемента всегда отсортирован. Возвращаем функцию мёржа для левой и правой части массива - мелкие массивы объединяются в более крупные. В этой функции заводим две переменные i и j = 0. Идем параллельно по двум массивам while, выход из цикла - когда i === arr1.length или j === arr2.length. Берем меньший по значению элемент (arr1[i] | arr2[j]) и пушим его в новый массив. Счетчик того массива, значение из которого было записано, увеличивается. При выходе из цикла, проверяем, не осталось ли в каком-то массиве еще значения, допушиваем их в возвращаемый массив.
Вспомогательная функция - вычисление pivot. Выбираем рандомный элемент (допустим, первый) - pivot. Запоминаем его индекс - pivotIndex. Идем по массиву и делим его на правую и левую части: в левой части элементы, которые меньше данного, в правой - которые больше. То есть смотрим, если элемент массива меньше чем наш pivot, это значит, что наш pivot должен быть справа от него, поэтому запоминаем, что текущий элемент нужно переместить на место pivotIndex + 1, сам же pivotIndex инкрементим. Доходим до конца массива и перемещаем наш pivot на получившееся место pivotIndex. При этом необходимо добавить доп аргументы: от какого и до какого элемента делать проверку. Для сортировки массива так же добавляем ещё 2 аргумента - left & right, для того, чтобы мы могли управлять тем, над какой частью массива мы работаем. Запускаем рекурсию - находим pivot, массив уже изменен, поэтому этот элемент стоит на нужном месте. Вызываем quickSort() для левой части массива (до pivot, не включая его), затем для правой части (тоже не включая pivot). Условие выхода из рекурсии - если left !< right. За скобками условия возвращаем массив.
Подходит только для чисел. Идея в том, что мы не сравниваем их друг с другом, а распределяем по кучкам. Сначала по единицам (все, которые заканчиваются на 1 - в одну кучку, на 2 - в другую и тд). Потом фигачим их в один массив в том порядке, в котором они в кучках, делим по десяткам. Если разряда нет - то в кучку с нулём. И так, пока все числа не окажутся в кучке с нулем. Первая вспомогательная функция - выдача нужного значения разряда. Есть два стула: один со строками (приводим к строке, инвертируем, берем str[ind]), второй - c числами (возвращаем остаток от деления на 10 в нужной степени). Вторая - выдать количество разрядов в числе. Можно так же через приведение к строке (просто вернуть ее длину), можно математически: вернуть то, в какой степени 10 дает это число +1. Третья вспомогательная функция - найти самое большое число (по количеству разрядов в нем): в цикле по данному массиву запускается предыдущая функция. Сама сортировка выглядит следующим образом: вычисляется, сколько проходов по циклу будет (через поиск самого длинного числа), запускается цикл, в котором объявляется массив массивов ("кучки" по разрядам), вычисляется значение разряда (сам разряд = counter цикла) и число определяется в нужную кучку. Затем кучки мержатся в один массив, это значение присваивается в исходный массив (чтобы при следующей итерации мы ходили по уже частично отсортированному массиву, иначе зачем это все).
Однонаправленный(?) список - каждая нода содержит в себе value и ссылку на следующую ноду (не предыдущую!). Сам список имеет начало (head) и конец (tail) - в которые записываются ссылки на ноды. Методы: push (создаем новую ноду, сохраняем ее в ссылку к tail.next, переназначаем tail), pop (итерируемся по списку, стираем ссылку на next у предпоследней ноды, переназначаем tail, возвращаем стираемую ноду), shift (возвращаем head, head.next делаем новым head), unshift (создаем новую ноду, в node.next пихаем ссылку на this.head, определяем новый head), get (заводим counter = 0, говорим, что искомый элемент = this.head и в цикле итерируемся, пока counter < искомого индекса), set (находим через get заменяемую ноду И ПРОСТО МЕНЯЕМ NODE.VAL, БЛЕАТЬ), insert (если индекс = 0 - просто делаем unshift, если = SLL.length - делаем push, в остальных случаях находим предыдущую ноду, создаем новую, prev.next пихаем в node.next, в prev.next сохраняем новую, инкрементим this.length), remove (edge cases: если ind = SLL.length, то используем this.pop, если = 0 - this.shift, в остальных случаях находим ноду предыдущую индексу, ее .next запоминаем в переменную, переопределяем на .next.next и возвращаем), reverse (сохраняем head в переменную, меняем местами head и tail, заводим переменную prev, в которую пока кладем null и next, куда ничего не кладем; заводим цикл: в next кладем node.next, в node.next кладем prev, сдвигаемся: prev = node, node = next)
Двунаправленный список - содержит value, next & prev (поэтому по памяти жрет больше). Пример - history браузера. Методы: push (tail.next = new node, node.prev = tail и tail = node), pop (тоже переназначаем ссылки, идем с конца), shift (the same), unshift (создаем новую ноду, обновляем ссылки и не забываем инкрементить длину), get (то же самое, что и в SLL, но с оптимизацией: если ind > this.length / 2, идти с конца по node.prev и декрементить counter), set (get ноду по нужному индексу и изменяем ее value), insert (ind = 0 - this.unshift, ind = DLL.length - this.push, в остальных случаях get предыдущую искомой ноду, меняем ссылку, инкрементим длину, возвращаем true), remove (ind = 0 - this.shift, ind = DLL.length-1 - this.pop, в остальных случаях так же через get и меняем ссылки, возвращаем ноду (не забыть потереть ссылки у неё самой!))
Last In First Out. Пример - callStack в рекурсивных функциях. Можно сделать через массивы (используя push и pop), можно через SLL (используя методы unshift (который для Stack будет push) и shift (который для Stack будет pop)). Главный принцип - работаем всегда с this.head, чтобы сохранить быстрый доступ.
First In First Out. Пример - background tasks. Можно так же через массивы (используя push и shift), можно через SLL (используя методы push (который для Queue будет enqueue) и shift (который для Queue будет enqueue)). При добавлении работаем с this.tail, при взятии - с this.head, ч
Если очередь и стэк - линейные структуры, то деревья - нелинейные. У деревьев всегда один root и не разрешаются никакие связи кроме как от родителя к ребенку. Leaf - нода без детей, edge - связь между нодами, siblings - ноды с одним родителем.
Дерево, в котором каждая нода может иметь максимум 2 ребенка
Бинарное дерево, в котором все ноды слева всегда меньше родителя, а все ноды справа - всегда больше родителя. Удобно использовать для поиска - потому что данные в дереве всегда отсортированы.
Для вставки создаем новую ноду (вместо prev и next - left и right). Если !root, записываем в нее новую ноду, если нет - заводим temp = root и сравниваем, если value > temp.value && temp.value.right, то перезаписываем temp = temp.right, если value < temp.value && temp.value.leftто перезаписываем temp = temp.left и проверяем дальше (рекурсивно или циклом). Когда выполнится первое условие и не выполнится второе - записываем новую ноду. Если value === temp.value, можно проигнорировать, а можно увеличить счетчик нод.
Абсолютно все то же самое, только возвращается нода.
Обходить можно несколькими путями: Breadth First Search (вширь) - заводим массив и очередь, в очередь сразу добавляем root. Далее в цикле while достаем из очереди ноду, ее value пушим в итоговый массив. Проверяем, если у ноды есть дети, то пушим их в очередь. Повторяем до тех пор, пока в очереди что-то есть.
Depth First Search (вглубь) - тоже несколькими путями. Preorder - идем от корня вниз. Заводим массив с результатами и вспомогательную функцию, в которой пушим value пришедшей ноды. Если есть left - вызываем себя же на node.left. То же самое справа. Возвращаем массив. Post - все абсолютно то же самое, но во вспомогательной функции пушим после того, как обошли всех детей. In - тоже самое , только пушим после того, как обошли только левых детей (при этом в результате получится полностью отсортированный массив).
Breadth First Search хорошо использовать для узких деревьев (по памяти жирно), Depth First Search - для широких.