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

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


image


Разворот строки


Задача


Получив строку, необходимо развернуть её.


Решение №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

Данная статья является лишь одной из частей цикла статей. Автор оригинальной статьи планирует делать продолжение, а в случае выхода новых частей — я подготовлю перевод!


Эту и многие другие полезные статьи для начинающих Frontend-разработчиков я транслирую в Telegram-канале Frontend.school(), где также готовлю полезные викторины для проверки своих знаний. Обращаю внимание, что канал является исключительно хобби и желанием помочь и не несет для меня материальной выгоды.

Ads
AdBlock has stolen the banner, but banners are not teeth — they will be back

More

Comments 14

    +4

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


    image


    Это происходит, потому что ваш код не учитывает существование знаков вне BMP, которые кодируются суррогатными парами UTF-16, и адресует не codepoint-ы, а их UTF-16-кодированное представление.

      –1
      Интересное замечание, не знал этого)
      Но это не мои решения, а автора оригинальной статьи — у меня перевод)
      0
      Во второй задаче гораздо разумнее найти позиции небуквенных символов, разница между ними и будет длиной слов. Такой подход сэкономит и время и память. (мы же хотим это сделать оптимально, иначе вообще подобные легкие задачи решать интереса мало)

      const re = /[^A-Za-zА-Яа-я]/g
      const string = 'Моя удивительная строка'
      let match, pos = 0, maxLength = 0 
      
      while (re.exec(string + '.') !== null) {
        maxLength = Math.max(maxLength, re.lastIndex - pos - 1)
        pos = re.lastIndex
      }
      
      console.log('Длина самого длинного слова:' + maxLength)
        0

        Можно ускорить ваше решение, если искать не небуквенные символы, а места переходов от буквенных к небуквенным:


        function longest(s) {
          const reStart = /(?:\W|^)\w/g;
          const reEnd = /\w(?:\W|$)/g;
          let inWord = false;
          let longest = 0;
          let startOffset;
        
          do {
            if (!inWord) {
              const m = reStart.exec(s);
              if (!m) {
                return longest;
              }
              reEnd.lastIndex = reStart.lastIndex - 1;
              startOffset = m.index - 2 + m[0].length;
              inWord = true;
            } else {
              const m = reEnd.exec(s);
              reStart.lastIndex = reEnd.lastIndex - 1;
              longest = Math.max(longest, m.index - startOffset);
              inWord = false;
            }
          } while (true);
        };
          –1
          Регулярки меня всё-таки сведут с ума)
          Можете подсказать хорошие статьи по ним?
            0
            Возможно достаточно поменять выражение на
            /[^A-Za-zА-Яа-я]+/g
              0

              но это будет извлекать ненужные участки междусловных знаков как строку, от чего мы вроде как хотели избавиться? :)
              И, наверное, лучше использовать классы знаков — ваше выражение аналогично /\W+/g, но не считается с буквами других алфавитов.

                0
                Мы хотели избавиться от извлечения слов, но возможно вы правы, это лишнее
            +1

            А Вы уверены, что регулярки в данном случае сэкономят время? Это довольно тяжелый инструмент. Я бы уж тогда сделал вот так


            const string = 'Моя удивительная строка';
            let pos = 0, max = 0;
            for (const idx in string) { 
                if (string[idx] == ' ' || idx == string.length - 1) { 
                    max = Math.max(max, idx - pos); 
                    pos = idx; 
                }
            }
              0
              Регулярку использовал просто для удобства, чтобы не писать

              const l = string[idx]
              if ((l < 'A' || l > 'Z') && 
                     (l < 'a' || l > 'z') &&
                     (l < 'А' || l > 'Я') &&
                     (l < 'а' || l > 'я'))


              Так да, возможно перебор будет немного быстрей.
                0
                В обоих случаях могут быть проблемы с «Ё»/«ё» (и это ещё без учёта некоторых других языков).
                0
                А знаки препинания?
              0

              Странно, что в примерах на поиск максимума в массивах не используется reduce. На мой взгляд это проще, чем map с… И вообще создавать дополнительные массивы для поиска максимума странно, если можно обойтись итераторами.

                0

                Вторая задача не учитывает пунктуацию. Можно сделать так:


                image


                Или, как вариант, не абюзить replace и запросить все матчи как-то так:


                const allMatches = (s, re) => {
                    const matches = [];
                    let m;
                    while (m = re.exec(s)) {
                        matches.push(m[0]);
                    }
                    return matches;
                }

                Но мне кажется, что это проще сделать за один проход.

                Only users with full accounts can post comments. Log in, please.