8

這一題要實作atoi(ASCII string TO Integrer)，這題有趣的地方在於他一開始就特意說明題目寫得很模糊是故意的，應該是想要考驗解題者考慮各種case的能力。越不一樣的題目對訓練越有用，所以這是一題很棒的練習題。

幸好我現在已經完全忘記atoi的行為，所以可以從最直觀的想法出發，一步步找出答案。首先看到atoi，最直觀會想到的是，他吃進一個String，吐出一個integer，這個關係會是一對一的嗎? 在回答這個問題之前，先停一下，我們平常在解問題的時候，都有一種衝動是，看到一個問題就想跳進去找出答案，但今天想做個新的嘗試，先把相關的疑惑都先列出來，然後我想驗證，是不是只要把這些疑惑都弄清楚了，自然就可以知道該怎麼寫。

string -> atoi -> int 的關係會是一對一嗎? (牽涉到string最大可以多大、int最大可以多大)
string 如果是空的，對應到的int會是什麼? 0嗎?
長度為1的string，有幾種可能性?是所有ASCII code會涵蓋的範圍嗎?
同樣長度的string，但ASCII code不同，會怎麼對應到不同的int? (e.g. "a" 跟 "b" 或 "a"跟"A")
不同長度的string，會怎麼對應到不同的int? (e.g. "a" 跟 "aa", "a" 跟 "ab")

不知不覺就列出了許多問題，理論上，如果我沒有漏問問題，只要回答得出來這些問題我就能實作出來。另一個問題是，如果在手邊沒有資料可以查的時候，要怎麼回答出這些問題?

先不要考慮沒有資料可以查的case，因為這些知識就是我們平常要準備好的。先單純檢驗我們自己提出問題的能力是不是已經足夠縝密。接下來就來一個個回答上面的問題:

首先，int的範圍是-2,147,483,648 ~ 2,147,483,647，講到+跟-就想到我們要怎麼決定字串是+還是-? 這時我才突然想起來，對吼，我之前在用num=atoi(s)的時候，都是已經可以直接看出s對應的數值該是多少了，我只是需要把它的型態轉換成int而已。所以這邊也順帶回答到第三個問題的答案，如果長度是1的話，就只有0~9這10種可能性而已。所以回到正負號的問題，如果s裡面有-為開頭，那就應該是負的int，反之如果有+或是沒特別寫，那就應該要是正的。

所以最一般的case應該就是正常的輸入，例如s="-2147483648"，轉換起來就很簡單，只要先處理負號，然後看剩下的數字有多長，就從個位數 + 十位數x10 + ...一路算下去得到結果，不過還要處理溢位問題(就假設超過最大值，應該要回傳最大值；低於最小值，回傳最小值)。
string如果是NULL，直觀上想起來對應到的int也應該是NULL。(查了一下應該要回傳的值，在這個case應該是0)
長度為1的string如果要是合理的int，就只有0~9這10種可能性。這邊倒是延伸出另一個問題，如果傳進來的s長度為1，但是是0~9以外的其他符號，那要怎麼處理?

至於4 & 5這兩題在理解atoi的行為之後，就沒有回答的必要了XD

整合一下目前有的線索，目前我的myAtoi想要cover的input有

s=NULL, 回傳0
s="-2147483648"~"+2147483647"，回傳算出來的int
s="-2147483649",回傳-2147483648；s="+2147483648"，回傳2147483647

不過如果只是這樣，這題應該就不用出了吧，所以接下來要再考慮到其他例外狀況。例外狀況的本質就是，會有其他的符號出現在某些地方，就像一開始我不知道atoi會有什麼行為的時候，會想要考慮所有ASCII支援符號要怎麼轉成int的case。這些符號能夠介入的地方也只有三種，正常的s的前面、中間跟後面。

舉例來說，s="-11"，那可能會有幾種例外情況，順手把我覺得這幾種情況應該怎麼處理寫下來:

s="#-11" => 回傳-11，因為是一路往下trace到負號才開始處理(如果真的在面試的時候碰到，還是要跟面試官確認一下)
s="-1#1" => 回傳-1，因為讀到#就表示目前的數字已經中斷
s="-11#" => 回傳-11，因為讀到#就表示目前的數字已經中斷

