#9. Palindrome Number

題目描述

給你一個整數x，如果x是一個回文，回傳true，反之則回傳false。

限制條件

-2^31 <= x <= 2^31 - 1

解題思路

Integer to String

要比對整數中的每個數字的話，最直覺的方式是將整數轉換為字串，再進行比對。

public class Solution { 
	public bool IsPalindrome(int x) {
        if(x<0) return false;
        var strx = x.ToString();
        int start = 0;
        int end = strx.Length-1;
        while(start<end){
            if(strx[start]!=strx[end]) return false;
            start++;
            end--;
        }
        return true;
    }
}

複雜度分析：

時間複雜度：時間複雜度為O(n)，n等於x的位數(字串轉換)+x一半的位數(檢查回文)。
空間複雜度：空間複雜度為O(n)，n等於x的位數。

Follow-up

你可以不將整數轉為字串來解決這個問題嗎？

Integer to Array

我們可以把所有的個位數存到陣列裡面，然後按照陣列的順序來檢查是不是回文。

public class Solution { 
	public bool IsPalindrome(int x) {
        if(x<0) return false;
        List<int> l = new List<int>();
        while(x!=0){
            l.Add(x%10);
            x/=10;
        }
        int left=0;
        int right=l.Count-1;
        while(left<=right){
            if(l[left]!=l[right])return false;
            left++;
            right--;
        }
        return true;
    }
}

複雜度分析：

時間複雜度：時間複雜度為O(n)，n等於x的位數+x一半的位數(檢查回文)。
空間複雜度：空間複雜度為O(n)，n等於x的位數。

學習重點

Array