【LeetCode刷题记录】9. Palindrome Number

发表于
字数统计: 396 字 | 阅读时长 ≈ 2 分钟

Description:

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

这道题目实现并不难，但题目要求空间复杂度为O(1), 有一定的技巧性。

Solutions:

Solution 1:

1
2
3
4
5
6
7
8
9
public boolean isPalindrome(int x) {
        int palindromeX = 0;
        int inputX = x;
        while(x>0){
            palindromeX = palindromeX*10 + (x % 10);
            x = x/10;
        }
        return palindromeX==inputX;	
    }

受到LeetCode 7.Reverse Integer 的启发，将原int型的数据完全反转后，比较反转后的数据与原数据是否相同，相同则为回文，反之不是。

Question：这个算法没有考虑到int型数据反转后可能存在的溢出情况，是不是有错误？
Answer: 若反转后的数据比原数据大，那么它一定与原数据不相同，肯定不是回文了，所以这个算法隐性地排除了溢出的情况。

但进一步思考，判断是否为回文需要将整个数字完全反转吗？反转到一半不久可以进行比较了吗？这就引出了Solution 2。

Solution 2:

1
2
3
4
5
6
7
8
9
10
bool isPalindrome(int x) {
        if(x<0|| (x!=0 &&x%10==0)) return false;
        int sum=0;
        while(x>sum)
        {
            sum = sum*10+x%10;
            x = x/10;
        }
        return (x==sum)||(x==sum/10);
    }

这个算法要额外考虑能被10整除的数，需要特别注意。

Solution 3:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool isPalindrome(int x) {
          //negative number
          if(x < 0)
              return false;
              
          int len = 1;
         while(x / len >= 10)
             len *= 10;
             
         while(x > 0) {  
             //get the head and tail number
             int left = x / len;
             int right = x % 10;
             
             if(left != right)
                 return false;
             else{
                 //remove the head and tail number
                 x = (x % len) / 10;
                 len /= 100;
             }
         }       
         return true;
     }

解题思路： 每次提取头尾两个数，判断它们是否相等，判断后去掉头尾两个数。