Программирование

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

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

Опубликовано

3 недели назад

22.08.2024

Автор:

AppTractor

Задача

Палиндром на LeetCode: https://leetcode.com/problems/palindrome-number/

Решение

Для решения задачи проверки, является ли число палиндромом, можно воспользоваться следующим подходом.

Алгоритм:

Если число отрицательное, сразу вернуть false, так как отрицательные числа не могут быть палиндромами (из-за знака минус).
Преобразуем число в строку.
Проверим, является ли эта строка равной самой себе, записанной в обратном порядке.
Если равны — число палиндром, возвращаем true. Если нет — false.

class Solution {
    func isPalindrome(_ x: Int) -> Bool {

    if x < 0 {
        return false
    }
    
    // Преобразуем число в строку
    let str = String(x)
    
    // Сравниваем строку с её обратной версией
    return str == String(str.reversed())

    }
}

Временная сложность алгоритма O(n), где n — количество цифр в числе.

Такое решение и работает медленно, и потребляет много памяти.

Другое решение

Конечно, существует несколько подходов для проверки, является ли число палиндромом, без преобразования его в строку. Один из таких подходов заключается в том, чтобы обратить число и сравнить его с исходным числом.

Алгоритм:

Если число отрицательное или заканчивается на 0 (и при этом не является нулем), оно не может быть палиндромом, поэтому сразу возвращаем false.
Инициализируем переменную для хранения перевернутого числа (начинаем с 0).
Извлекаем последнюю цифру числа и добавляем ее к перевернутому числу.
Уменьшаем исходное число, удаляя его последнюю цифру.
Повторяем шаги 3-4 до тех пор, пока исходное число не станет меньше или равно перевернутому числу.
Если исходное число равно перевернутому числу или перевернутое число равно исходному числу без последней цифры (это важно для чисел с нечетным количеством цифр), возвращаем true. В противном случае — false.

class Solution {
    func isPalindrome(_ x: Int) -> Bool {

    // Отрицательные числа и числа, которые заканчиваются на 0 (кроме самого 0), не являются палиндромами
    if x < 0 || (x % 10 == 0 && x != 0) {
        return false
    }
    
    var original = x
    var reversed = 0
    
    while original > reversed {
        let lastDigit = original % 10
        reversed = reversed * 10 + lastDigit
        original /= 10
    }
    
    // Число является палиндромом, если оригинальная часть равна перевернутой,
    // или если оригинальная часть равна перевернутой без последней цифры (для нечетных чисел)
    return original == reversed || original == reversed / 10

    }
}

В этом методе мы постепенно разворачиваем число, строя новое число, состоящее из цифр оригинального числа в обратном порядке.
Мы сравниваем только половину числа, чтобы избежать переполнения и уменьшить вычислительную нагрузку.
Если исходное число имеет нечетное количество цифр, после половины итераций перевернутое число будет больше оставшейся части оригинального числа. В этом случае мы удаляем последнюю цифру из перевернутого числа (с помощью reversed/10) и сравниваем.

Этот метод более эффективен и работает за время O(log₁₀(x)), поскольку количество итераций пропорционально количеству цифр в числе. К тому же он не использует «дорогие строки», а оперирует лишь целыми числами. Такое решение попадает в топ по быстродействию, однако по памяти опережает только половину других решений.

Можно было бы избавиться от одной переменной (original)? однако в таком случае компилятор выдает ошибку: «‘x’ is a ‘let’ constant in solution.swift».

Третье решение

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

Алгоритм:

Если число отрицательное или заканчивается на 0 (и не является самим 0), сразу возвращаем false.
Определяем количество цифр в числе.
Извлекаем первую и последнюю цифры числа и сравниваем их.
Если первая и последняя цифры совпадают, удаляем их и продолжаем проверку со следующей парой цифр.
Повторяем шаги 3-4 до тех пор, пока не проверим все пары цифр.
Если все пары совпали, возвращаем true, иначе false.

func isPalindrome(_ x: Int) -> Bool {
    // Отрицательные числа и числа, заканчивающиеся на 0 (кроме самого 0), не являются палиндромами
    if x < 0 || (x % 10 == 0 && x != 0) {
        return false
    }
    
    // Определяем количество цифр в числе
    var divisor = 1
    while x / divisor >= 10 {
        divisor *= 10
    }
    
    var original = x
    
    // Сравниваем цифры, начиная с самой левой и самой правой
    while original > 0 {
        let left = original / divisor  // Самая левая цифра
        let right = original % 10      // Самая правая цифра
        
        // Если не совпадают, число не палиндром
        if left != right {
            return false
        }
        
        // Удаляем самую левую и самую правую цифры
        original = (original % divisor) / 10
        
        // Уменьшаем делитель на 2 порядка, так как убрали 2 цифры
        divisor /= 100
    }
    
    return true
}

// Пример использования:
let x1 = 1221
print(isPalindrome(x1))  // Выведет true

let x2 = 12321
print(isPalindrome(x2))  // Выведет true

let x3 = 123
print(isPalindrome(x3))  // Выведет false

divisor помогает определить, какая цифра является самой левой. Например, для числа 12321 начальное значение divisor будет 10000.
В каждом цикле мы сравниваем самую левую и самую правую цифры. Если они совпадают, мы отбрасываем их и продолжаем сравнение.
Если все пары цифр совпадают, число является палиндромом.

Этот метод также имеет временную сложность O(log₁₀(x)), так как количество шагов пропорционально количеству цифр в числе. Однако он избегает работы с дополнительной памятью, требуемой для хранения строки или развернутого числа.