Palindrome Number

Q: Является ли отрицательное число палиндромом?

Нет. Если читать в обратном порядке, -121 превращается в 121- , и у знака минус нет соответствующего символа на другом конце. Поэтому для каждого отрицательного целого числа возвращается false .

Q: Какова временная сложность задачи проверки числа на палиндром?

Оба подхода работают за время O(log x) , потому что число x содержит примерно log10(x) цифр, и каждая обрабатывается один раз. Строковый подход использует дополнительную память O(log x) для текста; разворот половины числа использует O(1) .

ЛегкоМатематика и моделирование

+10

Число является палиндромом, если его цифры читаются одинаково слева направо и справа налево, например 1221. Для целого числа x верните true, если оно является палиндромом, и false в противном случае. Отрицательное число никогда не считается палиндромом, потому что у знака минус нет пары на другом конце.

Функция

isPalindrome(x: integer) → boolean

xinteger: целое число для проверки, возможно отрицательное
Возвращаетboolean: истина, если x читается одинаково в обоих направлениях, иначе ложь

Ограничения

-2³¹ ≤ x ≤ 2³¹-1
Для любого отрицательного числа возвращается false.

Примеры

Ввод: x = 121
Вывод: true
Пояснение: Если читать в обратном порядке, 121 всё ещё остаётся 121, поэтому ответ — true.

Ввод: x = -121
Вывод: false
Пояснение: Если прочитать в обратном порядке, -121 превращается в 121-, а это другой текст, поэтому ответ — false.

Дополнительный вопрос

Сможешь решить это, не преобразуя целое число в строку?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Число является палиндромом, если оно равно числу, записанному в обратном порядке. Если представить его как текст, достаточно одного сравнения. Без преобразования в текст восстановление всего числа в обратном порядке может привести к переполнению, поэтому разверните только вторую половину цифр и сравните её с первой половиной.

Сравните строку с её перевёрнутой версией

Идея

Запишите число в виде текста и сравните его с числом, записанным в обратном порядке. Для отрицательных чисел не нужен отдельный случай: -121 начинается со знака минус и заканчивается цифрой, поэтому оно никогда не будет равно числу, записанному в обратном порядке: 121-.

В тексте по одному символу на каждую цифру — примерно log10(x) символов и не более 11 в данном случае. Цена — дополнительная строка.

Алгоритм

Преобразуйте x в строку s.
Разверните s.
Верните результат проверки, равна ли s своей перевёрнутой версии.

def isPalindrome(x):
    s = str(x)
    # A minus sign sits only at the front, so a negative never matches its reverse.
    return s == s[::-1]

Перевернутая половина числа

Идея

x % 10 возвращает последнюю цифру, а целочисленное деление на 10 удаляет её. Перемещение цифр с конца x в другое число half формирует обратную последовательность из удалённых цифр. Остановись, когда half станет не меньше оставшейся части x: это означает, что ты взял половину цифр. После этого для 1221 получаем x = 12 и half = 12 — палиндром. При нечётном количестве цифр в half также окажется средняя цифра: после этого для 12321 получаем x = 12 и half = 123, поэтому нужно сравнить x с half / 10.

До цикла обработай два случая. Отрицательное число никогда не бывает палиндромом. Число, оканчивающееся на 0, должно было бы начинаться с 0, а это возможно только для самого числа 0. Без этой проверки 10 после обработки даст x = 0 и half = 1, и проверка x == half / 10 ошибочно пройдёт. Значение half никогда не превысит 6 цифр, поэтому поместится в целочисленный тип любого размера.

Алгоритм

Если x отрицательное или оканчивается на 0 и не равно 0, верните false.
Установите half = 0.
Пока x > half, установите half = half * 10 + x % 10 и разделите x на 10 с целочисленным делением.
Верните true, если x == half (чётное количество цифр) или x == half / 10 (нечётное количество цифр).

def isPalindrome(x):
    if x < 0:
        return False
    original, reversed_num = x, 0
    while x > 0:
        reversed_num = reversed_num * 10 + x % 10
        x //= 10
    return original == reversed_num

Ловушки и крайние случаи

Забывать о отрицательных числах. В языках, где остаток сохраняет знак, обращение -121 дает -121, и проверка проходит. В Python, где -1 // 10 равно -1, цикл while x != 0 никогда не заканчивается.
Не отклонять числа, оканчивающиеся на 0. Тогда обращение половины числа принимает 10. Само число 0 является палиндромом.
Обращать все число, используя 32-битное целое число. Обращенное число 2147483647 не помещается.
Использовать / там, где язык выполняет деление с получением дроби. Используйте Math.floor(x / 10) в JavaScript, // в Python, %/% в R и ~/ в Dart.
Сравнивать полное обращенное число с x после того, как цикл изменил x. Сохраните копию исходного числа.

Частые вопросы3

Является ли отрицательное число палиндромом?

Нет. Если читать в обратном порядке, -121 превращается в 121-, и у знака минус нет соответствующего символа на другом конце. Поэтому для каждого отрицательного целого числа возвращается false.

Зачем переворачивать только половину числа?

При обращении порядка всех цифр может произойти переполнение 32-битного целого числа: число, полученное обращением 2147483647, больше максимального значения int. Половина цифр всегда помещается, и цикл выполняет половину работы.

Какова временная сложность задачи проверки числа на палиндром?

Оба подхода работают за время O(log x), потому что число x содержит примерно log10(x) цифр, и каждая обрабатывается один раз. Строковый подход использует дополнительную память O(log x) для текста; разворот половины числа использует O(1).

def isPalindrome(x):
    # Напишите код здесь

Тест #1

Тест #2

Аргумент

x = 121

Ожидаемый вывод

true