我的想像是，不屬於正常數字該有的符號，如果是在最前面讀到，那可以先忽略，因為後面還可能有可以解讀的正常數字；而如果是已經開始讀到正常數字，但是接下來卻讀到奇怪的符號，那就應該停止，回傳目前得到的數字。(Again，這種有自己假設的東西，在面試的時候應該都要跟面試官確認，這邊只需要表達出自己有提出假設的能力即可，要怎麼定義atoi的行為只是知識，詢問無妨)

想像完之後當然還是要查一下，這些答案在C++ atoi的頁面都可以查到，但我們現在是在練習，所以不要去看詳細的描述，只看自己需要的部分就好，之後再來驗證自己是不是還有少問什麼問題。

所以到目前為止，我的myAtoi好像變得比較厲害一點，他可以吃更多種string進來而不會拉肚子:

s=NULL, 回傳0
s="-2147483648"~"+2147483647"，回傳算出來的int
s="-2147483649",回傳-2147483648；s="+2147483648"，回傳2147483647
s="$@% 456",回傳456
s="-789^%&&",回傳-789
s="-7^%&&89",回傳-7

到這邊為止，應該已經考慮完畢，因為是從最general的想像開始收斂，考慮到各種符號的變化狀況，也考慮到各種符號的排列狀況，接下來要把這些性質(descriptive spec)化成程式的行為(operational spec)。

如果S=NULL或長度是0，回傳0
首先假設int是正的，從string最前面一個個往後看，直到看到正負號或數字(第一個數字不能為0)才開始計算要回傳的int。如果都沒有碰到數字，也是回傳0
開始計算int之後，一個個往後看，每次往後看就把目前計算到的int乘上10，再加上最新一位數字，然後就順便檢查會不會溢位
碰到字串結束或是非0~9的符號就停止計算，並回傳答案

有了operational spec之後，實作出來的code如下:

class Solution {
public:
    int myAtoi(string str) {
        if(str.length() == 0) 
            return 0;

        int sign = 1;
        int ans = 0, digit;
        bool flag=false;

        for(int i=0; i<str.length(); i++)
        {
            if(flag == false)
            {
                if(str.at(i) == '-' || str.at(i) == '+')
                {
                    sign = (str.at(i) == '+' ? 1 : -1);
                    flag = true;
                }
                else if(str.at(i) > '0' && str.at(i) <='9')
                {
                    ans = str.at(i)-'0';
                    flag = true;
                }
                else
                    continue;
            }
            else
            {
                if(str.at(i) >= '0' && str.at(i) <='9')
                {
                    digit = str.at(i)-'0';

                    //Check if overflow
                    if (INT_MAX/10 < ans || (INT_MAX/10 == ans && INT_MAX % 10 < digit))
                        return sign == 1 ? INT_MAX : INT_MIN;

                    ans = ans*10 + digit;
                }
                else
                    break;
            }
        }

        return sign*ans;
    }
};

不過這個程式碼會掛在s=" b127494"這種case，所以看起來是只要由奇怪符號開頭的話，就直接回傳0。看來這邊是我沒有確認清楚atoi的行為，才會有這個問題，修改之後就可以過了。

class Solution {
public:
    int myAtoi(string str) {
        if(str.length() == 0) 
            return 0;

        int sign = 1;
        int ans = 0, digit;
        bool flag=false;

        for(int i=0; i<str.length(); i++)
        {
            if(flag == false)
            {
                if(str.at(i) == '-' || str.at(i) == '+')
                {
                    sign = (str.at(i) == '+' ? 1 : -1);
                    flag = true;
                }
                else if(str.at(i) > '0' && str.at(i) <='9')
                {
                    ans = str.at(i)-'0';
                    flag = true;
                }
                else if(str.at(i) == ' ' || str.at(i) == '0')
                    continue;
                else
                    break;
            }
            else
            {
                if(str.at(i) >= '0' && str.at(i) <='9')
                {
                    digit = str.at(i)-'0';

                    //Check if overflow
                    if (INT_MAX/10 < ans || (INT_MAX/10 == ans && INT_MAX % 10 < digit))
                        return sign == 1 ? INT_MAX : INT_MIN;

                    ans = ans*10 + digit;
                }
                else
                    break;
            }
        }

        return sign*ans;
    }
};

經過這次的實驗驗證，發現只要前期想得夠透徹，有可能可以把case都想完整。只是這個過程不夠精煉，花了很多時間，而且想出這些case之後，對應到程式碼的功力也還有待提升(例如處理溢位的地方就卡了一陣子)，看來目前還沒有把這題學到完全懂的能力，之後值得回來再訪。

# 8

8

results matching ""

No results matching ""