9. Palindrome Number

Leetcode 问题: 9. Palindrome Number

题目

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward.

For example, 121 is a palindrome while 123 is not.

传入正负整数 n,判断是否为 Palindrome 整数 ,如果是的话回传 true,不是的话回传 false

Example

Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

演算法

1. 负正数因为有「- 负数符号」,所以都没办法变成 Palindrome 整数

-xxx 裡面的负号只有一个,所以一定无法找到成对的 - 负号

所以 负整数 一定不是 Palindrome 整数

2. 取得最左右边数字进行比较

取得左边数字

要取得最左边数字,必须除以刚好小于那个数字的最大 10 的次方数字,再无条件捨去

数字 最左边数字 运算 divider 分母
11 1 Math.floor(11 / 10) 无条件捨去 10
121 1 Math.floor(121 / 100) 无条件捨去 100
1221 1 Math.floor(1221 / 1000) 无条件捨去 1000
12321 1 Math.floor(12321 / 10000) 无条件捨去 10000

所以 divider 分母1 开始 乘以10,直到刚好小于数字即可

取得右边数字

要取得最右边数字,必须mod % 10,取 10 的馀数

数字 最左边数字 运算
11 1 11 % 10
121 1 121 % 10
1221 1 1221 % 10
12321 1 12321 % 10

比较左右的数字,如果是一样的话,就可能为 Palindrome 整数,所以继续比较

如果不一样,则不是 Palindrome 整数

3. 计算下一个要比较的数字

去除左边数字

将原本的数字 mod % divider 分母,即可将最左边方数字去除

数字 去除左边数字后的数字 运算 divider 分母
11 1 11 % 10 10
121 21 121 % 100 100
1221 221 1221 % 1000 1000
12321 2321 12321 % 10000 10000

去除右边数字

将原本去除左边数字后的结果除以 10,并无条件捨去,就可以将最右边数字去除

去除左边数字后的数字 去除左右边数字后的数字 运算
1 0 Math.floor(1 / 10) 无条件捨去
21 2 Math.floor(21 / 10) 无条件捨去
221 22 Math.floor(221 / 10) 无条件捨去
2321 232 Math.floor(2321 / 10) 无条件捨去

记得要先去除左边再去除右边,避免数字去除发生错误

然后去除完左右边数字后,就可以在继续比较左右边的数字是否相同,直到比较的数字为 0 找不到可以再 比较的数字了

答案

JavaScript

TypeScript

function isPalindrome(checkNumber: number): boolean {
    if (checkNumber < 0) {
        // 负数都会有「- 负数符号」,所以都没办法变成 Palindrome 整数
        return false;
    }

    // 取得计算左侧数字 divider 分母
    let divider = 1;
    while (checkNumber >= divider * 10) {
        // 假如分母 * 10 还是小于原本数字,表示分母还可以继续加
        divider *= 10;
    }


    while (checkNumber) {
        // 右侧数字
        let rightDigit = checkNumber % 10;
        // 左侧数字
        let leftDigit = Math.floor(checkNumber / divider);

        if (leftDigit != rightDigit) {
            // 假如数字不相同,表示这个不是 Palindrome 整数
            return false;
        }

        // 取得下一个要检查的整数,去除原数字的左右数字
        // 取馀数:去除最左边数字
        checkNumber = checkNumber % divider;
        // 除以 10:去除最右边数字
        checkNumber = Math.floor(checkNumber / 10);
        // 取得去除左右数字后,下一个检查的分母
        divider = divider / 100;
    }

    return true;
};

参考资料