题目
判断一个整数是否是回文数. 回文数是指正序 (从左向右) 和倒序 (从右到左) 读都是一样的整数.
示例 1:
输入: 121
输出: true
示例 2:
输入:-121
输出: false
解释: 从左向右读, 为 -121 . 从右向左读, 为 121- . 因此它不是一个回文数.
示例 3:
输入: 10
输出: false
思路 1: 反转比较法
回文数有一个特性, 就是它翻转后值是一样的. 所以我们可以先将其反转, 然后比较反转数和原数是否相等.
代码
- public class Solution {
- public boolean isPalindrome(int x) {
- long reverse = 0, original = x;
- if(x<0){
- return false;
- }
- while(x>0){
- reverse *= 10;
- reverse += x % 10;
- x /= 10;
- }
- return original == reverse;
- }
- }
思路 2: 诸位比较法
反转比较有可能会溢出, 但我们遍历每一位的时候其实并不用保存上一位的信息, 只要和当前对应位相等就行了. 所以我们可以遍历一遍先算出数的长度, 再遍历一遍同时对比前后的对应位.
代码
- public class Solution {
- public boolean isPalindrome(int x) {
- if(x <0){
- return false;
- }
- int digits = 1;
- int original = x;
- // 计算当前数的位数, 个位数不用计算, 已经默认为 1
- while(x> 9){
- digits *= 10;
- x /= 10;
- }
- // 逐位比较
- x = original;
- while(x> 0){
- int msd = x / digits;
- int lsd = x % 10;
- if(msd != lsd){
- return false;
- }
- // 去除最高位和最低位
- x -= msd * digits;
- x /= 10;
- digits /= 100;
- }
- return true;
- }
- }
来源: http://www.jianshu.com/p/69a669fccc7b