前言

先按难度往下走，因为数据结构还没理清。

参考

~~c++ string：~~

~~length —— 返回字符串长度~~
~~size —— 返回字符串长度~~

~~注意：strlen是以char*去计算字符串长度直到‘\0’结束，本题用不到。~~

c++ vector:

size —— 获取vector容器元素个数
operator[] —— 类似数组根据下标返回元素值

正文

回文数

c++给到的代码框架：

class Solution {
public:
    bool isPalindrome(int x) {

    }
};

bool型函数，返回true或false即可

根据现有条件可以排除x<10的情况，因为个位数不可能存在回文现象，而两位数的10也不存在，负数更不用说，多了个-号；故此首先判断x<10，如果成立直接返回false；

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 10){
            return false;
        }else{
            
        }
    }
};

接下来就是要拆开x去判断是否为回文数字,题目进阶思想是不使用将整数转换成字符串。先用最低级暴力去解题试试看。

初解

字符串这里肯定不能用char了，因为不知道长度，所以得用str接着，让x每次%10，然后让str+=x%10;

注意：这里有个问题就是，int类型无法直接+=给string类型，网上是有一些不同版本特性诞生的函数可以操作，但是这样对于算法的鲁棒性就很差了
所以字符串应该是不可取的，至于题目进阶反而提示的是不使用整数转换成字符串我就不是很了解了，等我做完看看评论大哥怎么做的。

在上述不考虑string的情况下，我们如何让一个int类型还能做到拆分成像数组一样呢？其实就是老朋友vector了。

我们可以通过while转换:

vector<int> v;
while(x > 0){
    v.push_back(x%10);
    x /= 10;
}

即x倒置了一遍

然后根据vector自带的size方法，先获取元素个数

1	int len = v.size();

然后首尾之间判断肯定是通过两个for循环了，但是需要统计一下，为什么这么说呢，因为我是把长度/2来算，一个i从=0 < len/2; 一个j = len-1 > len/2; 这样首尾一判断也还行。故此代码：

int num = 0;
for(int i = 0; i < len/2; i++){
    for(int j = len-1; j > len/2; j--){
        if(v[i] == v[j])
            num++;
    }
}

然后最后在判断一些num是否=len/2，这样就证明了有几组数字是相同的。

提一嘴的就是，leetcode是要求函数必须返回一个值，所以我们直接在if完之后的return还不行。要定义一个bool flag；

在东拼西凑之后，代码如下：

class Solution {
public:
    bool isPalindrome(int x) {

        bool flag = false;
 
        if( x < 10){
            flag = false;
        }else{
            vector<int> v;
            int num = 0;

            while(x > 0){
                v.push_back(x%10);
                x /= 10;
            }
            int len= v.size();
            for(int i = 0; i < len/2; i++){
                for(int j = len-1; j > len/2; j--){
                    if(v[i] == v[j])
                        num++;
                }
            }
            if(num == len/2)
                flag = true;
 
        }
           return flag;
    }
};

测试了几个案例之后我们提交一下看看：

我直呼好家伙！！！！！
0居然算回文啊，那个位数其实都算了吧？
我直呼好家伙！！！！！
这么重要的东西不在示例里面。。靠，不过没事，

我们修改一下if(x < 0)就可以了：

class Solution {
public:
    bool isPalindrome(int x) {

        bool flag = false;
 
        if( x < 0){
            flag = false;
        }else{
            vector<int> v;
            int num = 0;

            while(x > 0){
                v.push_back(x%10);
                x /= 10;
            }
            int len= v.size();
            for(int i = 0; i < len/2; i++){
                for(int j = len-1; j > len/2; j--){
                    if(v[i] == v[j])
                        num++;
                }
            }
            if(num == len/2)
                flag = true;
 
        }
           return flag;
    }
};

再提交一次：

额，这就很尴尬了，简单测试了一下，发现是我的思路出问题了，因为我拆成两份算的时候考虑的是这个数是奇数位数而不是偶数位数……
调整的时候注意到一个问题。。预期对半算，不如直接i和len算

