30 алгоритмических задач по JavaScript

Бинарный поиск (Binary Search) - это эффективный алгоритм для поиска значения в отсортированном массиве. Принцип алгоритма очень прост. Мы всегда имеем дело с упорядоченным массивом. Это позволяет прибегать к хитрости - на каждой итерации цикла, который мы запускаем, мы вычисляем индекс среднего элемента. Этот элемент сравниваем с искомым. Если элемент из середины массива оказался меньше, чем тот, что мы ищем, значит нужный нам находится правее по массиву, ведь массив упорядочен. Соответственно, нам нужно перейти в следующую итерацию цикла, "оставляя" ей лишь правую часть массива - в ней снова будет найден средний элемент и алгоритм повторится. Если же элемент из середины массива оказался больше искомого, то мы переходим к следующей итерации, отбрасывая правую часть массива, а оставляя левую. Если же элемент совпадает с искомым, мы выходим из цикла. function binarySearch(array, target) { let left = 0; let right = array.length - 1; while (left <= right) { let mid = Math.floor((left + right) / 2); let currentElement = array[mid]; if (currentElement === target) { return mid; } else if (target < currentElement) { right = mid - 1; } else { left = mid + 1; } } return -1; } 1. left и right – это границы массива, которые мы просматриваем в данный момент. 2. mid – это индекс элемента в середине массива, мы используем его для определения, в какую сторону двигаться дальше. 3. currentElement – это элемент в массиве, который сейчас проверяется. 4. if (currentElement === target) – если текущий элемент равен искомому значению, то возвращаем его индекс. 5. else if (target < currentElement) – если искомое значение меньше текущего элемента, то мы перемещаем правую границу влево, так как искомое значение должно находиться слева от текущего элемента. 6. else – в противном случае, если искомое значение больше текущего элемента, мы перемещаем левую границу вправо, так как искомое значение должно находиться справа от текущего элемента. 7. while (left <= right) – цикл повторяется, пока левая граница меньше или равна правой. 8. return -1 – если мы вышли из цикла и не нашли искомое значение, то возвращаем -1, что означает, что элемент не найден. Вот пример использования функции бинарного поиска: const array = [1, 2, 3, 4, 5, 6, 7, 8, 9]; const target = 5; const index = binarySearch(array, target); console.log(index); // Output: 4 1. Создаем массив array с данными, в котором будем искать элемент. 2. Задаем значение target, которое мы хотим найти. 3. Вызываем функцию binarySearch с передачей массива и искомого значения. 4. Результат вызова функции присваиваем переменной index. 5. Выводим index в консоль. Результатом будет индекс 4, так как элемент со значением 5 находится под индексом 4 в массиве. В заключение, бинарный поиск является одним из эффективных алгоритмов поиска, особенно когда используется с отсортированными данными. Также существуют другие похожие алгоритмы, такие как линейный поиск и интерполяционный поиск. Среди всех этих алгоритмов бинарный поиск является самым эффективным и используется, когда необходимо быстро найти конкретный элемент в большом массиве данных. В то время как линейный поиск является более простым и понятным, но медленным при больших объемах данных. Интерполяционный поиск используется, когда есть информация о возможной позиции элемента в массиве, но является менее стабильным по сравнению с бинарным поиском.

Постановка: Палиндром — слово, предложение или последовательность символов, которая абсолютно одинаково читается как в привычном направлении, так и в обратном. К примеру, “Anna” — это палиндром, а “table” и “John” — нет. Дана строка; нужно написать функцию, которая позволяет вернуть значение true, если строка является палиндромом, и false — если нет. При этом нужно учитывать пробелы и знаки препинания. palindrome('racecar') // true palindrome('table') // false Разбираем задание Основная идея здесь — перевернуть строку в обратном направлении. Если «реверсная» строка полностью идентична исходной, значит, мы получили палиндром и функция должна вернуть значение true. Если же нет — false. Решение: Вот код, который позволяет решить задачу: const palindrome = str => { str = str.toLowerCase() return str === str.split('').reverse().join('') } Первый шаг — преобразование символов исходной строки в нижний регистр. Это гарантия того, что программа будет сравнивать символы без учета регистра. Второй шаг — реверс строки. Это сделать несложно: необходимо преобразовать ее в массив посредством метода .split(). Потом мы переворачиваем массив, используя .reverse(). Последний этап — преобразование обратного массива в строку при помощи .join(). Теперь все, что нужно, — сравнить «обратную» строку с исходной, вернув результат true или false.

Постановка: Так называют слово, которое содержит все буквы другого слова в том же количестве, но ином порядке. Нужно написать функцию, которая проверяет, являются ли две строки анаграммами, причем регистр букв не имеет значения. Учитываются лишь символы; пробелы или знаки препинания в расчет не берутся. anagram('finder', 'Friend') --> true anagram('hello', 'bye') --> false Разбираем задание Здесь важно учитывать, что необходимо проверять каждую букву в обеих строках и количество ее вхождений в каждую из них. finder --> f: 1 friend --> f: 1 i: 1 r: 1 n: 1 i: 1 d: 1 e: 1 e: 1 n: 1 r: 1 d: 1 Для хранения данных анаграммы стоит выбрать такую структуру, как объект. Ключ в этом случае — символ буквы, значение — количество ее повторений в текущей строке. Есть и другие условия: Нужно убедиться в том, что регистр букв при сравнении не учитывается. Просто преобразуем обе строки в нижний или верхний регистр. Исключаем из сравнения все не-символы. Лучше всего работать с регулярными выражениями. Решение: // Вспомогательная функция для создания объекта // хранящего пары вида <символ>:<кол-во повторений> const buildCharObject = (str) => { const charObj = {} for (let char of str.replace(/[^\w]/g).toLowerCase()) { // Поисходит первичная запись свойства в объект, // либо инкрементирование, если оно уже имеется charObj[char] = charObj[char] + 1 || 1 } return charObj } // Основная функция const anagram = (strA, strB) => { const aCharObject = buildCharObject(strA) const bCharObject = buildCharObject(strB) // Если в объектах разное кол-во символов, это не анаграмма if(Object.keys(aCharObject).length !== Object.keys(bCharObject).length) { return false } // Так же возвращаем false, если кол-во вхождений // не совпадает для какого-либо символа for(let char in aCharObject) { if(aCharObject[char] !== bCharObject[char]) { return false } } return true } Обратите внимание на использование Object.keys() в сниппете выше. Этот метод возвращает массив, содержащий имена или ключи в таком же порядке, в каком они встречаются в объекте. В этом случае массив будет таким: ['f', 'i', 'n', 'd', 'e', 'r'] Таким образом, мы получаем свойства объекта без необходимости выполнять объемный цикл. В задаче можно использовать этот способ со свойством .length — для проверки того, есть ли в обеих строках одинаковое количество символов — это важная особенность анаграмм.

