Когда дело доходит до поиска работы и собеседования по кодированию, вам нужно будет уметь продумывать задачи собеседования на основе алгоритмов перед интервьюером или группой экспертов. Практика с самого начала поможет вам успешно пройти технические собеседования.
Обычный вопрос, который вы можете ожидать от реализации, — это проверка того, является ли строка палиндромом. Чтобы познакомить вас с этой проблемой, мы рассмотрим, что такое алгоритм, и узнаем, как решить эту проблему несколькими способами.
Обновление алгоритмов
Вообще говоря, алгоритм — это набор шагов, необходимых для того, чтобы что-то сделать. Подумайте, что нужно, чтобы испечь торт или поменять масло в машине. Все шаги и все инструменты или ингредиенты, необходимые для того, чтобы эти вещи происходили по порядку, являются частью алгоритма.
На высоком уровне алгоритм — это рецепт или руководство по выполнению ряда шагов, которые позволят решить проблему.
В информатике алгоритмы относятся к последовательности четко определенных инструкций, которые говорят компьютеру, что делать для решения проблемы. Точно так же, как у нас должна быть серия шагов, чтобы испечь торт, нам нужна серия четко определенных инструкций для создания алгоритма, который решит нашу проблему.
Существуют всевозможные алгоритмы, и они обычно возникают на собеседованиях по кодированию. Алгоритмы применяются к разным структурам данных. Итак, мы берем структуру данных и применяем алгоритм для выполнения с ней определенных операций.
В этой статье мы рассмотрим, как управлять строкой с помощью алгоритма, в частности, как проверить, является ли строка палиндромом.
Разбивка задач кодирования
Цель этого алгоритма — ввести строку и использовать функцию, чтобы проверить, является ли это палиндромом.
Палиндром — это слово или фраза, которые читаются одинаково вперед и назад. Когда палиндромы равны длине предложения, они игнорируют заглавные буквы, пунктуацию и границы слов.
Например: гоночный автомобиль, 1001, 11.11.11 или 11:11.
Подсказка
Для заданного значения напишите функцию, которая будет проверять, является ли строка палиндромом или нет. Верните, trueесли это так или falseнет.
Примеры:
isPalindrome(“”) // true isPalindrome(1010) // false isPalindrome(“taco Cat”) // true isPalindrome(“Was it a car or a cat I saw?”) // true isPalindrome(“hello”) // false isPalindrome(“momma made me eat my m&ms”) //false
Подход
Есть несколько различных подходов к решению этой проблемы, которые мы рассмотрим ниже. Но сначала давайте поговорим об этом так, как если бы мы просто объясняли ответ кому-то без кода.
Итак, нам дана ценность. Что это за ценность? Это строка? Это что-то еще?
В приглашении не указывается тип значения. Если бы вы были в ситуации собеседования, это могло бы быть место, где вы могли бы подтвердить интервьюеру, является ли данное значение строкой.
Поскольку палиндром технически может быть чем угодно, давайте разберемся со всеми типами и рассмотрим все крайние случаи. В большинстве случаев на техническом собеседовании вам не нужно беспокоиться о крайних случаях, но интервьюер заметит, если вы скажете об этом.
Напишите функцию, которая будет проверять, является ли это значение палиндромом. Это должно указывать на то, что им нужно логическое значение ( Trueили False).
То, что мы знаем на данный момент:
- Наше значение может быть строкой, числом или объектом
- Нам нужно вернуть логическое значение
- Палиндром игнорирует регистр, пробелы и знаки препинания.
Псевдокод
Во-первых, нам нужно рассмотреть тип значения.
- Если это число, нам нужно преобразовать его в строку, чтобы сравнить, как оно читается в прямом и обратном направлениях.
- Если это объект, нам нужно как-то изменить его на строку, чтобы провести сравнение.
- А также если это строка, мы можем двигаться вперед.
- Если у нас есть null или undefined, как мы с этим справимся?
После того, как мы выяснили тип и изменили его на строку, нам нужно подготовить строку, чтобы мы могли читать ее слева направо и справа налево без каких-либо не буквенно-цифровых символов.
Нам нужно позаботиться об удалении всего постороннего. Мы можем сделать это несколькими способами, например, перебирая строку для удаления определенных символов.
Также мы должны позаботиться о том, чтобы игнорировать буквы, прописные или строчные. Мы можем сделать это, сделав все заглавными или строчными буквами.
Как только все символы, отличные от буквенно-цифровых, исчезли и у нас есть строки в одном корпусе, теперь наша строка готова к тестированию !
Подумайте о возможных способах решения этой проблемы:
- Сравните строку с ее обратной версией (методы JS)
- Выполните итерации, используя цикл for, и проверьте, есть ли символ на другой стороне строки ===
- Используйте рекурсию, чтобы проверить первую и последнюю буквы перед повторным вызовом функции с сокращенной строкой
Настройка кода JavaScript
Есть несколько способов решить эту проблему. Пока вы можете объяснить свой подход и прийти к правильному ответу, ваш подход, вероятно, будет в порядке. Это всего лишь три возможных способа выяснить, является ли переданное значение палиндромом или нет.
Независимо от вашего подхода, установка требует, чтобы мы подготовили значение для тестирования. Давайте продолжим и сделаем это сейчас. Это будет одинаково для всех трех решений.
const stripNonAlphaNum = (val) => {let str;switch(typeof val) {case «number»:str = val.toString();break;case «object»:str = JSON.stringify(val);break;case «string»:str = val;break;case «boolean»:str = null;break;}if(str === null || str === undefined) {return null;}else if(str.length === 0){return «»;}else {let newStr = str.toLowerCase().replace(/[\W_ ]/g, «»);return newStr;}}
В этом коде мы используем typeofнаш, valчтобы создать оператор switch, который присвоит переменной strстроковую версию значения. Если valэто число, нам просто нужно сделать его строкой.
А также если это объект, вы можете преобразовать его в строку с помощью одноименного метода JSON. Если это логическое значение, установите для строки значение null, поскольку логические значения не являются палиндромами.
Следующие строки кода проверяют, равна 0ли длина строки, является ли strона неопределенной или нулевой. Если это пустая строка, мы хотим присвоить strпустой строке. В противном случае мы вернем null.
Примечание. Технически пустая строка является палиндромом, поскольку она читается одинаково в прямом и обратном направлениях.
Наконец, мы используем несколько методов JavaScript, чтобы сделать все в нижнем регистре и заменить поисковый запрос пустой строкой. Этот поисковый запрос представляет собой регулярное выражение, которое ищет в строке все символы, не являющиеся буквенно-цифровыми, подчеркиваниями и пробелами.
Мы присваиваем это выражение вызываемой переменной newStrи возвращаем его.
Решение 1. Сравните строку с ее перевернутой версией
Мы собираемся использовать методы split, reverse и join, чтобы проверить, совпадает ли обратная версия строки с самой строкой.
const isPalindrome = (val) => {let str = stripNonAlphaNum(val);if(str === null) return false;return str.split(»).reverse().join(») === str;}
В первой строке функции мы назначаем strто, что возвращается из stripNonAlphaNum()функции, которая использует регулярное выражение для удаления всех лишних символов, которые нам не нужны, и для строчных букв всех символов.
Вот набор тестов, которые вы можете использовать, чтобы убедиться, что ваш код работает правильно:
console.log(isPalindrome(«taco Cat»)); // trueconsole.log(isPalindrome(1010)); // falseconsole.log(isPalindrome(«Was it a car or a cat I saw?»)); // trueconsole.log(isPalindrome({a: «b», b: «a»})); // trueconsole.log(isPalindrome(null)); // falseconsole.log(isPalindrome(false)); // falseconsole.log(isPalindrome(«»)); //true
Решение 2. Повторяйте использование цикла for
В этом решении мы собираемся использовать обычный цикл for для перебора строки. На каждой итерации давайте посмотрим на соответствующую букву, которая находится на одинаковом расстоянии от конца, чтобы увидеть, равны ли они.
Если мы дойдем до центра слова и все будет одинаково, мы получим палиндром. Иначе мы вернемся false.
const isPalindrome =(val) => {let str = stripNonAlphaNum(val);if(str === null) return false;for(let i = 0; i < str.length/2; i++) {if(str[i] !== str[str.length — 1 — i]) {return false;}}return true;}
Здесь мы выполняем итерацию только до середины строки, потому что мы проверяем вторую половину строки на ее аналог в передней половине строки.
Хороший подход к решению проблем — всегда проверять ложные значения. Если мы дойдем до пары букв, которые не совпадают, мы знаем, что это не палиндром, и можем остановиться на этом. Это то, что делает первая строка цикла for.
Мы проверяем, равен ли текущий символ персонажу в том же месте с конца. Если не совпадает, верните false.
Если мы проходим весь цикл for, а условие внутри цикла for не сработало, это означает, что все символы одинаковы, и у нас есть палиндром.
Решение 3. Используйте рекурсию
В этом третьем и последнем решении мы собираемся использовать рекурсию, чтобы выяснить, является ли наше значение палиндромом или нет. Помните, что для рекурсии нам нужен базовый вариант, иначе мы превысим максимальный размер стека вызовов.
const isPalindrome = (val) => {let str = stripNonAlphaNum(val);if(str == null || str === undefined) return false;let length = str.length;if (length === 0 || length === 1) {return true;}if (str[0] === str[length — 1]) {return isPalindrome(str.slice(1, length — 1) );}return false;};
Мы начинаем с получения строкового значения, вызывая функцию, которую мы написали для символов нижнего регистра, и избавляемся от всех не буквенно-цифровых символов. Если он проходит нулевой тест, мы проверим строку на соответствие нашему базовому случаю.
Если базовый случай прошел, это означает, что мы проверили всех наших персонажей и у нас есть палиндром.
В следующем условном выражении происходит наша рекурсия. Мы хотим сравнить первую букву строки с последней буквой строки.
Если они равны, мы вернем isPalindrome()функцию и передадим копию строки за вычетом первого символа и последнего символа в качестве аргумента.
Рекурсия будет продолжаться до тех пор, пока у нас есть совпадающие буквы или пока мы не достигнем нашего базового случая. Если мы попадаем в базовый вариант, наш strпалиндром, и мы возвращаемся true. Если в какой-то момент у нас есть символы, которые не совпадают, мы возвращаемся false.