for(int i = 0; i < len; i++){
    if(v[i] == v[len-i])
        num++;
}

先测试一下。。发现还是有点问题，就是因为len是元素个数，但是实际上vector[]重载跟数组一下都是从0开始，这就导致len得先-1，放在循环里反而不合适了。所以对上面的len=size的时候就-1，这代码就跟屎山一样现在堆积在一起。测了一下，0不起作用，其他都行了，因为我while的时候判断条件就是x>0，所以就很扯淡。这里直接用elseif套过去先，看看能不能通过。合并之后的代码：

class Solution {
public:
    bool isPalindrome(int x) {

        bool flag = false;
 
        if( x < 0){
            flag = false;
        }else if( x == 0 ){
            flag = true;
        }else{
            vector<int> v;
            int num = 0;

            while(x > 0){
                v.push_back(x%10);
                x /= 10;
            }
            int len= v.size()-1;
            for(int i = 0; i < len; i++){
                if(v[i] == v[len-i])
                    num++;
            }
            if(num == len)
                flag = true;
 
        }
           return flag;
    }
};

通过是通过了，但是这个时间和空间效率真的惨不忍睹，这大概就是陷进去了。不过在用while拆解x的时候突然想到一个点。在后面优化一下看看。

优化

回望屎山，满目鄙夷之色。。。。hhh,真的是人太菜。

回归正题，在将x不断%10拆解的时候，我那会就在想，如果用一个变量=x%10+变量*10，这样的话，例如x=121的时候，我创建一个变量n；

n = 121%10 + n*10，此时n = 1;
然后将x/10，再重复上步骤,
n = 12%10 + n*10; 这个时候n = 12;
在x/10重复,
n = 1%10 + n*10; n = 121;

这样直接if(n == x)好像就完事了。

0-9结果都一样，也不用再加什么elseif了。

浓缩后的代码：

class Solution {
public:
    bool isPalindrome(int x) {

        bool flag = false;
        int n = 0;

        while(x > 0){
            n = x%10 + n*10;
            x /= 10;
        }
        if(x == n)
            flag = true;

        return flag;
    }
};

然后测试了一下。。发现好像就0是对的，又看了几遍看出了点门道。。我的x被我一直/10，后面变成0了。。。。难怪if(x == n)怎么没变化。。，

找个变量先复制x的值就行了。

class Solution {
public:
    bool isPalindrome(int x) {

        bool flag = false;
        int n = 0;
        int y = x;

        while(x > 0){
            n = x%10 + n*10;
            x /= 10;
        }
        if(y == n)
            flag = true;

        return flag;
    }
};

决定命运的时刻来了，提交看看：

额，真是坎坷啊，它提示好像溢出了，也是哦，题目提示的范围是-2³¹ <= x <= 2³¹ - 1,
那也就是说要把n的类型改成long int应该就行了。

class Solution {
public:
    bool isPalindrome(int x) {

        bool flag = false;
        long int n = 0;
        int y = x;

        while(x > 0){
            n = x%10 + n*10;
            x /= 10;
        }
        if(y == n)
            flag = true;

        return flag;
    }
};

最后执行效率：

时间好像挺叼的了，空间拉不满应该是我用了long int的问题，不过最后还是取决与服务器之间的联系吧，多测一下好像最好的内存占用也是5.6mb，然后时间会从0ms-12ms浮动，不知道是不是网络波动的问题。

结语

不得不感慨。。有的时候屎山写着写着找到金子了好像。。

去看了看评论。第一条就是对题目的批评：

也难怪。。毕竟这个回文数没想到会这么大。。利用*10往上推是会出现这样的问题。

然后就是感觉能稍微优化一下空间和省略一个if哎，评论里大多都是直接return n==x这样，这样雀食省了我定义一个bool变量。

class Solution {
public:
    bool isPalindrome(int x) {
        long int n = 0;
        int y = x;

        while(x > 0){
            n = x%10 + n*10;
            x /= 10;
        }

        return y == n;
    }
};