leetcode 9.回文数(整数不转成字符串)

9. 回文数

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

• 例如，121 是回文，而 123 不是。

示例 1：

输入：x = 121
输出：true

示例 2：

输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：

输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。

不将整数转为字符串来解决这个问题吗？

思路：

1. 如果整数为负数，则一定不是回文，因为负号不会出现在末尾。
2. 如果整数是0，则是回文。
3. 通过反转整数的一部分（例如右半部分）来检查是否和左半部分相等，而不需要将其转换为字符串。
4. 对于反转操作：
   • 逐步将数字从右到左反转。
   • 比较反转部分和剩余部分，如果相等，则是回文。

class Solution 
{
public:
    bool isPalindrome(int x) 
    {
        if (x < 0 || (x%10==0 && x!=0)) return false; 
        if (x == 0) return true; 

        int half = 0;
        while (x > half) 
        {
            half = half * 10 + x % 10;
            x /= 10;
        }

        return x == half || x == half / 10;
    }
};

代码解释:

1. 负数排除：

   • 如果输入是负数，直接返回 false，因为负号无法对称。
2. 除了 0 以外，所有个位是 0 的数字不可能是回文，因为最高位不等于 0。所以我们可以对所有大于 0 且个位是 0 的数字返回 false。

3. 反转右半部分数字：

   • reversedHalf 保存当前反转后的右半部分数字。
   • 每次通过 x % 10 获取数字的最后一位，并将其加入到 reversedHalf。
   • 使用 x /= 10 去掉原数字的最后一位。

4. 判断条件：

   • 如果数字长度是偶数，原数字左半部分和反转的右半部分应相等（x == reversedHalf）。
   • 如果数字长度是奇数，左半部分应该等于反转部分去掉最后一位（x == reversedHalf / 10）。