leetcode 9、回文數（C/C++/JAVA/python）

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;
}
           

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;
    }
};
           

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;
    }
}

           

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
           

python參考網址