iT邦幫忙

2024 iThome 鐵人賽

0
佛心分享-刷題不只是刷題

刷經典 LeetCode 題目系列 第 57

經典LeetCode 9. Palindrome Number

  • 分享至 

  • xImage
  •  

這道題主要是判斷一個整數是否是回文數字。回文數字是指正著讀和反著讀都相同的數字。

題目:
給定一個整數 x,判斷它是否是回文數字。如果一個數字是負數,它不會是回文數字。例如,-121 不是回文數字,因為反過來後是 121-。如果一個正數是回文數字,那麼它正向和反向的數字排列應該相同。

範例:

輸入: 121
輸出: true

輸入: -121
輸出: false

輸入: 10
輸出: false

解題思路

解法1:整個數字反轉

回文的話反轉後跟原本數字應該相同,

reverse 改用 long,是因為考慮到有很大的數字會乘法溢位,例如 x = 1234567899,

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        if (x % 10 == 0 && x != 0)
            return false;

        int num = x;
        long reverse = 0;
        while (num != 0) {
            int digit = num % 10;
            reverse = reverse * 10 + digit;
            num = num / 10;
        }

        if (reverse == x)
            return true;
        else
            return false;
    }
};

時間複雜度:O(log n),因為每次迴圈減少一個十進位數字。
空間複雜度:O(1)

解法2:stack 先進後出特性

用 stack 先進後出特性,然後藉此判斷是否為回文,

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        if (x % 10 == 0 && x != 0)
            return false;

        int num = x;
        stack<int> stk;
        while (num != 0) {
            stk.push(num % 10);
            num = num / 10;
        }

        num = x;
        while (num != 0) {
            if (stk.top() != num % 10)
                return false;
            stk.pop();
            num = num / 10;
        }

        return true;
    }
};

時間複雜度:O(n)
空間複雜度:O(n)

解法3 只反轉一半

class Solution {
public:
    bool isPalindrome(int x) {
        if (x < 0)
            return false;
        if (x % 10 == 0 && x != 0)
            return false;
        
        int num = x;
        long reversedHalf = 0;
        while (num > reversedHalf) {
            int digit = num % 10;
            reversedHalf = reversedHalf * 10 + digit;
            num = num / 10;
        }

        if (num == reversedHalf || num == reversedHalf / 10)
            return true;
        else
            return false;
    }
};

時間複雜度:O(log n),因為每次迴圈減少一個十進位數字。
空間複雜度:O(1)

參考:
#9. Palindrome Number


上一篇
經典LeetCode 234. Palindrome Linked List
下一篇
經典LeetCode 13. Roman to Integer
系列文
刷經典 LeetCode 題目80
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言