LeetCode 9. 回文数

LeetCode 9. 回文数

  啊，笔者的期末考试终于结束了，火速进行一个码的学。

---

题目描述

题目链接：点我做题

思路 思路1：暴力解法

  我考虑用一个数组把这个传进来的数的每一位从低到高放到数组里，然后进行一个双指针法，left和right进行比较。

  有小伙伴可能就要问题，为什么不直接把每一位取出来后，以数组结尾为个位，以数组倒数第二位为十位，一次类推重新组合成一个int和原数做比较呢？问题就在于重新组合出来的数可能超过INT_MAX.

  我们通过观察题例可以发现，负数一定不是回文数，因为’-'也参与了回文过程，但是没有数字等于‘-’；同样的，个位是0的数一定不是回文数，因为最高位不可能为0.

class Solution {
public:
    bool isPalindrome(int x) 
    {
        if (x < 0 || x % 10 == 0)
        {
            return false;
        }
        int n = 1;
        vector tmp(10);
        //这里开10个是因为看传进来的是int intmax最多是十位。
        while (x != 0)
        {
            tmp[n - 1] = x % 10;
            x = x / 10;
            n++;
        }
        int left = 0;
        int right = n - 2;
        while (left < right)
        {
            if (tmp[left] != tmp[right])
            {
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
};

思路2：转化为字符串求解

  为什么用C++刷题，它内置了一些函数，比如可以把整数转化为字符串的函数std::to_string函数，它的原型如下：

std::string to_string(int value); (1) (C++11起) 
std::string to_string(long value); (2) (C++11起) 
std::string to_string(long long value); (3) (C++11起) 
std::string to_string(unsigned value); (4) (C++11起) 
std::string to_string(unsigned long value); (5) (C++11起) 
std::string to_string(unsigned long long value); (6) (C++11起) 
std::string to_string(float value); (7) (C++11起) 
std::string to_string(double value); (8) (C++11起) 
std::string to_string(long double value); (9) (C++11起)

  转化为字符串了，然后就可以调用reverse函数，这个函数可以把容器中的字符串翻转过来，然后翻转后的字符串和原字符串比较就得出结果了。

class Solution {
public:
    bool isPalindrome(int x) 
    {
        string tmp1 = to_string(x);
        reverse(tmp1.begin(), tmp1.end());
        return tmp1 == to_string(x);
    }
};

思路3：翻转一半的数字

  这个解法非常神奇，我们把整数的后一半翻转形成一个int，

• 如果位数是偶数，当为回文数的时候，翻转后的形成的int和原数的前半部分相等；当不是回文数的时候，翻转后形成的int一定和原数不等
• 如果位数是奇数，如12321，我们可以翻转后5/2+1位，形成一个123，原数的前半部分是12,123/10就得到了12,12==12,12321是回文数

  怎样控制翻转一半呢？当翻转形成的值大于等于原数剩下的值时，说明就已经翻转1半了，因此，在位数是奇数的情况下，就会翻转位数/2+1位。

class Solution {
public:
    bool isPalindrome(int x) 
    {
        //翻转一半的数字 
        //考虑到回文数字是后面一半翻转过来和前面一半相等就行 
        //并且这是充要条件
        
        //先是一些边界条件
        if (x == 0)
        {
            return true;
        }
        if (x < 0 || x % 10 == 0)
        {
            return false;
        }
        //怎么控制现在已经翻转一半了呢 
        //只要翻转过来的数字大于等于前面数字就行
        int halfreversenum = 0;
        while (x > halfreversenum)
        {
            halfreversenum = 10 * halfreversenum + x % 10;
            x /= 10;
        }
        //如果是偶数 那么后一半翻转的数字应该和剩下的一般数字相等
        //如果是奇数 那么后一半翻转过来形成的数字和剩下的数字不相等
        //但是后一半翻转过来形成的数字整除10和前一半数字相等
        //如12321 后一半翻转123 整除10 12 
        return halfreversenum == x || 
        halfreversenum / 10 == x;
    }
}