| leetcode

LeetCode笔记-PalindromeNumber

回文数

  • “Determine whether an integer is a palindrome. Do this without extra space.”
  • 回文数指的是首尾对称，正着念反着念都一样的数字。
  • 不能用额外的空间，所以不能用string。

解法一

  • 将数字整个反过来，如果和原来的数字相等则为回文数
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    class Solution {
        public:
            bool isPalindrome(int x) {
                int a = x, r = 0;
                if (a < 0) return false;
                for (;a;) {
                    // 检测溢出
                    // if (a < (INT_MAX - x % 10) / 10) return 0;  
                    r = r * 10 + a % 10;
                    a = a / 10;
                }
                return r == x;
            }
        };

解法二

  • 每次取数字的最高位和最低位，比比看是不是相等，再把这两位丢掉继续比剩下的，直到x为0;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public:
        bool isPalindrome(int x) {
            int a = x, h = 1;
            if (a < 0) return false;
            while (a / h >= 10) {
                h = h * 10;
            }
            while (a > 0) {
                if (a / h != a % 10) return false;
                a = a % h;
                a = a / 10;
                h = h / 100;
            }
            return true;
        }
    };

比较

  • 解法一：~150ms, 解法二: ~80ms