題目
請(qǐng)你來實(shí)現(xiàn)一個(gè) atoi 函數(shù)萄传，使其能將字符串轉(zhuǎn)換成整數(shù)畦浓。
首先源葫，該函數(shù)會(huì)根據(jù)需要丟棄無用的開頭空格字符产还，直到尋找到第一個(gè)非空格的字符為止。接下來的轉(zhuǎn)化規(guī)則如下：
- 如果第一個(gè)非空字符為正或者負(fù)號(hào)時(shí)屯蹦，則將該符號(hào)與之后面盡可能多的連續(xù)數(shù)字字符組合起來维哈，形成一個(gè)有符號(hào)整數(shù)盯漂。
- 假如第一個(gè)非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來笨农，形成一個(gè)整數(shù)就缆。
- 該字符串在有效的整數(shù)部分之后也可能會(huì)存在多余的字符，那么這些字符可以被忽略谒亦，它們對(duì)函數(shù)不應(yīng)該造成影響竭宰。
注意：假如該字符串中的第一個(gè)非空格字符不是一個(gè)有效整數(shù)字符、字符串為空或字符串僅包含空白字符時(shí)份招，則你的函數(shù)不需要進(jìn)行轉(zhuǎn)換切揭，即無法進(jìn)行有效轉(zhuǎn)換。
在任何情況下锁摔，若函數(shù)不能進(jìn)行有效的轉(zhuǎn)換時(shí)廓旬，請(qǐng)返回 0 。
提示：
本題中的空白字符只包括空格字符 ' ' 谐腰。
假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位大小的有符號(hào)整數(shù)孕豹，那么其數(shù)值范圍為 [?231, 231 ? 1]。如果數(shù)值超過這個(gè)范圍十气，請(qǐng)返回 INT_MAX (231 ? 1) 或 INT_MIN (?231) 励背。
示例 1:
輸入: "42"
輸出: 42
示例 2:
輸入: " -42"
輸出: -42
解釋: 第一個(gè)非空白字符為 '-', 它是一個(gè)負(fù)號(hào)。
我們盡可能將負(fù)號(hào)與后面所有連續(xù)出現(xiàn)的數(shù)字組合起來砸西，最后得到 -42 叶眉。
示例 3:
輸入: "4193 with words"
輸出: 4193
解釋: 轉(zhuǎn)換截止于數(shù)字 '3' ，因?yàn)樗南乱粋€(gè)字符不為數(shù)字芹枷。
示例 4:
輸入: "words and 987"
輸出: 0
解釋: 第一個(gè)非空字符是 'w', 但它不是數(shù)字或正衅疙、負(fù)號(hào)。
因此無法執(zhí)行有效的轉(zhuǎn)換鸳慈。
示例 5:
輸入: "-91283472332"
輸出: -2147483648
解釋: 數(shù)字 "-91283472332" 超過 32 位有符號(hào)整數(shù)范圍饱溢。
因此返回 INT_MIN (?231) 。
解法一（反向排除法Python）
思路：首先對(duì)字符串進(jìn)行處理蝶涩，先排除各種意外情況理朋，則剩下的部分即為有效數(shù)字絮识。
- 處理字符開頭的空格绿聘、’0‘、正負(fù)號(hào)
- 讀取有效數(shù)值組成的字符集合
- 使用字符串比較來判斷是否越界次舌，返回有效字符
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
#author： suoxd123@126.com
class Solution:
def myAtoi(self, str1: str) -> int:
str1 = str1.lstrip()
if len(str1) == 0:
return 0
idx,flag = 0, True
if str1[0] == '-': #提取符號(hào)
flag = False
str1 = str1[1:]
elif str1[0] == '+':
str1 = str1[1:]
while len(str1) > 0 and str1[0] == '0': #去掉0開頭
str1 = str1[1:]
while idx < len(str1):#提取有效數(shù)字
if not('0' <= str1[idx] <= '9'):
break
idx += 1
numStr = str1[0:idx]
numMaxStr, numMinStr = str(2**31 - 1), str(2**31)
if idx == 0: #長(zhǎng)度為0
return 0
elif (idx > 10 or idx == 10 and numStr > numMaxStr) and flag: #大于最大值
return int(numMaxStr)
elif (idx > 10 or idx == 10 and numStr > numMinStr) and not flag: #小于最小值
return -int(numMinStr)
else:#一般情況
return int(numStr) * (1 if flag else -1)
解法二（正向檢查C#）
思路：直接對(duì)每個(gè)字符進(jìn)行判斷和審查熄攘，將讀取到的數(shù)值使用Long型變量存儲(chǔ)和查看是否對(duì)Int溢出。
- 使用flag標(biāo)記是否進(jìn)入數(shù)值模式彼念，一旦進(jìn)入數(shù)值模式挪圾，任何其它字符出現(xiàn)都將退出
- 使用num保存當(dāng)前已經(jīng)記錄的數(shù)值
- 任何出現(xiàn)的其它字符都屬于結(jié)束后續(xù)檢查
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
//author： suoxd123@126.com
public class Solution {
public int MyAtoi(string str) {
bool nagetive = false , flag = false;
long num = 0;
long minN = 0-(long)Math.Pow(2,31),maxN = (long)Math.Pow(2,31) - 1;
for(int i=0;i<str.Length;i++)
{
if(str[i] == '-' || str[i] == '+')
{//符號(hào)
if(flag == true)
break;
flag = true;
if(str[i] == '-')
{
nagetive = true;
}
}
else if(str[i] <= '9' && str[i] >= '0')
{//數(shù)值
flag = true; //標(biāo)記是否已經(jīng)進(jìn)入計(jì)數(shù)模式
num = num * 10 + (str[i] - '0') * (nagetive?-1:1);
if(num>maxN || num < minN)
{
if(num < minN)
num = minN;
else
num = maxN;
break;
}
}
else if(str[i] == ' ')
{//空格
if(flag == true)
break;
continue;
}
else
{//其它字符
break;
}
}
return (int)(num);
}
}
解法三（有限狀態(tài)機(jī) C語言）
思路：使用狀態(tài)機(jī)的思路來浅萧，搞清楚不同狀態(tài)之間的切換關(guān)系即可，本題根據(jù)空格哲思、符號(hào)洼畅、數(shù)值和其它字符4種類型，可以定義開始棚赔、符號(hào)帝簇、數(shù)值和結(jié)束4個(gè)狀態(tài)，狀態(tài)跳轉(zhuǎn)如下表（橫坐標(biāo)為當(dāng)前狀態(tài)靠益，縱坐標(biāo)為當(dāng)前字符丧肴，跳轉(zhuǎn)表指當(dāng)前狀態(tài)遇到當(dāng)前字符的下一個(gè)狀態(tài)）：
| 當(dāng)前狀態(tài) | 空格 | 正負(fù)號(hào) | 數(shù)值 | 其它字符 |
|---|---|---|---|---|
| 開始 | 開始 | 符號(hào) | 數(shù)值 | 結(jié)束 |
| 符號(hào) | 結(jié)束 | 結(jié)束 | 數(shù)值 | 結(jié)束 |
| 數(shù)值 | 結(jié)束 | 結(jié)束 | 數(shù)值 | 結(jié)束 |
| 結(jié)束 | 結(jié)束 | 結(jié)束 | 結(jié)束 | 結(jié)束 |
- 定義狀態(tài)跳轉(zhuǎn)矩陣和跳轉(zhuǎn)函數(shù)
- 循環(huán)讀取當(dāng)前字符，直到狀態(tài)進(jìn)入結(jié)束
- 當(dāng)前結(jié)果轉(zhuǎn)換為字符串
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
//author： suoxd123@126.com
int getStatus(int lastStatus,char currentChar){//狀態(tài)跳轉(zhuǎn)
int currentStatus = 0;
const int status[4][4] = {//狀態(tài)跳轉(zhuǎn)矩陣
{1,2,3,4},
{4,4,3,4},
{4,4,3,4},
{4,4,4,4}
};
if(currentChar == ' '){
currentStatus = 1;
}
else if(currentChar == '+' || currentChar == '-'){
currentStatus = 2;
}
else if(currentChar >= '0' && currentChar <= '9'){
currentStatus = 3;
}
else{
currentStatus = 4;
}
return status[lastStatus-1][currentStatus-1];
}
int myAtoi(char * str){
int status = 1, sign = 1; //狀態(tài)默認(rèn)是1（開始狀態(tài)）
char numChar = *str++;
long val = 0;
int intMax = 0x7FFFFFFF, intMin = -0x80000000;
while(status < 4 && numChar != '\0'){
status = getStatus(status,numChar);
if(status == 2){//符號(hào)
sign = (numChar == '-' ? -1:1);
}
else if(status == 3){//數(shù)值
val = val * 10 + sign * (numChar - '0');
if(sign == 1){//檢查向上越界
val = val > intMax?intMax:val;
}
else{//檢查向下越界
val = val < intMin?intMin:val;
}
}
numChar = *str++;
}
return (int)val;
}
