leetcode 9、回文数（C/C++/JAVA/python）_先计算出两个正整数 a+b 的结果 sum,然后要判断 sum 是不是回文数。 回文数:设 n

PS：算法并非原创，仅用于记录个人学习，侵删。

题目详情

算法分析：
个人的算法思路：
1、将整数转化为字符串，然后将字符串倒置，两个字符串进行比较。
2、将整数转化为字符串，然后用首尾两个指针进行字符逐个对比
（本文中的python实现）
之后阅读了前辈们的算法实现，又发现了其他满足进阶要求的算法思路：
1、将整数拆分存入整型数组，然后双指针比较
（本文中的C实现）
2、将整数颠倒得到一个新的数据，比较两者是否相等
（本文中的C++实现）
3、将整数的后半段颠倒，判断是不是和前半段相等，如果相等则是回文序列
（本文中的java实现）

代码实现：
【C】

/*
主要思路是拆分数字，将得到的数字存储为整型数组，然后双指针进行比较
*/
bool isPalindrome(int x) {
    if(x<0){//是负数
        return false;
    }
    //当x是正整数时，
    int count=0;//表示长度
    int y=x;//y为x的一份复制
    while(y){//计算整数的长度
        count++;
        y/=10;
    }
    int* temp=(int*)malloc(sizeof(int)*count);//临时数组，用来存数字
    int k=0;
    while(x){
        int cc=x%10;//x的个位
        temp[k]=cc;//存入temp[k]数组，
        k++;
        x/=10;//x截取个位，得到新的数
    }
    for(int i=0;i<k/2;i++){//类似于双指针，前后两个元素比较
        if(temp[i]!=temp[k-1-i]){
            return false;
        }
    }
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

C语言参考实现

【C++】

/*
C++的思路：将整数颠倒过来，但是不必先转化为字符串，而是直接进行整数的颠倒和比较
*/
class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) //负数不为回文数
            return false;
        else if(x == 0) //0为回文数
            return true;
        long a = 0; //转换时可能存在数组溢出的情况，所以需要长整型存储
        int temp = x;
        while(temp){
            a = a*10 + temp%10;
            temp = temp / 10;
        }
        if(a == x)//比较两个整数
            return true;
        else
            return false;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

C++参考网址

【java】

/*
java的思想比起C++的算法更加简洁，不需要颠倒全部的数组，而是只需要颠倒后半段，利用颠倒过程中原始数据的不断截断，最终比较两半是不是相同
*/
class Solution{
    public boolean isPalindrome(int x) {
    	//负数和以0结尾且非0的数显然不是回文数
        if(x<0||(x%10==0&&x!=0)) {
        	return false;
        }
        int reverseNum=0;//颠倒的后半段数据
        while(x>reverseNum){//只需要颠倒一半的数据
        	reverseNum = reverseNum*10+x%10;
        	x = x/10;//x截取个位
        }
        //如果x是奇数，直接x/10去掉中间那个数
        return x==reverseNum||x==reverseNum/10;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

JAVA参考网址

【python】

#python算法思路：
##转化为字符串，再进行双指针
class Solution:
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        if x<0:#x是负数
            return False
        s=str(x)#将x转为字符串
        for i in range(0,len(s)//2):#进行双指针处理
            if s[i]!=s[len(s)-1-i]:
                return False
        return True
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

python参考网址