String to Integer (atoi)
題目敘述
實作一個將字串轉換成32-bit的有符號整數的函式myAtoi(string s)
。
功能類似C/C++的atoi
函式。
myAtoi(string s)
內部演算法實作上有幾個規則:
- 忽略任何前置空格。
- 將
'-'
或'+'
作為數值的正負符號表示,如果沒有符號則預設為正數。 - 持續讀取下一個字元直到字串尾或者遇到非整數,停止讀取後忽略剩下的字串。
- 將字串內的整數轉換成整數型態的數值,若字串內沒有任何整數,則回傳結果為0。
- 當數值超出整數範圍[-2^31, 2^31-1]時,將數值限制在整數型態範圍內。
- 回傳整數作為結果。
註記:
- 只有字元
' '
才被視為空格。
- 除了前置空格以及停止讀取後的字串,不要忽略其他字元。
其他限制條件
- 字串長度為[0, 200]。
- 字串
s
包含了大小寫的英文字元、數字(0-9)、空格' '
、'+'
、'-'
、'.'
。
解題思路
這一題需要處理的條件比較多,光靠題目描述沒有辦法完全涵蓋所有狀況,所以首先我們要先進行個別案例的分析。
英文字元A-Z、a-z:
英文字元是不能被忽視的字元,所以只要遇到英文字元程式就會直接結束。
Ex.
Input :"a123"
Output:0
Input :"12a3"
Output:12
Input :" a123"
Output:0
Input :"+a123"
Output:0
Input :"-a123"
Output:0
空格' '
:
題目敘述說前置空格可以被省略,但其餘字元不能被省略,所以後置空格也在其餘字元的描述內。
Ex.
Input :" 123"
Output:123
Input :"1 23"
Output:1
正負符號'+'
、'-'
:
題目敘述說'+'
、'-'
被視為數值的正負符號被算入,所以會有以下幾種狀況:
Ex.
Input :"+123"
Output:123
Input :"-123"
Output:-123
Input :"+ 123"
Output:0
Input :"+-123"
Output:0
Input :"-+123"
Output:0
符號'.'
:
符號'.'
並沒有提到有什麼特殊的條件,所以將他視為與英文字元一樣的需要被排除的其餘字元。
停止讀取的條件:
停止讀取的條件為到達字串尾以及遇到非整數字元的其餘字元,透過上面的分析應該可以很清楚的釐清達成條件的案例,比較特殊的是計入'+'
、'-'
之後的下一個字元已經被算在轉換數值的範圍之內,要注意只要出現任何非整數字元的字元,就算是達成停止條件。
數值範圍:
數值範圍被限制在整數範圍之內,但是要注意輸入字串內的數值有可能超過整數範圍。
處理步驟:
- 先排除所有前置空格,直到遇到不是前置空格的字元。
- 排除前置空格後的第一格字元,若是
'+'
、'-'
則記錄下來。 - 若不是
'+'
、'-'
則回傳結果為0。 - 處理整數,遇到停止條件則回傳加上符號的整數數值。
程式碼:
class Solution {
public:
int myAtoi(string s) {
long res=0; //答案 處理字串過程中有可能超過整數數值,所以宣告為long。
bool negative=false; //符號
int pos=0; //字串位置
//忽略前置空格
while(s[pos]==' '){
pos++;
}
//紀錄符號
if(s[pos]=='-'){
negative=true;
pos++;
}else if(s[pos]=='+'){
pos++;
}
//忽略空格後的字元為非整數字元
// or
//紀錄符號後的字元為非整數字元
if(s[pos]<'0' or s[pos]>'9') return 0;
//處理整數字元
for(int i=pos;i<s.length();i++){
//停止條件,遇到非整數字元
if(s[i]<'0' or s[i]>'9'){
res/=10; //每一次加上數值後會做乘上10的進位,回傳前先除以10。
if(negative) res=-res; //加上符號
if(res>INT_MAX) res=INT_MAX;//將數值限制在範圍內
if(res<INT_MIN) res=INT_MIN;
return res;
}
res+=(s[i]-'0'); //加上數值,'0'-'0' = 0 ,'1' - '0' = 1 。
if(res<LONG_MAX/10)res*=10;//乘上10作進位。
}
//停止條件,到達字串尾。
res/=10; //每一次加上數值後會做乘上10的進位,回傳前先除以10。
if(negative) res=-res; //加上符號
if(res>INT_MAX) res=INT_MAX;//將數值限制在範圍內
if(res<INT_MIN) res=INT_MIN;
return res;
}
};
時間複雜度分析
最壞的狀況為從字串頭讀取到字串尾,因此為O(n)。
空間複雜度分析
沒有在函式中額外增加空間,因此為O(1)。
自動引用通知: 【LeetCode】 刷題地圖 - 人生自習室