9. Palindrome Number

Условие задачи

Нужно определить, является ли данное целое число палиндромом.
Палиндром — это число, которое читается одинаково слева направо и справа налево.

Примеры:

• 121 → палиндром, так как при чтении справа налево снова получится 121
• -121 → не палиндром, так как при чтении справа налево будет 121-
• 10 → не палиндром, так как при чтении справа налево получится 01, что не равно 10

Формально задача звучит так:

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

Решения через преобразование числа в строку

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

Решение 1: сравнение с развернутой строкой

Идея

1. Преобразовать число в строку.
2. Развернуть строку.
3. Сравнить исходную строку и её развернутую версию.

import (
    "strconv"
)
 
func reverseASCII(s string) string {
    b := []byte(s)
    for i, j := 0, len(b)-1; i < j; i, j = i+1, j-1 {
        b[i], b[j] = b[j], b[i]
    }
    return string(b)
}
 
func isPalindrome(x int) bool {
    xs := strconv.Itoa(x)
    xr := reverseASCII(xs)
    return xs == xr
}

Решение 2: посимвольное сравнение

Идея

1. Преобразовать число в строку.
2. Сравнивать символы с начала и конца строки, двигаясь к центру.
3. Если все пары совпали — число палиндром.

import (
    "strconv"
)
 
func isPalindromeString(s string) bool {
    for i, j := 0, len(s) - 1; i < j; {
        if s[i] != s[j] {
            return false
        }
        i++
        j--
    }
    return true
}
 
func isPalindrome(x int) bool {
    xs := strconv.Itoa(x)
    return isPalindromeString(xs)
}

Решение без строкового преобразования

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

Идея

• Отрицательные числа сразу исключаются (они не могут быть палиндромами из-за знака).
• Последовательно «разворачиваем» число, формируя новую переменную, куда записываются цифры в обратном порядке.
• Чтобы не разворачивать число целиком (и не рисковать переполнением), достаточно разворачивать только половину числа и сравнивать её с оставшейся половиной.

Алгоритм

1. Если x < 0 или число оканчивается на 0, но само не равно 0, то это не палиндром.
2. Разворачиваем число справа налево, пока обратная половина не станет больше или равна оставшейся половине.
3. Проверяем два случая:
   • для чётного количества цифр обе половины должны быть равны;
   • для нечётного количества цифр обратная половина без последней цифры должна быть равна оставшейся.

func isPalindrome(x int) bool {
    if x < 0 || (x % 10 == 0 && x != 0) {
        return false
    }
 
    reversed := 0
    for x > reversed {
        reversed = reversed * 10 + x % 10
        x /= 10
    }
 
    return x == reversed || x == reversed/10
}

Объяснение

• В цикле мы «переворачиваем» только половину числа: например, для 1221 в итоге x = 12, reversed = 12.
• Для нечётной длины, например 12321, получится x = 12, reversed = 123. Здесь последняя цифра 3 не влияет, поэтому сравниваем x с reversed/10. Такое решение работает за O(log10(n)) по времени и O(1) по памяти.