LeetCode 9. 回文数

题目

• 难度：简单
• 题型分类：数学、数字反转
• 题目链接：回文数

给定整数x，判断其是否为回文数，是则返回true，否则返回false。

回文数是指从左向右和从右向左读都相同的整数。

进阶：不将整数转换为字符串来解决。

示例

输入：x = 121 输出：true 输入：x = -121 输出：false 解释：负号导致正反读取不同。 输入：x = 10 输出：false 解释：反向读取为 01，与原数不同。

数据范围

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

解题思路

只反转数字的后半部分，避免反转整个整数可能产生的溢出。

1. 负数不是回文数；除0外，末位为0的整数也不是回文数。
2. 不断取出x的末位，追加到revertedNumber，同时删除x的末位。
3. 当x <= revertedNumber时停止：
   • 偶数位：判断x == revertedNumber，例如1221最后两者均为12。
   • 奇数位：判断x == revertedNumber / 10，忽略中间一位，例如12321最后分别为12和123。

0不会进入循环，最终判断为回文数。

• 时间复杂度：O(d)，其中d为整数的十进制位数。
• 空间复杂度：O(1)

Java

classSolution{publicbooleanisPalindrome(intx){if(x<0||(x%10==0&&x!=0)){returnfalse;}intrevertedNumber=0;while(x>revertedNumber){revertedNumber=revertedNumber*10+x%10;x/=10;}returnx==revertedNumber||x==revertedNumber/10;}}

C++

classSolution{public:boolisPalindrome(intx){if(x<0||(x%10==0&&x!=0)){returnfalse;}intrevertedNumber=0;while(x>revertedNumber){revertedNumber=revertedNumber*10+x%10;x/=10;}returnx==revertedNumber||x==revertedNumber/10;}};

Python 3

classSolution:defisPalindrome(self,x:int)->bool:ifx<0or(x%10==0andx!=0):returnFalserevertedNumber=0whilex>revertedNumber:revertedNumber=revertedNumber*10+x%10x//=10returnx==revertedNumberorx==revertedNumber//10