Номер палиндрома LeetCode

Постановка задачи

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

Целое число является палиндромом, если оно читается одинаково как в прямом, так и в обратном направлении. Например, 121 является палиндромом, а 123 — нет.

Пример 1:

Input: x = 121
Output: true

Пример 2:

Input: x = -121 
Output: false

Пример 3:

Input: x = 10
Output: false

Пример 4:

Input: x = -101 
Output: false

Ограничения:

- -2^31 <= x <= 2^31 - 1

Объяснение

Как упоминалось в условии задачи, палиндромное число — это число, которое одинаково читается с обеих сторон.

Решение грубой силы

Решение грубой силы будет состоять в том, чтобы преобразовать целое число в строку, перевернуть строку и проверить, совпадают ли две строки.

Но этот подход потребует дополнительного места для создания строки.

Временная сложность этой программы будет O(N). Сложность пространства будет O(M), где M — количество цифр в целом числе.

Оптимизированное решение

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

Получить последнюю цифру очень просто, и мы можем использовать оператор модуля %. Получить первую цифру можно с помощью делителя.

Проверим алгоритм.

Алгоритм

- if x < 0 
  - return false. 
- set divisor = 1 
// We use the divisor to compute the number of digits in the number x.
// We keep multiplying the divisor by 10 till x / divisor is greater than equal to 10. 
- Loop while x / divisor >= 10 
  - divisor = divisor * 10 
- Loop while x != 0 
  // here we check if first and last digit are same or not. 
  - if x / divisor != x % 10 
    - return false 
    // remove the first digit 
    - set x = x % divisor 
    
    // remove the last digit 
    - set x = x / 10 
   // since first and last digit are removed we divide divisor by 100 
    - set divisor = divisor / 100 
- return true

Решение C++

class Solution {
public: 
    bool isPalindrome(int x) {
        if(x < 0){
            return false;
        }
        int divisor = 1;
        while(x/divisor >= 10){
            divisor *= 10;
        }
        while(x != 0){
            if (x / divisor != x % 10) {
                return false;
            }
            x %= divisor;
            x /= 10;
            divisor /= 100;
        }
        return true;
    }
};

Решение Golang

func isPalindrome(x int) bool {
    if x < 0 {
        return false
    }
    divisor := 1
   
    for x / divisor >= 10 {
        divisor *= 10
    }
    for x != 0 {
        if x / divisor != x % 10 {
            return false
        }
        x %= divisor
        x /= 10
        divisor /= 100
    }
    return true
}

Решение для JavaScript

var isPalindrome = function(x) {
    if( x < 0 ){
        return false;
    }
    let divisor = 1;
    while( x / divisor >= 10 ){
        divisor *= 10;
    }
    while( x != 0 ){
        if( Math.trunc(x / divisor) != Math.floor(x % 10) ){
            return false;
        }
        x %= divisor;
        x = Math.floor( x / 10 );
        divisor /= 100;
    }
    return true;
};

Давайте проверим наш алгоритм.

x = 12321 
Step 1: x < 0 
        12321 < 0 
        false 
Step 2: divisor = 1 
Step 3: while x / divisor >= 10
 
        1. 12321 / 1 >= 10 
           12321 >= 10 
           divisor *= 10 
           divisor = 10 
        2. 12321 / 10 >= 10 
           1232 >= 10 
           divisor *= 10 
           divisor = 100 
        3. 12321 / 100 >= 10 
           123 >= 10 
           divisor *= 10 
           divisor = 1000 
        4. 12321 / 1000 >= 10 
           12 >= 10 
           divisor *= 10 
           divisor = 10000 
        5. 12321 / 10000 >= 10 
           1 >= 10 
           Loop exit 
Step 4: while x != 0 
        
        1. 12321 / 10000 != 12321 % 10 
           1 != 1 
           false 
 
           x %= divisor 
           x = 12321 % 10000 
           x = 2321 
           x /= 10 
           x = 232 
           divisor /= 100 
           divisor = 100 
        2. 232 / 100 != 232 % 10 
           2 != 2 
           false 
           x %= divisor 
           x = 232 % 100 
           x = 32 
           x /= 10 
           x = 3 
           divisor /= 100 
           divisor = 1 
        3. 3 / 1 != 3 % 10 
           3 != 3 
           false 
           x %= divisor 
           x = 3 % 1 
           x = 0 
           x /= 10 
           x = 0 
           divisor /= 100 
           divisor = 0 
        4. x != 0 
           0 != 0 
           Loop exit 
Step 5: return true

Первоначально опубликовано на https://alkeshghorpade.me.