LeetCode_#9_回文数 Palindrome Number_C++题解

9. 回文数 palindrome number

题目描述

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.
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

example 3:

input: 10
output: false

explanation: reads 01 from right to left. therefore it is not a palindrome.
解释: 从右向左读, 为 01 。因此它不是一个回文数。

follow up 进阶

coud you solve it without converting the integer to a string?

你能不将整数转为字符串来解决这个问题吗？

自解_string

class solution {
public:
    bool ispalindrome(int x) {
        if (x < 0) return false;
        string ori = to_string(x);
        for (int i = 0; i < ori.length() / 2 + 1; i++){
            if (ori[i] != ori[ori.length()-i-1])
                return false;
        }
        return true;
    }
};

• int转string在c++11中增加了全局函数to_string来支持

  参考：c++ int与string的相互转换(含源码实现)

• 需要额外的非常量空间来创建问题描述中所不允许的字符串。

自解_long

class solution {
public:
    bool ispalindrome(int x) {
        if (x < 0) return false;
        int ori = x;
        long long rev = 0;
        while (x > 0){
            rev = rev * 10 + x % 10;
            x = x / 10;
        }
        return rev == ori? true : false;
    }
};

参考官方题解_翻转一半

class solution {
public:
    bool ispalindrome(int x) {
        if (x < 0 || (x % 10 == 0 && x != 0)) return false;
        int rev = 0;
        while (x > rev){
            rev = rev * 10 + x % 10;
            x = x / 10;
        }
        return rev == x || rev / 10 == x;
    }
};

反转后的数字大于int_max时，将遇到整数溢出问题。考虑只反转 int 数字的一半，如果该数字是回文，其后半部分反转后应该与原始数字的前半部分相同。

• 反转后半部分的数字的方法与第7题基本一致，当原始数字小于反转后的数字时，就意味着我们已经处理了一半位数的数字。
• 处理特殊情况：x < 0；数字的最后一位是 0，第一位数字也是 0 的只有 0 满足
• 当数字长度为奇数时，由于处于中位的数字不影响回文（它总是与自己相等），可以通过 rev / 10 将其去除。

各种情况验证

• 数字长度为奇数时，最后循环结束一定为 rev 比 x 多一位，由 rev / 10 == x 进行回文判断
• 数字长度为偶数时，当循环到rev与x位数相等时
  • 若 x > rev，此时 x 不是回文，但符合循环条件继续进入循环，使得 rev 较 x 多两位，由 rev == x 与 rev / 10 == x 进行回文判断， 均不成立，判断正确
  • 若 x <= rev，跳出循环，二者位数相等，由 rev == x 进行回文判断