題目描述
字符串轉(zhuǎn)換整數(shù) (atoi)
請你來實(shí)現(xiàn)一個 atoi 函數(shù)，使其能將字符串轉(zhuǎn)換成整數(shù)。
首先，該函數(shù)會根據(jù)需要丟棄無用的開頭空格字符，直到尋找到第一個非空格的字符為止。接下來的轉(zhuǎn)化規(guī)則如下：
如果第一個非空字符為正或者負(fù)號時，則將該符號與之后面盡可能多的連續(xù)數(shù)字字符組合起來，形成一個有符號整數(shù)。
假如第一個非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來，形成一個整數(shù)。
該字符串在有效的整數(shù)部分之后也可能會存在多余的字符，那么這些字符可以被忽略，它們對函數(shù)不應(yīng)該造成影響。
注意：假如該字符串中的第一個非空格字符不是一個有效整數(shù)字符、字符串為空或字符串僅包含空白字符時，則你的函數(shù)不需要進(jìn)行轉(zhuǎn)換，即無法進(jìn)行有效轉(zhuǎn)換，在任何情況下，若函數(shù)不能進(jìn)行有效的轉(zhuǎn)換時，請返回 0 。
提示：
- 本題中的空白字符只包括空格字符 ' ' 。
- 假設(shè)我們的環(huán)境只能存儲 32 位大小的有符號整數(shù)，那么其數(shù)值范圍為 [?231, 231 ? 1]，如果數(shù)值超過這個范圍，請返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 。
示例 1:
輸入: "42"
輸出: 42
示例 2:
輸入: " -42"
輸出: -42
解釋: 第一個非空白字符為 '-', 它是一個負(fù)號。
我們盡可能將負(fù)號與后面所有連續(xù)出現(xiàn)的數(shù)字組合起來，最后得到 -42 。
示例 3:
輸入: "4193 with words"
輸出: 4193
解釋: 轉(zhuǎn)換截止于數(shù)字 '3' ，因?yàn)樗南乱粋€字符不為數(shù)字。
示例 4:
輸入: "words and 987"
輸出: 0
解釋: 第一個非空字符是 'w', 但它不是數(shù)字或正、負(fù)號。
因此無法執(zhí)行有效的轉(zhuǎn)換。
示例 5:
輸入: "-91283472332"
輸出: -2147483648
解釋: 數(shù)字 "-91283472332" 超過 32 位有符號整數(shù)范圍。
因此返回 INT_MIN (?231) 。
數(shù)據(jù)結(jié)構(gòu)
- 數(shù)組
算法思維
- 遍歷、狀態(tài)機(jī)、逆向思維
解題要點(diǎn)
- 用包含 0,1,2 三種狀態(tài)的狀態(tài)機(jī)模型來表示正負(fù)
- 邊界條件的判定：將
res*10+tmp > Integer.MAX_VALUE改為res < (Integer.MAX_VALUE-tmp)/10
“逆向思維”：將運(yùn)算放在右側(cè)，加變減，乘變除，數(shù)字變小，可以有效防止 不等式左側(cè)的 數(shù)字溢出
解題思路
一. Comprehend 理解題意
可以理解為 “過濾問題”
二. Choose 選擇數(shù)據(jù)結(jié)構(gòu)與算法
數(shù)據(jù)結(jié)構(gòu)：字符數(shù)組
算法思維：遍歷
三. Code 編碼實(shí)現(xiàn)基本解法
錯誤代碼：測試“9223372036854775808”，期望結(jié)果：2147483648，運(yùn)行結(jié)果：-2147483648
原因：數(shù)字溢出（超出 long 類型的范圍：Long.MAX_VALUE = 9223372036854775807）
class Solution{
public int myAtoi(String s) {
//1.將字符串轉(zhuǎn)換成字符數(shù)組
char[] arr = s.toCharArray();
//2.遍歷字符數(shù)組
long num = 0L;
int sign = 0;
for (int i=0; i<arr.length; i++){
if (arr[i] != ' ') {
//3.若為正負(fù)號，則判斷此前是否已經(jīng)有符號了
if (arr[i] == '-'){
if (sign == 0) sign = -1;
else break;
} else if (arr[i] == '+'){
if (sign == 0) sign = 1;
else break;
} else if (arr[i]>='0' && arr[i]<= '9'){
sign = sign==0 ? 1 : sign;
num = num * 10 + arr[i] - 48;
} else break;
}
}
//判斷溢出
num = num * sign;
if (num > Integer.MAX_VALUE) return Integer.MAX_VALUE;
else if (num < Integer.MIN_VALUE) return Integer.MIN_VALUE;
else return (int)num;
}
}
四. Consider 思考更優(yōu)解
改變算法思維：
- “有限狀態(tài)機(jī)”：正負(fù)號的三種狀態(tài)：0--初始狀態(tài)（第一位為數(shù)字），1--正（第一位為'+'），2--負(fù)（第一位為'-'）
- “逆向思維”：使用逆運(yùn)算作為邊界判斷條件，防止數(shù)字溢出
時間復(fù)雜度：O(n) -- 一次數(shù)組遍歷
空間復(fù)雜度：O(n) -- 一個字符數(shù)組的內(nèi)存空間
五. Code 編碼實(shí)現(xiàn)最優(yōu)解
class Solution{
public int myAtoi(String s) {
int res = 0;
int state = 0 ; // state == 0 為初始狀態(tài) ，1 為正整數(shù)狀態(tài) ，2為負(fù)整數(shù)
//1.遍歷字符數(shù)組
for(char i : s.toCharArray())
{
//2.對各種情況進(jìn)行判斷和過濾
if(state == 0 && i == ' ');
else if(state == 0 && i == '+') state = 1;
else if(state == 0 && i == '-') state = 2;
else if(i >= '0' && i <= '9')
{
//注意：一旦讀取到數(shù)字了，就要將狀態(tài)變?yōu)椤罢保@樣下一次讀取到'+'或'-'時才能跳出
state = state==0 ? 1 : state;
int tmp = i - '0';
//3.每次數(shù)字運(yùn)算前，都進(jìn)行溢出判斷
if(res > (Integer.MAX_VALUE-tmp)/10){
if(state == 1) return Integer.MAX_VALUE;
else return Integer.MIN_VALUE; //注意：這里沒加 if 條件是因?yàn)榇丝?state 不是 1 就是 2 了
}
res = res * 10 + tmp;
}
else break;
}
//根據(jù)符號返回結(jié)果
return state==2 ? -res : res;
}
}
執(zhí)行耗時:2 ms,擊敗了99.28% 的Java用戶
內(nèi)存消耗:38.3 MB,擊敗了90.21% 的Java用戶
六. Change 變形與延伸
=== 待續(xù) ===
