Problem
Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.
Example 1:
Input: 121 Output: true
Example 2:
Input: -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: 10 Output: false Explanation: Reads 01 from right to left. Therefore it is not a palindrome.
Follow up:
Could you solve it without converting the integer to a string?
Solution 1: Convert to string (cheating)
Time complexity: O(log10(x))
Space complexity: O(log10(x))
C++
|
1 2 3 4 5 6 7 8 |
// Author: Huahua class Solution { public: bool isPalindrome(int x) { string s = to_string(x); return s == string(rbegin(s), rend(s)); } }; |
Solution 2: Digit by Digit
Every time we compare the first and last digits of x, if they are not the same, return false. Otherwise, remove first and last digit and continue this process.
How can we achieve that via int math?
e.g. x = 9999, t = pow((10, int)log10(x)) = 1000
first digit: x / t, last digit: x % 10
then x = (x – x / t * t) / 10 removes first and last digits.
t /= 100 since we removed two digits.
x / t = 9 = 9 = x % 10, 9999 => 99
9 = 9, 99 => “”
Time complexity: O(log10(x) / 2)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
// Author: Huahua class Solution { public: bool isPalindrome(int x) { if (x < 0) return false; int d = static_cast<int>(log10(x) + 1); int t = pow(10, d - 1); for (int i = 0; i < d / 2; ++i) { if (x / t != x % 10) return false; x = (x - x / t * t) / 10; t /= 100; } return true; } }; |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment