Пошаговое руководство по решению этого вопроса алгоритма с использованием хэш-карты.
Чувак, я действительно начинаю любить хэш-карты.
Странное ощущение. Всего несколько месяцев назад я едва мог решить вопрос об алгоритме самостоятельно, не говоря уже о том, чтобы найти достаточно эффективное решение. Хотя я все еще осознаю огромный пробел, который мне нужно преодолеть, чтобы достичь того, чего я хочу достичь как разработчик программного обеспечения, важно осознавать эти маленькие победы в моем саморазвитии.
Это чувство ничем не отличается - многократное использование хэш-карты заставляет мой разум рассматривать ее как вариант с большинством вопросов по алгоритму, с которыми я сталкиваюсь в последнее время, и приятно чувствовать, что я наконец разблокирую та часть моего мозга.
Благодарим вас, Уоррен, за то, что вы остались с ним и не сдавались.
Достаточно позитива - давайте займемся этой проблемой перемешивания строк.
Эта проблема
Обратите внимание, что эта проблема связана с Leetcode (# 1528). Чтобы попытаться решить эту проблему напрямую, посетите: https://leetcode.com/problems/shuffle-string/
Наша проблема гласит:
Дана строка s и индексы целочисленного массива одинаковой длины. Строка s будет перемешана так, что символ в i- позиции переместится в индексы [i] в перемешанной строке. Вернуть перемешанную строку.
Хм, это звучит немного запутанно - давайте возьмем пример из Leetcode, чтобы попытаться визуализировать эту проблему немного лучше.
У нас есть два входа, строка и целочисленный массив. Скажем, наши два входа следующие:
Входная строка: codeleet
Целочисленный массив: [4, 5, 6, 7, 0, 2, 1, 3]
Итак, каков наш ожидаемый результат? Давайте еще раз прочитаем следующую строку в инструкции:
Строка s будет перемешана таким образом, что символ в i- -й позиции переместится в индексы [i] в перемешанной строке.
Это означает, что «c» переместится в 4-й индекс, «o» - в 5-й индекс, «d» - в 6-й индекс и т. Д.
Наш ожидаемый результат будет выглядеть следующим образом:
Большой! Теперь, когда мы понимаем вопрос, как нам подойти к этой проблеме?
Подход
Поэтому нам нужно как-то переместить наши буквы в соответствующий индекс. Поскольку мы уже знаем, под каким номером и назначенным индексом они должны быть, мы можем настроить их как пары ключ-значение в хэш-карте!
- Создайте пустой хеш, в котором будут храниться наши индексы и соответствующий им символ.
- Создайте экземпляр новой строки, в которой мы будем создавать нашу вновь организованную строку в их перетасованном порядке.
- Настройте цикл for, который будет перебирать длину нашего массива индексов, заполняя нашу хэш-карту нашими парами значений ключа - начиная с нулевого индекса.
- Настройте второй цикл for, который будет строить нашу строку, ища пары ключ-значение в нашей хэш-карте.
- Верните нашу вновь созданную строку в конце нашей функции
Решение
Давайте попробуем и сделаем шаг за шагом.
Наши первые два шага включают создание пустого хэша, а также новую перетасованную строку, которую мы вернем в конце нашей функции. Достаточно просто!
Все идет нормально.
Наш следующий шаг - перебрать наш входной массив индексов. Помните, что на этом этапе наша цель - построить нашу хеш-карту, начиная с нулевого индекса. Поскольку у нас есть индексы и соответствующий им символ во входной строке, мы можем установить наши ключи хэша на индекс, а их соответствующее значение - на символ во входной строке. Чтобы получить значение строки по определенному индексу, мы можем использовать строковый метод charAt ().
Например, в нашем примере s.charAt (0) вернет нам «c».
Давайте теперь построим нашу хеш-карту:
На каждой итерации мы устанавливаем для нашего ключа (индекса) соответствующее значение во входной строке.
Как вы можете видеть в нашем console.log, у нас есть хорошо построенная хэш-карта, в которой наши ключи расположены в возрастающем порядке, что дает нам желаемый результат («leetcode»).
Наш последний шаг - перебрать нашу хеш-карту и добавить наши значения в нашу переменную newString:
Заключение
И вот оно! Используя хэш-карту, мы можем сразу связать наши индексы и соответствующий им символ во входной строке. Путем итерации по массиву индексов создается хэш-карта в порядке индексов и размещает наши буквы в соответствующем порядке, что в конечном итоге дает нам желаемый результат.
Хотя хеш-карта - это один из способов решения этой проблемы, я хотел бы услышать, как вы подошли к этой проблеме! Не стесняйтесь оставлять комментарии ниже или обращаться ко мне напрямую.
До скорого.
Больше контента на plainenglish.io
