题目链接：https://oj.leetcode.com/problems/palindrome-number/

 

问题：Determine whether an integer is a palindrome. Do this without extra space.

 

针对本题可能存在的疑惑

1）负数是否属于回文（例如-1）？

暂定负数不为回文。

 

解题思路：

方法一：

1）将输入数字表示成字符串

缺点：违法不能运用额外条件的限制

1     public boolean isPalindrome(int x){ 2         if(x < 0){ 3             return false; 4         } 5         String num = String.valueOf(x); 6         int i = 0; 7         int j = num.length() - 1; 8         while(i < j){ 9             if(num.charAt(i) != num.charAt(j)){10                 return false;11             };12             i++;13             j--;14         }15         return true;16     }

时间复杂度：O(N)，空间复杂度：O(N)

 

方法二：

1）将输入数字逆转

2）将 逆转后的数字与原数字进行对比，是否相同

缺点：若反转后的数字发生溢出将发生错误

1     public boolean isPalindrome(int x){ 2         if(x < 0){ 3             return false; 4         } 5         int reverse = reverse(x); 6         if(reverse == x){ 7             return true; 8         } 9         return false;10     }11     12     private int reverse(int num){13         int result = 0;14         while(num != 0){15             result = result * 10 + num % 10;16             num /= 10;17         }18         return result;19     }

时间复杂度：O(N)，空间复杂度：O(1)

 

方法三：

从最头和最尾开始，依此向中间进行比较：

若比较的两个数不同，返回false

若比较的两个数相同，去除头尾数字，继续比较 

1 public boolean isPalindrome(int x){ 2         if(x < 0){ 3             return false; 4         } 5         int div = 1; 6         while(x / div >= 10){ 7             div *= 10; 8         } 9         while(x!=0){10             int l = x / div;11             int r = x % 10;12             if(l != r){13                 return false;14             }15             x = (x % div) / 10;16             div /= 100;17         }18         return true;19     }

时间复杂度：O(N)，空间复杂度：O(1)