9.回文数

判断一个数是否是回文数：

1. 负数不是回文
2. 如何取一个数的第一个数字和最后一个数字
3. 是否需要考虑中间数为0的情况
4. 考虑这个数有奇数位个数还是偶数位

不成熟的小办法

我写的程序的主要逻辑是，取x的第一个和最后一个数字进行比对，如果相同则继续向下取，不同则停止返回false，否则返回true。
遇到的困难就是2，我想的方法是求出这个数的长度，比如121，用121/100，但是这里还涉及到取10^3。
同时取剩下的x的时候用(x-b-temp)/10的方法，但是当中间的数为0的时候，减出来的数往往就是个负数了。

然后这个程序就在1221和1001中摇摆不定，我很讨厌纠结在这种小细节中出不来，所以一定是我的大逻辑哪里出了错。调试了多个test case之后发现根源还是在于x=(x-b-a*temp)/10，当剩下的数以0开头的时候，就像字符串变成了数值，比如10021，按照我这种做法就是x=2，然后按照我的判断逻辑，这个数是回文数，显然错误。

贴一下我愚蠢笨重的代码以勉励自己。

 bool isPalindrome(int x) {
if(x<0)
{return false;}
//求出数的长度
int len = length(x);
//求出x的第一个和最后一个数字

if(len>1)//这里加这个判断是为了防止temp除数为0
{
    int temp=pow(10,length(x)-1);
    int a=x/temp;
    int b=x%10;
    if((x-b-a*temp)!=0)
    {x=(x-b-a*temp)/10;}///////////////////////////////////
    else x=0;


    while(a==b&&(x!=0))
    {
        if(len >1)
        {
            int temp=pow(10,length(x)-1);
            int a=x/temp;
            int b=x%10;
            if((x-b-temp)!=0)
            {x=(x-b-a*temp)/10;}
            else x=0;
        } 
        else return true;
    }
    if(x==0&&a==b) //这里要加a==b
        return true;
    else return false;
}

else 
    return true;
}	

int length(int x)
{
    int i=0;
    while(x!=0)
    {
        x=x/10;
        i++;
    }
    return i;
}
int pow(int a,int b)//写这个pow函数注意返回的结果初始化，不能用a*=a
{
    int re=1;
for(int i=0;i<b;i++)
{
   re=re*a;
}
return re;
}

当你的大逻辑不对的时候，所能做的只能是根据test case修修补补。所以我准备直接看正确答案了。

正确答案

思路

1. 第一种想法是把数变成字符串，然后逐个匹配，但是这会用到额外的空间。
2. 我们把这个数逆序，看和之前的数是否一致。进一步想，我们只需要逆序这个数的一半进行比较就可以了。比如1221，我们只需要逆序后面的21和前面的12进行比较。

算法

public bool IsPalindrome(int x) {
    if(x < 0 || (x % 10 == 0 && x != 0)) {
        return false;
    }
    
    int revertedNumber = 0;
    while(x > revertedNumber) {
        revertedNumber = revertedNumber * 10 + x % 10;
        x /= 10;
    }

    return x == revertedNumber || x == revertedNumber/10;
}

来看一下这个程序是如何满足上面的条件的：

1. 首先是对特殊情况的处理：这里包括两种情况，一种是负数，一种是结尾为0但是开头不为0（比如10，运行到最后revertedNumber=1,x=0,返回true）。
2. 这里不考虑如何取第一个数，而是将整个数分成两半进行对比。当你拿到后面一半的时候，自然剩下前一半。
3. 因为上面已经处理了结尾为0的情况，所以这里r=r*10+x%10不存在转化之后为0的情况
4. 最后返回return x == revertedNumber || x == revertedNumber/10;保证了不管基数偶数都能适用。
5. 最后这个判断什么时候终止呢，当x>revertedNumber的时候。

真理往往都是简洁的。