8. String to Integer (atoi)

Previous726. Number of Atoms Next12. Integer to Roman

Last updated 3 years ago

8. String to Integer (atoi)

這一個題目主要考察的並不是演算法與資料結構，考察的點在於是否可以冷靜地處理邊角案例，在面試中，給出的例子可能並不多，要看看在面試的人是否有辦法清楚的了解題目在幹嘛。

面試官可能就會只貼出下面的例子，並要我們寫出一個程式碼來做轉換，但是千萬不能夠馬上跳進去寫！

"420" -> 420
"-420" -> -420
"420 hello world" -> 420
"hello world 420" -> 0
"    -420   " -> -420

不管怎麼樣，要先從給出的這些例子，看看我們可以觀察出什麼事情

如果給定的字串就是一串數字，那結果就會是一串數字，範例中有包含了兩種情況，但是這樣是不夠的：
1. 字串為正整數 -> 直接變成正整數
2. 字串為負整數 -> 直接變成負整數
3. 如果整數前面有正號呢？ +420 ？要問到面試官回答你：420
4. **如果是浮點數呢？**要問到面試官回答你：只需要取整數的部分，不用四捨五入，正負號的取法和上面一樣。
5. 如果說數字前面有很多 0 呢？00420 要問到面試官回答你：410
第二種情況，那就是數字和文字同時出現的情況，範例中包含了兩種情況，但是這樣還是不夠的：
1. 題目的開始就是數字，後面所有的文字都捨棄
2. 題目的開始就是文字，後面的就算有數字也回傳回零
3. 如果是數字在文字中間呢？要問到面試官回答，視同 2-2
4. 如果說有兩串文字出現呢？例如：420 710 hello world 要問到面試官回答到只要取第一個就好。（這個題目也可以在第一大類情況的時候問，不過我放在這裡是因為，我其實就是到這裡才想到這個例子的，想要表達的是，不用緊張，慢慢的推敲題目，比起寫到一半才發現是這樣，那會悲劇）
5. 其他可以一起在這裡確認的就是如果整個字串都沒有數字，那**基礎情況（Base case）**是什麼？要問到面試官回到 0
第三種情況，這個題目有可能會有很多的空白，和第二種情況不一樣的是，如果說在合法的字元前面有非常多的空白，都是可以忽略不計的，當問到這裡的時候，就可以比較清楚知道題目的規則了。
1. 如果是 42 0 那這樣是 420 還是 42 ？要問到面試官回答到 42
第四種情況，如果是空字串呢？那要問到面試官回答到答案是 0 。

以上是我自己會詢問問題的方式，這個過程看起來很長，但是如果沒有先搞懂這件事情，這個題目其實會變得很困難，這個題目以上的問題其實都可能可以換答案，例如題目可能可以從問一個數字面成一串數字...等，這些其他因素都會影響題目好不好做。

上面的這個推論，甚至可以用文字來表達他的大意，那就是我們要找到一串字串中「第一個的合法整數」，如果字串的開頭不是合法的整數或是正負號，表示此題目無解。

有了以上的情況，題目就不難了，LeetCode 的題目有額外給在正數或負數的情況，答案會怎麼影響，這和面試沒有什麼太大的關係。

class Solution:
    def myAtoi(self, s: str) -> int:
        # 空字串
        if len(s) == 0:
            return 0

        # 都是空白
        arr = list(s.strip())
        if len(arr) == 0:
            return 0
        
        # 先取正、負號
        sign = -1 if arr[0] == '-' else 1
        
        # 判斷要出發點
        i = 1 if arr[0] in ['+', '-'] else 0
        
        # 開始建構答案
        # 1. 如果遇到第一個不是數字的字元，while 就會停止
        # 2. 如果 while 連執行都沒有執行，那答案就是 0 
        res = 0
        while i < len(arr) and arr[i].isdigit():
            res = 10 * res + int(arr[i])
            i += 1
            
        
        # LeetCode 才有的條件，面試中可能不會被問到
        if sign == 1:
            return min(res, 2**31-1)
        else:
            return max(-res, -2**31)

Previous726. Number of Atoms Next12. Integer to Roman

Last updated 3 years ago

面試官可能就會只貼出下面的例子，並要我們寫出一個程式碼來做轉換，但是千萬不能夠馬上跳進去寫！

"420" -> 420
"-420" -> -420
"420 hello world" -> 420
"hello world 420" -> 0
"    -420   " -> -420

不管怎麼樣，要先從給出的這些例子，看看我們可以觀察出什麼事情

如果給定的字串就是一串數字，那結果就會是一串數字，範例中有包含了兩種情況，但是這樣是不夠的：
1. 字串為正整數 -> 直接變成正整數
2. 字串為負整數 -> 直接變成負整數
3. 如果整數前面有正號呢？ +420 ？要問到面試官回答你：420
4. **如果是浮點數呢？**要問到面試官回答你：只需要取整數的部分，不用四捨五入，正負號的取法和上面一樣。
5. 如果說數字前面有很多 0 呢？00420 要問到面試官回答你：410
第二種情況，那就是數字和文字同時出現的情況，範例中包含了兩種情況，但是這樣還是不夠的：
1. 題目的開始就是數字，後面所有的文字都捨棄
2. 題目的開始就是文字，後面的就算有數字也回傳回零
3. 如果是數字在文字中間呢？要問到面試官回答，視同 2-2
4. 如果說有兩串文字出現呢？例如：420 710 hello world 要問到面試官回答到只要取第一個就好。（這個題目也可以在第一大類情況的時候問，不過我放在這裡是因為，我其實就是到這裡才想到這個例子的，想要表達的是，不用緊張，慢慢的推敲題目，比起寫到一半才發現是這樣，那會悲劇）
5. 其他可以一起在這裡確認的就是如果整個字串都沒有數字，那**基礎情況（Base case）**是什麼？要問到面試官回到 0
第三種情況，這個題目有可能會有很多的空白，和第二種情況不一樣的是，如果說在合法的字元前面有非常多的空白，都是可以忽略不計的，當問到這裡的時候，就可以比較清楚知道題目的規則了。
1. 如果是 42 0 那這樣是 420 還是 42 ？要問到面試官回答到 42
第四種情況，如果是空字串呢？那要問到面試官回答到答案是 0 。

有了以上的情況，題目就不難了，LeetCode 的題目有額外給在正數或負數的情況，答案會怎麼影響，這和面試沒有什麼太大的關係。

class Solution:
    def myAtoi(self, s: str) -> int:
        # 空字串
        if len(s) == 0:
            return 0

        # 都是空白
        arr = list(s.strip())
        if len(arr) == 0:
            return 0
        
        # 先取正、負號
        sign = -1 if arr[0] == '-' else 1
        
        # 判斷要出發點
        i = 1 if arr[0] in ['+', '-'] else 0
        
        # 開始建構答案
        # 1. 如果遇到第一個不是數字的字元，while 就會停止
        # 2. 如果 while 連執行都沒有執行，那答案就是 0 
        res = 0
        while i < len(arr) and arr[i].isdigit():
            res = 10 * res + int(arr[i])
            i += 1
            
        
        # LeetCode 才有的條件，面試中可能不會被問到
        if sign == 1:
            return min(res, 2**31-1)
        else:
            return max(-res, -2**31)