题目

Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

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

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

解法：模拟

转化成字符串来做
时间复杂度O(n)，空间复杂度O(n)

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        string s = to_string(x);
        for (int i = 0, j = s.size() - 1; i < j; i++, j--) {
            if (s[i] != s[j]) return false;
        }
        return true;
    }
};

直接反转数字比较是否相等
时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0) return false;
        int y = x;
        long long r = 0;
        while (x) {
            r = r * 10 + x % 10;
            x /= 10;
        }
        return r == y;
    }
};

边反转边比较
时间复杂度O(n)，空间复杂度O(1)

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0 || x && x % 10 == 0) return false;
        int s = 0;
        while (s <= x) {
            s = s * 10 + x % 10;
            if (s == x || s == x / 10) return true;
            x /= 10;
        }
        return false;
    }
};