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

Постановка: Палиндром — слово, предложение или последовательность символов, которая абсолютно одинаково читается как в привычном направлении, так и в обратном. К примеру, “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.

Постановка: Так называют слово, которое содержит все буквы другого слова в том же количестве, но ином порядке. Нужно написать функцию isAnagram(a, b), которая проверяет, являются ли две строки анаграммами, причем регистр букв не имеет значения. Учитываются лишь символы; пробелы или знаки препинания в расчет не берутся. isAnagram('finder', 'Friend') // true isAnagram('hello', 'bye') // false Решение: function isAnagram(a, b) { if (a.length != b.length) return false; return a.toLowerCase().split('').sort().join() === b.toLowerCase().split('').sort().join() }

Метод двух указателей - это популярный шаблон решения задач, используемый в 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, каррирование всех аргументов

Бинарный поиск (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 в массиве. В заключение, бинарный поиск является одним из эффективных алгоритмов поиска, особенно когда используется с отсортированными данными. Также существуют другие похожие алгоритмы, такие как линейный поиск и интерполяционный поиск. Среди всех этих алгоритмов бинарный поиск является самым эффективным и используется, когда необходимо быстро найти конкретный элемент в большом массиве данных. В то время как линейный поиск является более простым и понятным, но медленным при больших объемах данных. Интерполяционный поиск используется, когда есть информация о возможной позиции элемента в массиве, но является менее стабильным по сравнению с бинарным поиском.

Дана структура данных в виде дерева: const tree = { value: 1, children: [ { value: 2, children: [ { value: 4 }, { value: 5 }, ] }, { value: 3, children: [ { value: 6 }, { value: 7 }, ] } ] }; Необходимо написать функцию, возвращающую значения всех вершин дерева: getTreeValues(tree); // => [1, 2, 3, 4, 5, 6, 7] Через рекурсию: function getTreeValues(tree) { let values = [tree.value]; if (Array.isArray(tree.children)) { tree.children.forEach(item => values = values.concat(getTreeValues(item))); } return values; } Через цикл: function getTreeValues(tree) { const tmpTree = [tree]; const res = []; let current; while (tmpTree.length > 0) { current = tmpTree.shift(); res.push(current.value); if (current.children) { current.children.forEach(item => tmpTree.push(item)); } } return res } Бинарные деревья поиска и рекурсия – это просто Обход дерева - это просто

Постановка: Необходимо реализовать функцию rle(str), принимающую в аргументах строку, состоящую из букв и возвращающую новую строку, в которой повторяющиеся буквы заменены количеством повторений. Функция должна быть чувствительна к регистру символов. Символ, повторяющийся один раз, в итоговой строке должен быть без цифры. Например: rle('AVVVBBBVVXDHJFFFFDDDDDDHAAAAJJJDDSLSSSDDDD') // 'A3V3B2VXDHJ4F6DH4A3J2DSL3S4D' Решение: function rle(str) { let encoded = ''; let count = 1; for (let i = 0; i < str.length; i++) { if (str[i] === str[i + 1]) { count++; } else { encoded += count > 1 ? count + str[i] : str[i]; count = 1; } } return encoded; } Простейшие алгоритмы сжатия: RLE и LZ77

Постановка: Напишите функцию reverseWords(str), которая принимает на вход предложение и возвращает его же, но уже с развернутыми словами, разделенными пробелами. Примеры вызова функции: reverseWords('Гречка может быть вкусной!') // ''акчерГ тежом ьтыб !йонсукв'' reverseWords('Апельсины - профилактика от онкологии') // 'ынисьлепА - акиткалифорп то ииголокно' Решение: function reverseWords(str) { return str.split('').reverse().join('').split(' ').reverse().join(' '); }

Постановка: Напишите функцию getVowelsCount(str), принимающую строку в качестве аргумента и возвращающую количество гласных, которые содержатся в этой строке. Гласными являются А, Е, Ё, О, У, Ы, Э, И, Ю, Я. Функция должна подсчитывать гласные любого регистра, то-есть работать независимо от регистра. Примеры вызова функции: getVowelsCount('Привет, медвед') // 4 getVowelsCount('Арифметика') // 5 getVowelsCount('Горная порода дикобраза') // 10 Решение: Вот самый простой вариант: function getVowelsCount(str) { let count = 0 const vowels = ['а', 'е', 'ё', 'о', 'у', 'ы', 'э', 'и', 'ю', 'я'] for (let char of str.toLowerCase()) { if (vowels.includes(char)) { count++ } } return count } Важно обратить внимание на использование метода .includes(). Он доступен и для строк, и для массивов. Его стоит применять для того, чтобы выявить, содержит ли массив определенное значение. Этот метод возвращает true, если массив содержит указанное значение, и false, если нет. Есть и более краткое решение проблемы: function getVowelsCount(str) { const matched = str.match(/[аеёоуыэиюя]/gi) return matched ? matched.length : 0 } Здесь задействуется метод .match(), который позволяет реализовать эффективный поиск. Если регулярное выражение как аргумент метода обнаружено внутри указанной строки, то возвращаемым значением становится массив совпадающих символов. Если совпадений нет, то .match() возвращает null.

Постановка задачи: Напишите функцию sortCharactersByFrequency(str), которая принимает строку в качестве входных данных и возвращает новую строку, в которой символы упорядочены по количеству их вхождений — от самого часто встречающегося до наименее часто встречающегося. Повторяющиеся символы должны включаться в итоговую строку только один раз. Пробел тоже считается символом, который нужно подсчитывать. Примеры вызова функции: sortCharactersByFrequency('абв') // 'абв' sortCharactersByFrequency('Старик и море') // 'ри Стакмое' sortCharactersByFrequency('Семья') // 'Семья' Решение: Прежде чем приступить к сортировке, необходимо подсчитать частоту встречаемости каждого символа в строке. Для этого мы используем объект JavaScript, где ключами будут символы, а значениями — их частота. function countCharacterFrequency(str) { let charFrequency = {}; for (let char of str) { charFrequency[char] = (charFrequency[char] || 0) + 1; } return charFrequency; } Эта функция проходит по каждому символу в строке, увеличивая соответствующее значение в объекте charFrequency. Если символ встречается впервые, он добавляется в объект с частотой 1. В конечном итоге функция возвращает объект с частотой каждого символа. После того как мы успешно подсчитали частоту символов, перейдем к их сортировке по убыванию частоты. Воспользуемся массивом, который отсортируем с использованием функции сравнения. function sortCharactersByFrequency(str) { const charFrequency = countCharacterFrequency(str); const sortedChars = Object.keys(charFrequency).sort((a, b) => { return charFrequency[b] - charFrequency[a]; }); return sortedChars.join(''); } В этой функции sortCharactersByFrequency, мы используем функцию countCharacterFrequency для получения объекта частоты символов. Затем мы получаем массив ключей (символов) и сортируем их в порядке убывания частоты. Функция сравнения sort сортирует символы так, чтобы те с более высокой частотой были первыми. Наконец, мы объединяем отсортированный массив символов в строку и возвращаем результат.

Постановка: Написать функцию, принимающую две строки и определяющую, являются ли они изоморфными. Изоморфными называются строки, между символами которых можно установить однозначное соответствие. Например, paper и title изоморфны (p = t, a = i, e = l, r = e). Количество и порядок символов при этом необходимо учитывать. egg и sad — неизоморфны, dgg и add — изоморфны. Решение: isIsomorphic("egg", 'add'); // true isIsomorphic("paper", 'title'); // true isIsomorphic("kick", 'side'); // false function isIsomorphic(str1, str2) { if (str1.length !== str2.length) { return false; } for (let i = 0; i < str1.length; i++) { for (let j = i + 1; j < str1.length; j++) { if ( (str1[i] === str1[j] && str2[i] !== str2[j]) || (str1[i] !== str1[j] && str2[i] === str2[j]) ) { return false; } } } return true; }