Eisen 筆記

#8. String to Integer (atoi)

題目描述

實作將字串轉換成32位元有符號整數的myAtoi(string s)函式(功能和C/C++的atoi類似)。

myAtoi(string s)的演算法規則如下：

  1. 忽略任何前置空白。
  2. 確認下一個字元(如果不是字串結尾)是否為'-'或'+'，如果是的話則讀取進來。這個字元會做為整數正負的判斷。假設沒有任何符號，則預設為正值。
  3. 讀取下一個字元直到沒有任何數字字元存在或者達到字串結尾。剩餘的其他字串則忽略。
  4. 轉換這些數字字元變成整數。如果沒有任何數字字元被讀取，則整數值為0。並且根據步驟2的結果轉換正負號。
  5. 如果整數超過32位元的範圍[-231, 231-1]，則限制整數的值，讓它保持在範圍內。明確的說，整數小於-231會被限制在-231，大於231-1則會被限制在231-1。
  6. 回傳整數作為答案。

注意：

  • 只有空格字元' '才會被判定是空白字元。
  • 不要忽略任字元除了前置空白以及數字字元後的剩餘字串。

限制條件

  1. 0 <= s.length <= 200
  2. 字串s由英文大小寫、數字字元(0-9)、' '、+、-、以及.所組成。

解題思路

這一題按照規則一步一步的處理就可以了，首先可以看到需要排除掉的字元為空白字元與數字後的剩餘字串，也就是說，去掉這兩個部分後，中間才是我們真正要處理的部分。

接著是正負號的部分，要注意的是字串可能會出現像是"+-1234"、"-+1234"這種輸入，題目中並沒有描述需要怎麼處理這種案例的規則，既然沒有提到，基本上我們會假設他不是符合規定的格式。

再來可能會出現這種"+ 1234"、"- 1234"在符號與數字之間多了空格，與上面的案例一樣，沒有提到代表他不是合規的格式。

接下來純數字的部分，可能出現的案例為"12 34"，這個案例其實和規則3是一樣的，數字字元後是非數字字元，因此忽略剩下的字串，因此這個案例的數值會是12。

到這裡字串格式的問題都解決了，接下來我們看到數值的問題。

數值的問題主要是正負號的數值與超過32位元極限這兩個。

正負號的數值因為分別是[-231,231-1]這兩個數字，在處理數值的時候並沒有先考慮到符號，因此如果以正值來處理數值的話在答案為-231的情況下，會因為在正值下處理而超過231-1因此被限制在231-1，接著加上符號後，就會變成-231-1，得到錯誤的答案，因此這邊最好是將數值以負值的方式來處理。

再來考慮到超過界線的案例，基本上只會遇到兩種情況，十位數溢位與個位數溢位，以下面的例子來說明

s = "21474836480"，這個案例剛好比231多的1位，我們在處理字元的時候，會先把單一字元轉換成個位數值，接著處理下一個字元時，會先將現在累積的數值*10，進位後再加上下一個字元轉換後的數值，但如果遇到進位後大於231的數值就會出錯，因此我們需要判定進位後是否會大於極限，簡單用等號左右互換得到條件式currVal > Int32.MaxValue/10，當條件式成立的時候代表數值進位時會溢位，因此可以直接知道答案等於極限值，另外注意要負值下處理，所以會是currVal < Int32.MinValue/10。

而個位數溢位的案例為s = "2147483649"，剛好比極限值多出1，同理條件式為currVal < Int32.MinValue + val的情況之下，若成立則代表數值會發生溢位，因此答案直接等於極限值。

最後當數值處理完後，加上正負號時，需要判斷如果數值等於Int32.MinValue但是符號為正時，數值應為231-1，其餘則按照結果回傳即可。

public class Solution {
    public int MyAtoi(string s) {
        int idx = 0;
        while(idx<s.Length && s[idx]==' ') idx++;        
        if(idx>=s.Length) return 0;
        
        bool positive = true;
        if(s[idx] == '-'){
            positive = false;
            idx++;
        }else if(s[idx] == '+'){
            idx++;
        }
        if(idx>=s.Length) return 0;
        
        if(!Char.IsNumber(s[idx])) return 0;
        int ans = 0;
        while(idx<s.Length && Char.IsNumber(s[idx])){
            if(ans< Int32.MinValue/10){
                ans = Int32.MinValue;
                break;
            }
            ans*=10;
            int val = s[idx]-'0';
            if(ans < Int32.MinValue+val){
                ans = Int32.MinValue;
                break;
            }
            ans-=val;
            idx++;            
        }
        if(!positive) return ans;
        if(ans == Int32.MinValue) return Int32.MaxValue;
        return ans*-1;
    }
}

複雜度分析：

  • 時間複雜度：最差要跑完整個字串，時間複雜度為O(n)。
  • 空間複雜度：空間複雜度為O(1)。

學習重點

  • String
Last Updated:
Contributors: eisen