Главная » Статьи » Нахождение наиболее часто повторяющегося символа в JavaScript

Нахождение наиболее часто повторяющегося символа в JavaScript

Нахождение наиболее часто повторяющегося символа в JavaScript

От автора: как найти в коде JavaScript символ, встречающийся чаще всего, а также подсчитать общее количество повторов? В этой задаче мы будем иметь дело со строками, массивами и объектами. Мы научимся работать с этими типами данных, используя различные методы, которые в итоге дадут нам рабочее решение.

Довольно разговоров, давайте приступим! Здесь вы можете найти код.

У вас уже должна быть настроенная среда разработки для этого курса. Обновите свой клонированный репозиторий, выполнив команду git pull. Внутри папки Beginner перейдите к папке maxRecurringChar. Наша работа для этой задачи будет выполняться здесь. Обязательно следуйте инструкциям в файле index-START.js.

Вызов

Получив строку текста, найдите и верните наиболее часто повторяющийся символ. Например:

maxRecurringChar('aabacada') // возвращает 'a'

Довольно просто, да?

Продумывание алгоритма

Из оператора вызова мы можем сделать вывод, что наша функция имеет только один параметр; строку текста. Нам нужно как-то отслеживать каждый символ в строке, а также количество раз, которое он встречается. Это мы бы описали как карта символов. После того, как мы успешно создадим такую карту, мы сможем легко определить, какой символ имеет больше всего вхождений.

Реализация кода

Из приведенных выше рассуждений вы заметили, что есть одна вещь, которая очень важна, если мы хотим найти подходящее решение этой проблемы. Нам нужно отслеживать каждый символ в строке, а также количество раз, которое он встречается. Как нам это сделать?

Карта символов

Представьте, что вам дали мешок с шарами следующих цветов; зеленый, красный, синий и желтый. Ваша задача — отсортировать их. Интуитивно понятно, что вы должны вынуть шарики из сумки и сгруппировать их по цвету. В конце концов, именно эти группы шаров одинакового цвета помогут вам определить, какое количество шаров каждого цвета существует, и, соответственно, самый часто встречающийся цвет.

Поздравляем! Вы успешно сопоставили шары. Теперь давайте выполним ту же магию с символами. Наше намерение состоит в том, чтобы сопоставить символы с количеством раз их вхождения, как показано ниже. Если бы у нас была строка текста ‘aaabbbcdcb’, мы бы имели:

a = 3

b = 4

c = 2

d = 1

Чтобы реализовать это, очень удобно использовать объект. Мы перебираем полученный текст и добавляем каждый символ к объекту карты символов в качестве ключа и количество раз, которое он встречается, в качестве значения. Объект будет выглядеть так:

let charMap = { a:3, b:4, c:2, d:1
}

Вот как мы создаем такой объект из строки **text**:

let charMap = {}; for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap[char]++ } else { charMap[char] = 1; }
}

Инициализировав пустой объект charMap, мы используем цикл for… для перебора строки текста. Для каждого символа мы проверяем, было ли оно сопоставлено (является ли свойством объекта charMap), вызывая метод объекта .hasOwnProperty(). Если это так, мы увеличиваем его значение, в противном случае оно добавляется как свойство и его значение устанавливается равным 1.

Создав карту символов, мы теперь можем сосредоточиться на реальном решении проблемы. Нам нужно вернуть символ, который наиболее часто встречается. Давайте теперь рассмотрим два способа сделать это.

Итерация for…in

JavaScript предлагает различные способы перебора итерируемых объектов. Итерируемый объект в основном представляет собой набор последовательно отформатированных данных. В качестве примера можно назвать строки, массивы, объекты, подобные массиву и т. д. Оператор for… in выполняет итерацию по всем не-символьным , перечисляемым свойствам объекта. Посмотрите, как мы используем это ниже:

function maxRecurringChar(text) { let charMap = {} let maxCharValue = 0 let maxChar = '' for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap[char]++ } else { charMap[char] = 1 } } for (let char in charMap) { if (charMap[char] > maxCharValue) { maxCharValue = charMap[char] maxChar = char } } return maxChar
}

