C++算法实践07-回文数

一、题目：

给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。

回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

例如，121 是回文，而 123 不是。

示例 1：输入：x = 121 输出：true

示例 2：输入：x = -121 输出：false 解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3：输入：x = 10 输出：false 解释：从右向左读, 为 01 。因此它不是一个回文数。

二、思路：

正常思路就是采用循环取出尾数，然后将数字翻转就可以进行比较原数字和翻转后的数字是否一样，最重要的是要注意翻转后的溢出问题，防止溢出的处理原理在文章C++算法实践06-整数反转详细说明。

第二种思路就是首先使用to_string函数将整型转换为字符串来处理，同样取出第一个字符为‘-’的话直接返回false即可。而后续定义了一个函数str_len用于返回双指针中间的元素个数，如果函数的返回值和原来字符串的长度一样就可以确定这个数是回文数。

三、代码：

1.常规解法：

class Solution 
{
public:
    bool isPalindrome(int x) 
    {
        //当x为负数时一定返回false
        if(x < 0)
        {
            return false;
        }
        int ret=0;
        int result=0;
        int guodu=x;
        while(guodu != 0)
        {
            ret = guodu % 10;
            if(result > 214748364 || (result == 214748364 && ret > 7))
            {
                return false;
            }
            result = result*10 + ret;
            guodu /= 10;
        }
        if(result == x)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

2.变换为字符串：

class Solution {
public:
    bool isPalindrome(int x) {
        std::string str = std::to_string(x);
        
        if (str[0] == '-') {
            return false; 
        }
        int len = str.length();
        int left = (len % 2 == 0) ? (len-1)/2 : len/2;
        int ret = str_len(str, left, len % 2 == 0 ? left+1 : left);
        
        return ret == len;
    }

    int str_len(std::string s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            --left;
            ++right;
        }
        return right - left - 1;
    }
};