回文数是指正序(从左向右)和倒序(从右向左)读都一样的整数。例如,121、1221、13531等都是回文数,而-121、10、25等则不是回文数。
判断一个整数是否是回文数的算法可以有多种实现方式,以下是几种常见的算法:
196算法
随意找一个十进制的数,把它倒过来成另一个数,再把这两个数相加,得一个和数。
将这个和数倒过来,与原来的和数相加,又得到一个新的和数。
照此方法,一步步接续往下算,直到出现一个“回文数”为n。
反转比较法
将整数反转,然后判断反转后的数字是否等于原数字。
具体实现中,可以将整数转换为字符串,然后使用双指针法从字符串首尾开始成对比较。
数学方法
通过数学计算来判断一个数是否为回文数。例如,对于一个n位数,可以通过计算其前半部分和后半部分的回文数个数来确定该数是否为回文数。
位操作法
利用位操作来判断一个数是否为回文数。例如,可以通过异或操作来判断一个数的每一位是否与其对应的反向位相等。
```java
public class PalindromeNumber {
public static boolean isPalindrome(int x) {
if (x < 0) {
return false;
}
int revertedNumber = 0;
while (x != 0) {
revertedNumber = revertedNumber * 10 + x % 10;
x /= 10;
}
return x == revertedNumber || x == revertedNumber / 10;
}
public static void main(String[] args) {
System.out.println(isPalindrome(121)); // true
System.out.println(isPalindrome(-121)); // false
System.out.println(isPalindrome(10)); // false
}
}
```
这个算法的时间复杂度是O(log10(n)),因为每次循环都会将n除以10。