LeetCode之整數反轉（7）、字元串轉換整數（8）、回文數（9）

1、整數反轉（7）

題目描述：

題目連結

題解一:利用字元串反轉

• 整數—>字元串—>反轉
• 注意反轉後溢出範圍的判斷

class Solution:
    def reverse(self, x: int) -> int:
        if -10<x<10:
            return x
        str_x=str(x)
        if str_x[0] != "-":
            str_x=str_x[::-1]
            x=int(str_x)
        else:
            str_x=str_x[:0:-1]
            x=int(str_x)
            x=-x
        return x if -(1<<31) < x < ((1<<31)-1) else 0
        # return x if -2147483648 < x < 2147483647 else 0 這個時間少點
           

• 由于計算機是基于二進制的，是以原理是二進制操作的左移

  1<<31

  比

  2**31

  快一點

題解二：數學解法

• 求餘得末尾數字，末尾數字依次乘10，相加

思路

• 以12345為例，先拿到5，再拿到4，之後是3，2，1，我們按這樣的順序就可以反向拼接處一個數字了，也就能達到 反轉 的效果。怎麼拿末尾數字呢？好辦，用取模運算就可以了

• 1、将12345 % 10 得到5，之後将12345 / 10

  2、将1234 % 10 得到4，再将1234 / 10

  3、将123 % 10 得到3，再将123 / 10

  4、将12 % 10 得到2，再将12 / 10

  5、将1 % 10 得到1，再将1 / 10

• 正負數的判斷，我們可以将x取絕對值命名為y，暫時忽略正負數的差別，然後作上述操作，循環的判斷條件應該是while(y!=0)，無論正數還是負數，按照上面不斷的/10這樣的操作，最後都會變成0，是以判斷終止條件就是

  !=0

• 溢出範圍的判斷：
  • 假設有1147483649這個數字，它是小于最大的32位整數2147483647的，但是将這個數字反轉過來後就變成了9463847411，這就比最大的32位整數還要大了，這樣的數字是沒法存到int裡面的，是以肯定要傳回0(溢出了)。是以，每次反轉後，我們可以判斷其是否溢出，若溢出直接傳回0.
  • 那麼反轉後的數字最大是多少，才不會溢出呢？
  • 由于最大數字是 2147483647，如果反轉後數字大于 214748364那後面就不用再判斷了，肯定溢出了；如果某個數字等于 214748364呢，這對應到下圖中第三、第四、第五排的數字，需要要跟最大數的末尾數字比較，如果這個數字比7還大，說明溢出了。

class Solution:
    def reverse(self, x: int) -> int:
        y,res=abs(x),0
        while y!=0:
            #每次取末尾數字
            tmp=y%10
            if res>214748364 or (res==214748364 and tmp>7):
                return 0
            res=res*10+tmp
            y//=10
        return res if x>0 else -res
           

• 時間複雜度： O ( log ⁡ n ) O(\log n) O(logn)
• 空間複雜度： O ( 1 ) O(1) O(1)。

2、字元串轉換整數（8）

題目描述：

題目連結

題解一： 正常周遊

• 根據轉換規則，我們先去掉空格，然後判斷是否有正負号，利用flag标記，最後開始比對數字并将數字記錄在ans裡面，并結合flag傳回值；

class Solution:
    def myAtoi(self, s: str) -> int:
        i=0
        n=len(s)
        while i<n and s[i]==' ':
            i+=1
        if n==0 or i==n:
            return 0
        flag=1
        if s[i]=='-':
            flag=-1
        if s[i]=='+' or s[i]=='-':
            i+=1
        int_min=-1<<31
        int_max=(1<<31)-1
        ans=0
        while i<n and '0'<=s[i]<='9':
            ans=ans*10+int(s[i])
            i+=1
            if ans-1>int_max:
                break
        ans=ans*flag
        if ans>int_max:
            return int_max
        return int_min if ans<int_min else ans

           

題解二：有限狀态機

• 正常周遊的方法隻是适用于分支讨論較少的情況，不然代碼就會顯得很備援，也很難思考
• 而有限狀态機的關鍵在于我們的程式在每個時刻有一個狀态 s，每次從序列中輸入一個字元 c，并根據字元 c 轉移到下一個狀态 s’。這樣，我們隻需要建立一個覆寫所有情況的從 s 與 c 映射到 s’ 的表格即可解決題目中的問題

• 這種方法這要确定好了狀态就可以解決複雜的字元串問題，無論是在題目改成要求找多組數字或者是加入其他判斷條件

  下面是官方圖給的狀态

