[Из песочницы] Решение частых алгоритмических вопросов на JavaScript
Вы когда-нибудь пытались разработать алгоритм решения задачи на техническом собеседовании? В этом коротком уроке мы разберём три главных вопроса о проектировании алгоритмов, начиная с метода грубой силы (шаг за шагом, но не обязательно эффективно) и переходя к более оптимизированному, элегантному решению.
Разворот строки
Задача
Получив строку, необходимо развернуть её.
Решение №1
Мы можем использовать метод string.substring (), позволяющий взять каждую букву параметра str и добавить её в новую строку. Метод подстроки принимает один обязательный параметр и один необязательный параметр.
Первый параметр — это индекс, с которого вы хотите начать подстроку. Это инклюзивное значение, если вы пишете myString.substring (1), вывод будет включать в себя первый символ.
Вторым (необязательным) параметром является конечный индекс. Этот параметр не является инклюзивным. Это означает, что ваша подстрока будет включать все символы до этого индекса плюс каждый оставшийся символ справа от этого индекса.
Другой метод, который мы могли бы использовать в данном способе решения, был бы string.charAt (). Метод charAt принимает один параметр: индекс символа, который вы хотите вернуть.
Давайте напишем два алгоритма решения для возврата обратной строки.
// Метод №1: Substring
function reverseString(str) {
let reversedString = '';
/* Проходим по каждому символу в аргументе str
Чтобы развернуть строку, мы присваиваем переменной i значение str.length
Добавляем по очереди каждый символ строки str, начиная с конца, в новую строку.
*/
for (let i = str.length; i > 0; i--) {
reversedString += str.substring(i, i-1);
}
return reversedString;
}
// Метод №2: CharAt
function reverseString(str) {
let reversedString = '';
/* с помощью цикла проходим по каждому элементу str
Чтобы развернуть строку мы присваиваем переменной i значение str.length-1 в то время, как i больше или равно 0.
Добавляем каждый символ, начиная с конца, в новую строку
*/
for (let i = str.length-1; i >= 0; i--) {
reversedString += str.charAt(i);
}
return reversedString;
}Решение №2
Один из самых быстрых встроенных способов решения этой проблемы — разбить каждый символ в строке на элемент массива, перевернуть элементы в массиве и превратить элементы массива обратно в строку.
Мы будем использовать следующие методы:
string.split () — разбивает каждый символ на индекс массива.
string.reverse () — разворачивает элементы массива в обратном порядке.
string.join () — объединяет все элементы массива в строку.
Вы можете связать эти три функции вместе для элегантного решения.
function reverseString(str) {
return str.split('').reverse().join('');
}Самое длинное слово
Задача
Вернуть длину самого длинного слова в проверяемом предложении.
Решение №1
Для первой попытки вы можете использовать string.split (' ') метод разбиения отдельных слов в предложении на массивы индексов. Этот способ не будет учитывать пунктуацию, однако вы можете решить эту проблему с помощью регулярного выражения.
Далее мы можем перебрать каждый элемент массива и подсчитать количество букв в каждом слове. Мы можем отследить самое длинное слова в предложении. Если текущее значение слова больше максимального значения слова, сохраненного в данный момент, заменяем его! Затем просто возвращаем переменную, содержащую самое длинное слово.
Вы можете перебрать массив с помощью цикла for или метода array.forEach (). Я предпочитаю последнее, но я включила и то, и другое ниже.
// Решение с использованием цикла for
function findLongestWordLength(str) {
let maxVal = 0;
const wordArr = str.split(' ');
for(let i = 0; i < wordArr.length; i++) {
let word = wordArr[i];
if (word.length > maxVal) {
maxVal = word.length;
}
}
return maxVal;
}
// Решение с использованием метода array.forEach
function findLongestWordLength(str) {
let maxVal = 0;
const wordArr = str.split(' ');
wordArr.forEach(word => {
if (word.length > maxVal) {
maxVal = word.length;
}
});
return maxVal;
}Решение №2
Чтобы оптимизировать это решение, мы всё равно будем использовать метод string.split (), который позволяет разделить предложение на элементы массива по словам.
Далее мы будем использовать метод array.map (), который позволяет взаимодействовать с различными значениями каждого элемента массива. Это вернет совершенно новый массив с необходимыми значениями, поэтому мы сохраним его в новой переменной.
Для каждого элемента в массиве вернём длину строки и сохраним её в новом массиве под названием arrOfLengths.
Наконец, мы можем использовать метод Math.max (…spreadOperator) с оператором spread для того, чтобы вернуть целочисленное значение для самой длинной строки в предложении.
function findLongestWordLength(str) {
const arrOfWords = str.split(' ');
const arrOfLengths = arrOfWords.map(item => item.length);
return Math.max(...arrOfLengths);
}Массив наибольших значений вложенного массива
Задача
Возвращает массив, состоящий из наибольших чисел каждого вложенного массива. Для простоты предоставленный массив будет содержать ровно 4 вложенных массива.
[1,2,3,4]
[5,18,0,12]
[3,5,12,5]
[28,9,2,34]
Should return => [4,18,12,34]Решение №1
В качестве первого решения мы можем начать с вложенного цикла for-loop.
Для каждого элемента во внешнем массиве просмотрим его вложенный массив и найдём наибольшее значение, а затем вставим его в новый массив.
// вариант с циклом for
function largestOfFour(arr) {
let arrayOfMaxValues = [];
for (let i = 0; i < arr.length; i++) {
let subArr = arr[i];
let maxSubArrVal = 0;
for (let j = 0; j < subArr.length; j++) {
let currentValue = subArr[j];
if (currentValue > maxSubArrVal) {
maxSubArrVal = currentValue;
}
}
arrayOfMaxValues.push(maxSubArrVal);
}
return arrayOfMaxValues;
}
// вариант с forEach
function largestOfFour(arr) {
let arrayOfMaxValues = [];
arr.forEach(subArr => {
let maxSubArrVal = 0;
subArr.forEach(item => {
if (item > maxSubArrVal) {
maxSubArrVal = item;
}
});
arrayOfMaxValues.push(maxSubArrVal);
});
return arrayOfMaxValues;
}Решение №2
Мы можем использовать метод Math.max (…spreadOperator) с методом array.map () для циклического перебора каждого элемента во внешнем массиве, возврата максимального значения из вложенного массива и прямого возврата этого вновь созданного массива.
function largestOfFour(arr) {
return arr.map(subArr => Math.max(...subArr));
}Данная статья является переводом оригинальной статьи «Breaking Down JavaScript Solutions To Common Algorithmic Questions (Part 1)» by Emma Bostian
Данная статья является лишь одной из частей цикла статей. Автор оригинальной статьи планирует делать продолжение, а в случае выхода новых частей — я подготовлю перевод!
Эту и многие другие полезные статьи для начинающих JavaScript-разработчиков я транслирую в Telegram-канале school.js, где также готовлю полезные викторины для проверки своих знаний. Обращаю внимание, что канал является исключительно хобби и желанием помочь и не несет для меня материальной выгоды.
