9. Palindrome Number

Задача

Задача на Палиндром

Дано целое число x . Верните true , если x является палиндромом, и false в противном случае.

Пример 1:

Вход: x = 121
Выход: true
Объяснение: 121 читается как 121 слева направо и справа налево.

Пример 2:

Вход: x = -121
Выход: false
Объяснение: Слева направо читается как -121. Справа налево становится 121-. Следовательно, это не палиндром.

Пример 3:

Вход: x = 10
Выход: false
Объяснение: Читается как 01 справа налево. Следовательно, это не палиндром.

Примеры

Пример 1

Input: x = 121
Output: true

Пояснение

121 читается одинаково слева направо и справа налево.

Пример 2

Input: x = -121
Output: false

Пояснение

Слева направо: -121, справа налево: 121-. Не палиндром.

Пример 3

Input: x = 10
Output: false

Пояснение

Справа налево читается как 01. Не палиндром.

Решение

Решение

// Временная сложность: O(log x)
//   Почему log x?
//   В цикле while мы на каждой итерации делим входное число на 10 (temp = Math.floor(temp / 10)).
//   Это означает, что количество итераций равно количеству цифр в числе.
//   
//   Количество цифр в числе x пропорционально log10(x).
//   Например:
//   x = 100    -> 3 цифры -> 3 итерации (~ log10(100) = 2)
//   x = 10000  -> 5 цифр  -> 5 итераций (~ log10(10000) = 4)
//   
//   Поэтому сложность растет логарифмически относительно значения самого числа.
// Пространственная сложность: O(1)
 
var isPalindrome = function(x) {
    if (x < 0) return false;
 
    let reversed = 0; // Сюда будем собирать перевернутое число
    let temp = x; // Копия числа, которую будем "разрушать" в цикле
 
    // Цикл работает, пока в числе temp есть цифры (пока оно больше 0)
    while (temp > 0) {
 
        // ШАГ 1: Получаем последнюю цифру
        // Оператор % 10 возвращает остаток от деления на 10.
        // Для 123: 123 / 10 = 12 целых и 3 в остатке. digit = 3.
        const lastDigit = temp % 10;
 
        // ШАГ 2: "Освобождаем место" и добавляем цифру в reversed
        // Умножая reversed на 10, мы сдвигаем все его цифры влево,
        // освобождая разряд единиц для новой цифры.
        // Было 0, стало 0*10 + 3 = 3.
        // На след. шаге: было 3, станет 3*10 + 2 = 32.
        reversed = reversed * 10 + lastDigit;
 
        // ШАГ 3: Отрезаем последнюю цифру от temp
        // Делим на 10 и округляем вниз, чтобы убрать дробную часть.
        // 123 / 10 = 12.3 -> Math.floor -> 12.
        // Мы физически уменьшили число, убрав последнюю цифру.
        temp = Math.floor(temp / 10);
    }
 
    // Сравниваем исходное число с перевернутым
    return x === reversed;
};

Решение 2 (мое)

// Временная сложность: O(n)
// Пространственная сложность: O(n)
 
var isPalindrome = function(x) {
    if (x < 0) return false;
    if (x < 10) return true;
 
    const str = x.toString().split('').reverse().join('');
 
    return x / str === 1;
};