Метод двух указателей - это популярный шаблон решения задач, используемый в JavaScript и других языках программирования, особенно полезный при работе с массивами и строками. Основная идея Основная идея метода двух указателей заключается в использовании двух указателей, которые движутся по массиву или строке в разных направлениях или со скоростями. Этот метод часто используется для решения задач оптимизации, так как он может сократить необходимость вложенных циклов и уменьшить сложность алгоритма. Пример использования Возьмем для примера задачу поиска пары чисел в отсортированном массиве, которые в сумме дают заданное число. Можно использовать метод двух указателей для решения этой задачи. function findPair(arr, target) { let left = 0; let right = arr.length - 1; while (left < right) { let sum = arr[left] + arr[right]; if (sum == target) { return [left, right]; } else if (sum < target) { left++; } else { right--; } } return [-1, -1]; // возвращаем, если пара не найдена } В этом примере мы инициализируем два указателя, один указывает на начало массива, а другой на конец. Затем мы двигаем указатели в зависимости от суммы текущих элементов. Если сумма равна целевому числу, мы нашли пару. Если сумма меньше целевого числа, мы двигаем левый указатель вправо. Если сумма больше целевого числа, мы двигаем правый указатель влево. Заключение Метод двух указателей - это мощный инструмент, который может значительно улучшить производительность вашего кода при правильном использовании. Он особенно полезен при работе с массивами и строками, и может быть использован для решения широкого спектра задач.

Постановка: Напишите функцию для нахождения длины самой длинной подстроки без повторяющихся символов в строке. Решение: Использование двух указателей для отслеживания подстроки: function longestSubstringWithoutRepeating(s) { let leftPointer = 0; // Левый указатель начала подстроки let maxLength = 0; // Максимальная длина подстроки const charIndexMap = {}; // Хранит индексы символов в текущей подстроке for (let rightPointer = 0; rightPointer < s.length; rightPointer++) { const currentChar = s[rightPointer]; // Если символ уже встречался в текущей подстроке, обновляем левый указатель if (charIndexMap[currentChar] !== undefined && charIndexMap[currentChar] >= leftPointer) { leftPointer = charIndexMap[currentChar] + 1; } // Обновляем индекс символа в текущей подстроке charIndexMap[currentChar] = rightPointer; // Обновляем максимальную длину подстроки maxLength = Math.max(maxLength, rightPointer - leftPointer + 1); } return maxLength; } // Пример использования: const strExample = 'abcabcbb'; console.log(longestSubstringWithoutRepeating(strExample)); // Вернет 3. 1. Правый указатель rightPointer движется вперед, проверяя каждый символ. 2. Если символ уже встречался в текущей подстроке, обновляем leftPointer до индекса следующего символа после повторения. 3. Обновляем индекс символа в charIndexMap. 4. Обновляем maxLength с учетом текущей длины подстроки. В конце прохода возвращаем максимальную длину подстроки без повторений. Объяснение подхода с двумя указателями: 1. Использование двух указателей (leftPointer и rightPointer) позволяет эффективно отслеживать текущую подстроку без повторений. 2. Обновление leftPointer после повторения символа гарантирует, что мы рассматриваем только уникальные символы. Проход по строке выполняется за линейное время O(n), где n - длина строки. Этот алгоритм эффективно решает задачу нахождения длины самой длинной подстроки без повторяющихся символов и является одним из классических примеров использования двух указателей.

Каррирование – продвинутая техника для работы с функциями. Она используется не только в JavaScript, но и в других языках. Каррирование – это трансформация функций таким образом, чтобы они принимали аргументы не как f(a, b, c), а как f(a)(b)(c). function curry(f) { // curry(f) выполняет каррирование return function(a) { return function(b) { return f(a, b); }; }; } Использование: function sum(a, b) { return a + b; } let curriedSum = curry(sum); alert( curriedSum(1)(2) ); // 3 Более продвинутые реализации каррирования, как например _.curry из библиотеки lodash, возвращают обёртку, которая позволяет запустить функцию как обычным образом, так и частично. function sum(a, b) { return a + b; } let curriedSum = _.curry(sum); // используем _.curry из lodash alert( curriedSum(1, 2) ); // 3, можно вызывать как обычно alert( curriedSum(1)(2) ); // 3, а можно частично Чтобы понять пользу от каррирования, нам определённо нужен пример из реальной жизни. Например, у нас есть функция логирования log(date, importance, message), которая форматирует и выводит информацию. В реальных проектах у таких функций есть много полезных возможностей, например, посылать логи по сети, здесь для простоты используем alert: function log(date, importance, message) { alert(`[${date.getHours()}:${date.getMinutes()}] [${importance}] ${message}`); } А теперь давайте применим к ней каррирование! log = _.curry(log); После этого log продолжает работать нормально: log(new Date(), "DEBUG", "some debug"); // log(a, b, c) Но также работает вариант с каррированием: log(new Date())("DEBUG")("some debug"); // log(a)(b)(c) Давайте сделаем удобную функцию для логов с текущим временем: // logNow будет частичным применением функции log с фиксированным первым аргументом let logNow = log(new Date()); // используем её logNow("INFO", "message"); // [HH:mm] INFO message Теперь logNow – это log с фиксированным первым аргументом, иначе говоря, «частично применённая» или «частичная» функция. Мы можем пойти дальше и сделать удобную функцию для именно отладочных логов с текущим временем: let debugNow = logNow("DEBUG"); debugNow("message"); // [HH:mm] DEBUG message Итак: Мы ничего не потеряли после каррирования: log всё так же можно вызывать нормально. Мы можем легко создавать частично применённые функции, как сделали для логов с текущим временем. В случае, если вам интересны детали, вот «продвинутая» реализация каррирования для функций с множеством аргументов, которую мы могли бы использовать выше. Она очень короткая: function curry(func) { return function curried(...args) { if (args.length >= func.length) { return func.apply(this, args); } else { return function(...args2) { return curried.apply(this, args.concat(args2)); } } }; } Примеры использования: function sum(a, b, c) { return a + b + c; } let curriedSum = curry(sum); alert( curriedSum(1, 2, 3) ); // 6, всё ещё можно вызывать нормально alert( curriedSum(1)(2,3) ); // 6, каррирование первого аргумента alert( curriedSum(1)(2)(3) ); // 6, каррирование всех аргументов