LeetCode [9] Palindrome Number

9. Palindrome Number

Easy

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Follow up: Could you solve it without converting the integer to a string?

 

Example 1:

Input: x = 121
Output: true

Example 2:

Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Example 4:

Input: x = -101
Output: false

 

Constraints:

• -231 <= x <= 231 - 1 

Note:

• mthode1
• step1, compute the length
• step2, compare the digits from both sides
• method2: eg. isPalindrome(12321)

                   x=12321 y=12321
                   x=1232 y=12321
                   x=123 y=12321
                   x=12 y=12321
                   x=1 y=12321
                   x=0 y=12321
                   x=1 y=12321
                   x=12 y=1232
                   x=123 y=123
                   x=1232 y=12 
                   x=12321 y=1

• on the way down the recursion, each digit of "x" is exposed (ie., becomes the tail) in reverse order
• on the way back up, each digit of "y" is exposed orderly
• it seems the redundant comparisons are necessary since it has to reach the bottom of the recursions to expose all digits 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

class Solution { public: bool isPalindrome(int x) { if(x<0) return false; int w = 1; while(x/w/10){ w*= 10;} while(x){ int left = x/w; int right = x%10; if(left!=right) return false; x = x%w; x = x/10; w = w/100; } return true; } }; class Solution { public: bool isPalindrome(int x, int &y){ if(x==0) return true; if(isPalindrome(x/10, y) && x%10==y%10){ y /= 10; return true; }else{ return false; } } bool isPalindrome(int x) { if(x<0) return false; return isPalindrome(x, x); } }; class Solution { public: bool isPalindrome(int x) { string s = to_string(x); int n = s.size(), l = 0, r = n-1; while(l<r){ if(s[l++]!=s[r--]) return false; } return true; } };

1 2 3 4 5 6 7 8 9 10

class Solution { public boolean isPalindrome(int x) { String s = Integer.toString(x); int n = s.length(), l = 0, r = n-1; while(l<r){ if(s.charAt(l++)!=s.charAt(r--)) return false; } return true; } }