• 題目定義4狀态，每種狀态遇到空格，符号，數字、其他又會轉入不同的狀态

INT_MAX = (1 << 31) - 1
INT_MIN = -1 << 31
#定義自動機即有限狀态機
class Automaton:
    def __init__(self):
        self.state = 'start'
        self.sign = 1
        self.ans = 0
        self.table = {
            'start': ['start', 'signed', 'in_number', 'end'],
            'signed': ['end', 'end', 'in_number', 'end'],
            'in_number': ['end', 'end', 'in_number', 'end'],
            'end': ['end', 'end', 'end', 'end'],
        }
    #定義狀态轉移趨勢    
    def get_col(self, c):
        if c.isspace():
            return 0
        if c == '+' or c == '-':
            return 1
        if c.isdigit():
            return 2
        return 3
    #定義狀态
    def get(self, c):
        self.state = self.table[self.state][self.get_col(c)]
        if self.state == 'in_number':
            self.ans = self.ans * 10 + int(c)
            self.ans = min(self.ans, INT_MAX) if self.sign == 1 else min(self.ans, -INT_MIN)
        elif self.state == 'signed':
            self.sign = 1 if c == '+' else -1

class Solution:
    def myAtoi(self, s: str) -> int:
        auto = Automaton()
        for c in s:
            auto.get(c)
        return auto.sign * auto.ans
           

• 時間複雜度 O ( n ) O(n) O(n)，
• 空間複雜度 O ( 1 ) O(1) O(1)

題解三：正規表達式

• 正規表達式通常被用來測試字元串内的模式、替換那些符合某個模式的文本、基于模式比對從字元串中提取子字元串。
• 對于本題，這裡我們如果應用正規表達式把數字那一串提取出來再進行處理就簡單多了
• 正規表達式元字元
• python正規表達式中group

class Solution:
    def myAtoi(self, s: str) -> int:
        import re
        mathes=re.match('[ ]*([+-]?\d+)',s)
        if not mathes:
            return 0
        ans=int(mathes.group(1))
        return min(max(ans,-1<<31),(1<<31)-1)
           

• 時間複雜度 O ( n ) O(n) O(n)，
• 空間複雜度 O ( 1 ) O(1) O(1)

3、回文數（9）

題目描述：

題目連結

題解一：利用字元串做反轉

• 整數—>字元串—>反轉—>判斷與之前的字元串是否一緻

• 當x小于0時，肯定不是一個回文數，直接傳回false

class Solution:
    def isPalindrome(self, x: int) -> bool:
        str_x=str(x)
        if str_x[0]=="-":
            return False
        else:
            return str_x==str_x[::-1]
           

• 時間複雜度： O ( n ) O(n) O(n)
• 空間複雜度： O ( n ) O(n) O(n)

題解二：反轉一半數字

• 由于回文數具有對稱性的特點，是以我們隻需要反轉後面一半的數字，與前面一半的數字判斷是否一緻即可

思路：

• 首先，考慮一些臨界情況：所有負數都不可能是回文；除了 0 以外，所有個位是 0 的數字不可能是回文，因為最高位不等于 0。是以我們可以對所有小于0，大于 0 且個位是 0 的數字傳回 false。

• 反轉後半部分的數字

  對于數字 1221，如果執行 1221 % 10，我們将得到最後一位數字 1，要得到倒數第二位數字，我們可以先通過除以 10 把最後一位數字從 1221 中移除，1221 / 10 = 122，再求出上一步結果除以 10 的餘數，122 % 10 = 2，就可以得到倒數第二位數字。如果我們把最後一位數字乘以 10，再加上倒數第二位數字，1 * 10 + 2 = 12，就得到了我們想要的反轉後的數字。如果繼續這個過程，我們将得到更多位數的反轉數字。

  現在的問題是，我們如何知道反轉數字的位數已經達到原始數字位數的一半？

  由于整個過程我們不斷将原始數字除以 10，然後給反轉後的數字乘上 10，是以，當原始數字小于或等于反轉後的數字時，就意味着我們已經處理了一半位數的數字了。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        if x<0 or (x!=0 and x%10==0):
            return False
        elif x==0:
            return True
        else:
            reverse_x=0
            while x>reverse_x:
                tmp=x%10
                reverse_x=reverse_x*10+tmp
                x//=10
            return reverse_x==x or reverse_x //10==x
           

• 時間複雜度： O ( log ⁡ n ) O(\log n) O(logn)，對于每次疊代，我們會将輸入除以 10，是以時間複雜度為 O(\log n)O(logn)。
• 空間複雜度： O ( 1 ) O(1) O(1)。我們隻需要常數空間存放若幹變量。