Задача с собеседования: как найти палиндром

Задача с собеседования: как найти палиндром

Элитная задача с сайта Leetcode

Продолжаем разбирать задачки с сайта Leetcode. В прошлый раз было про массив и сумму чисел, теперь тоже необычное. 

Условия

В переменной X лежит какое-то целое число

Задача — проверить, является ли это число палиндромом.

Задача со звёздочкой — проверить на наличие палиндрома, не используя строки.

Палиндром — это когда строка или число одинаково читается в прямом и обратном направлении:

121 — это палиндром.

А роза упала на лапу Азора — тоже палиндром (если не считать заглавных букв).

12321 — и это палиндром.

Решение, где используем строки

Самый простой способ проверить, число в переменной палиндром или нет, — преобразовать его в строку, выставить знаки задом наперёд и сравнить с оригиналом. Этим мы сразу решаем проблему отрицательных чисел, когда «−121»превращается в «121−» и сразу становится ясно, что это не палиндром.

Сначала решим это на Python. Тут вообще суть в одной строке:

X = 121
if str(X) == str(X)[::-1]:
    print("Это палиндром")
else:
    print("Это не палиндром")

Здесь мы использовали трюк с переворачиванием строки без её изменения — применили конструкцию [::-1]. Работает это так:

  • Первым параметром указывают начало, откуда начинать обработку строки. Раз ничего не указано, то начинаем с первого символа.
  • Второй параметр — на каком по счёту символе надо остановиться. Здесь тоже ничего нет, поэтому алгоритм пройдёт до конца строки.
  • Последний параметр — шаг и направление обработки. У нас указана минус единица, значит, алгоритм обработает строку справа налево, на каждом шаге считывая по символу.
  • В итоге этот код вернёт нам строку, собранную в обратном порядке, при этом с оригинальной строкой ничего не случится — она останется неизменной.

Мы уже делали похожие штуки, когда писали свой генератор новых слов, но там было одно двоеточие, а здесь два.

Теперь решим это же, но на JavaScript:

var X = 121;
if (X.toString().split("").reverse().join("") == X.toString()) {
    console.log("Это палиндром")
} else {
    console.log("Это не палиндром")
}

Здесь мы использовали другой метод пересборки:

  1. X.toString() — переводит число в строку.
  2. split("") — разбивает строку на массив из символов. В кавычках принцип разделения — если бы там была точка, то разделили бы на местах точек. А так как там пустота, то делится вообще по каждому из символов.
  3. reverse() — меняет элементы в массиве в обратном порядке.
  4. join("") — добавляет результат к пустой строке, чтобы на выходе получить строку в обратном порядке.

Решение без строк

Тем, кто справился с первой частью, предлагают задачу со звёздочкой — сделать то же самое, но не используя строки, а работая только с числами. Попробуем и мы.

Сделаем в JavaScript функцию, которая будет возвращать true, если в переменной лежит палиндром, и false — если нет. Всё остальное будем писать внутри этой функции:

function palindrome(x) {
}

Теперь обработаем три стандартные ситуации:

  1. Если в переменной лежит ноль, то это палиндром.
  2. Если переменная меньше ноля, то это не палиндром.
  3. Если переменная делится на 10 без остатка — это тоже не палиндром.

Запишем это на JavaScript:

function palindrome(x) {
    // если перед нами ноль — это палиндром
    if(x == 0) {
        return true;
    }
    // если число меньше нуля или делится на 10 без остатка — это не палиндром
    if(x < 0 || x%10 == 0){
        return false;
    }
}

Чтобы проверить, является ли число палиндромом или нет, можно сделать так: отрезаем от числа цифры справа по одной, добавляем их в начало нового числа и постоянно сравниваем новое и старое значение. Если они станут равны — перед нами палиндром. Читайте комментарии, чтобы вникнуть в то, что происходит в коде:

function palindrome(x) {
    // если перед нами ноль — это палиндром
    if(x == 0) {
        return true;
    }
    // если число меньше нуля или делится на 10 без остатка — это не палиндром
    if(x < 0 || x%10 == 0){
        return false;
    }
    // сюда будем собирать число в обратном порядке
    temp = 0;
    // а тут будем хранить промежуточные значения икса
    preX = x;
    // пока не дойдём до середины числа — повторяем цикл
    while (x > temp) {
        // берём самую правую цифру в числе — это остаток от деления на 10
        pop = x%10;
        // запоминаем старое значение переменной X
        preX = x;
        // и отрезаем от переменной последнюю цифру — делаем это через целую часть деления на 10
        x /= 10;
        // добавляем отрезанную цифру к обратной переменной
        temp = temp*10 + pop;
    }
    // если обратная переменная совпала с оставшейся половиной исходной переменной — это палиндром
    // мы добавляем сравнение с предыдущей версией исходной половины (которая на 1 цифру больше) на тот случай, если исходное число состояло из нечётного количества символов и его нельзя было бы разбить строго пополам
    if(x == temp || preX == temp)
        return true;
    // 
    else
        return false;
};

Для запуска кода просто вызываем функцию и передаём её нашу переменную:

// запускаем код
var X = 121;
console.log(palindrome(X));

Чтобы попрактиковаться, попробуйте сделать такое же, но на Python и не подглядывая в наш код.

Текст:

Михаил Полянин

Редактор:

Максим Ильяхов

Художник:

Алексей Сухов

Корректор:

Ирина Михеева

Вёрстка:

Кирилл Климентьев

Соцсети:

Виталий Вебер

Получите ИТ-профессию
В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.
Начать карьеру в ИТ
Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию Получите ИТ-профессию
Еще по теме
Разбор: задача про массив и сумму чисел
Разбор: задача про массив и сумму чисел

Простой код для собеседований

easy
Подключаем логгер к проектам на JavaScript
Подключаем логгер к проектам на JavaScript

Следим за каждым шагом программы

medium
Как сделать свой сайт за 10 минут без программирования

Для некоторых это становится источником постоянного дохода, если подойти к процессу с умом.

easy
Решаем кодом: найти самую длинную вложенную строку
Решаем кодом: найти самую длинную вложенную строку

Без повторных символов

medium
Сегодня вы поймёте, что такое интеграл в математике
Сегодня вы поймёте, что такое интеграл в математике

(и в программировании)

medium
Тёмная тема на сайте: второй этап
Тёмная тема на сайте: второй этап

Сохраняем тему и добавляем переключатель

medium
Что означает ошибка SyntaxError: 'break' outside loop
Что означает ошибка SyntaxError: 'break' outside loop

Это значит, что мы пытаемся выйти из цикла, которого нет

easy
Что означает ошибка ReferenceError: Cannot access uninitialized variable
Что означает ошибка ReferenceError: Cannot access uninitialized variable

Любопытная ошибка, которая находится совсем в другом месте

easy
Вкладываете условия в условия? Это для вас
easy
Ещё больше полезных CSS-команд
Ещё больше полезных CSS-команд

Короткие и мощные.

hard
easy