Вы заметите, что в приведенной выше функции maxRecurringChar мы используем фрагмент, рассмотренный ранее, для генерации карты символов полученной строки текста. Для циклического прохождения объекта charMap мы инициализируем в начале две переменные.

maxCharValue используется для хранения максимального значения, которое встречается в точке каждой итерации в цикле for… in.

maxChar используется для хранения символа с наибольшим значением на каждой итерации.

Выполняя цикл for… in, мы проверяем, имеет ли оцениваемый символ большее значение, чем наше maxCharValue, которое изначально равно нулю. Если это так, он становится новым maxCharValue и символ сохраняется в maxChar. Если это не так, мы переходим к следующему символу.

В конце мы возвращаем maxChar, который теперь содержит символ с наибольшим значением, и, таким образом, наиболее повторяющийся. Все понятно? Давайте теперь попробуем другой способ.

Формирование массивов из карты символов

В ES6 мы можем выполнять различные вычисления для объектов, сначала преобразовывая их в массивы. ES6 — это в основном EcmaScript 6 / EcmaScript 2015. EcmaScript — это просто стандарт, на котором основан JavaScript. Итак, ES6 — это новая версия или новый стандарт JavaScript. В ES6 появилось много новых функций, таких как концепция классов, теги шаблонов, функции стрелок и т. д.

Давайте посмотрим, как это работает:

function maxRecurringChar(text) { let charMap = {} let charArray =[] let vaulesArray = [] let maxCharValue = 0 for (let char of text) { if (charMap.hasOwnProperty(char)) { charMap[char]++ } else { charMap[char] = 1 } } charArray = Object.keys(charMap) vaulesArray = Object.values(charMap) maxCharValue = Math.max(...vaulesArray) return charArray[vaulesArray.indexOf(maxCharValue)]
}

В приведенном выше фрагменте кода мы снова создаем карту символов с первоначально рассмотренным фрагментом кода. Далее мы используем синтаксис ES6 для формирования массивов из карты символов. Сначала массив ключей charMap (все символы в тексте), известный как charArray, а затем массив значений (число вхождений), известный как valuesArray, упорядоченных в соответствующем порядке.

Для карты символов, которую мы визуализировали ранее (например, «aaabbbcdcb»), у нас было бы что-то вроде этого:

charArray = ['a', 'b', 'c','d']
valuesArray = [4,3,2,1]

Далее мы используем встроенную функцию Math.max() для поиска максимального значения в массиве значений и сохраняем это значение в переменной maxCharValue.

Наконец, мы используем метод .indexOf() для поиска valuesArray для позиции maxCharValue. Это необходимо, так как положение maxCharValue в valuesArray соответствует положению символа в charArray с этим числом вхождений.

Таким образом, при получении индекса (позиции) мы возвращаем символ, занимающий ту же позицию в charArray. Это самый часто встречающийся символ. Мы наконец сделали это! Теперь давайте проверим наши решения.

Тестирование

Тестирование с помощью Jest. Для каждого решения, приведенного выше, выполните следующую команду, чтобы запустить тесты:

npm run test maxRecurringChar

Вот результаты:

Итерация for…in

Формирование массивов из карты символов

Надо отметить, что оба решения приняты во всех случаях.

Тестирование производительности с помощью JSPerf. Здесь, на JSPerf, мы сравниваем оба решения, чтобы увидеть, какое из них работает лучше. Смотрите результаты ниже:

Всегда проверяйте тесты самостоятельно, чтобы убедиться, что у вас есть похожие результаты. Результат, как приведенный выше, приводит нас к выводу, что: For … In итерация является самой быстрой. При использовании метода Arrays отставание составляет примерно 30%.

Практическое применение

Вы найдете методы, рассмотренные в этой задаче, полезными при собеседовании на JavaScript и проблемам кода. Кроме того, они могут использоваться на более продвинутом уровне в поисковой оптимизации (SEO) для определения плотности ключевых слов в части контента.

Заключение

Из этой задачи мы научились управлять объектами, используя различные методы JavaScript. Мы рассмотрели два способа решения проблемы и определили, что цикл For… in лучше оптимизирован. Тем не менее, оба рассматриваемых решения отлично работают и могут быть использованы на собеседовании.

Автор: Obosi Philip

Источник: https://scotch.io/

Редакция: Команда webformyself.