前言
首先，正式慶祝這是我在知乎專欄寫作的第 20 篇題解（這裡的下标從 1 開始）。當然，我本地庫存的題解，還要比釋出出來的多一倍。
關鍵字：字元串，狀态機
歸航return：(Trivial) LeetCode 6—Z 字形變換zhuanlan.zhihu.com
歸航return：(Trivial) LeetCode 46—全排列zhuanlan.zhihu.com
Problem
請你來實作一個 atoi 函數，使其能将字元串轉換成整數。
首先，該函數會根據需要丢棄無用的開頭空格字元，直到尋找到第一個非空格的字元為止。接下來的轉化規則如下：
- 如果第一個非空字元為正或者負号時，則将該符号與之後面盡可能多的連續數字字元組合起來，形成一個有符号整數。
- 假如第一個非空字元是數字，則直接将其與之後連續的數字字元組合起來，形成一個整數。
- 該字元串在有效的整數部分之後也可能會存在多餘的字元，那麼這些字元可以被忽略，它們對函數不應該造成影響。
注意：假如該字元串中的第一個非空格字元不是一個有效整數字元、字元串為空或字元串僅包含空白字元時，則你的函數不需要進行轉換，即無法進行有效轉換。
在任何情況下，若函數不能進行有效的轉換時，請傳回 0 。
提示：
- 本題中的空白字元隻包括空格字元 ' ' 。
- 假設我們的環境隻能存儲 32 位大小的有符号整數，那麼其數值範圍為 [−2^31, 2^31 − 1]。如果數值超過這個範圍，請傳回 INT_MAX (2^31 − 1) 或 INT_MIN (−2^31) 。
示例 1:
輸入: "42"
輸出: 42
示例 2:
輸入: " -42"
輸出: -42
解釋: 第一個非空白字元為 '-', 它是一個負号。
我們盡可能将負号與後面所有連續出現的數字組合起來，最後得到 -42 。
示例 3:
輸入: "4193 with words"
輸出: 4193
解釋: 轉換截止于數字 '3' ，因為它的下一個字元不為數字。
示例 4:
輸入: "words and 987"
輸出: 0
解釋: 第一個非空字元是 'w', 但它不是數字或正、負号。
是以無法執行有效的轉換。
示例 5:
輸入: "-91283472332"
輸出: -2147483648
解釋: 數字 "-91283472332" 超過 32 位有符号整數範圍。
是以傳回 INT_MIN (−2^31) 。
8. 字元串轉換整數 (atoi) - 力扣（LeetCode）leetcode-cn.com
Solution
這道題目也沒有很 tricky 的東西，完全就是需要自己足夠
細心來處理問題。關于這個問題，我的思路是這樣的：
（1）維護一個最終結果是負數還是非負數的 int 變量，和一個存儲所有數字的 queue，容器的 instantiation 是 char 類型；
（2）逐個掃描字元串中的元素，直到字元串被掃描完畢，或者遇到了第一個一定不合法的字元（不是數字，空格，或者正負号）；
（3）如果掃描過程中第一次遇到了數字，空格，或者正負号，那麼意味着之後的合法字元必須全部是數字，是以将 queue 中插入一個 0，或者是這個數字本身，用來表明這個更高的合法性要求（使用 queue 非空作為是否需要使用這個合法性要求的條件），而且如果是負号，應該将上述的非負數變量 flag 記作 -1，之後将所有的數字加入隊列中來；
if (numQueue.empty())
（4）得到所有數字之後，維護一個 string 類型，将 queue 中的數字字元變成數字字元串，這裡需要将開頭的 0 去掉，是以維護一個 bool 變量來标記是否遇到過非零的數；
（5）第（4）步中得到的 string 就是以字元串形式存儲的要求的整數的絕對值，根據非負數和負數的情況分别判定是否可能溢出，如果溢出就傳回極端值，否則就将這個 string 從左到右地轉化為整數即可，這裡還需要一個模拟人類比較兩個非負整數大小的輔助函數：
bool isFormerNumericallyBiggerThanLatter(const string &s1,const string &s2);
綜上所述，代碼如下：
class Solution {
public:
int myAtoi(string str) {
if (str.size() == 0)
return 0;
int res = 0;
int isPositive = 1;
queue<char>numQueue;
for (int i = 0; i < str.size(); ++i){
if (!mayBePossible(str[i])){
break;
}
else{
if (numQueue.empty()){
if (str[i] == ' '){
continue;
}
else if (str[i] == '-'){
isPositive = -1;
numQueue.push('0');
}
else if (str[i] == '+'){
numQueue.push('0');
}
else if (isdigit(str[i])){
numQueue.push(str[i]);
}
}
else{
if (!isdigit(str[i])){
break;
}
else
numQueue.push(str[i]);
}
}
}
bool isFirstNonZeroEmerged = 0;
string resInString;
while (!numQueue.empty()){
if (isFirstNonZeroEmerged){
resInString += numQueue.front();
numQueue.pop();
}
else{
if (numQueue.front() != '0'){
isFirstNonZeroEmerged = 1;
resInString += numQueue.front();
}
numQueue.pop();
}
}
if (isPositive == 1 && isFormerNumericallyBiggerThanLatter(resInString, "2147483647"))
return INT_MAX;
if (isPositive==-1 && isFormerNumericallyBiggerThanLatter(resInString, "2147483648"))
return INT_MIN;
for (const char &ch:resInString){
res = 10*res + isPositive*(ch-'0');
}
return res;
}
private:
bool mayBePossible(const char &ch){
return (isdigit(ch) || ch == ' ' || ch == '-' || ch=='+');
}
bool isFormerNumericallyBiggerThanLatter(const string &s1, const string &s2){
if (s1.size() != s2.size()){
return s1.size() > s2.size();
}
for (int i = 0; i < s1.size(); ++i){
if (s1[i] != s2[i])
return s1[i] > s2[i];
}
return false;
}
};
這個解法的耗時是 4ms，打敗了 82.47% 的 C++ 送出。
在官方題解中還給出了一種使用狀态機的思想寫出來的代碼，雖然耗時比我這種各種 if else 要長（20ms，打敗了 8% 的 C++ 送出），而且使用了 long long 類型，但是
可讀性比我的明顯要好，值得學習。
首先維護了一個 table 用來存儲狀态，分為四種：start 代表空格，signed 代表遇到了正負号，in_number 代表某個是數字，end 代表轉化到了尾部狀态了，容易觀察到這幾個狀态的狀态轉移關系，結果在下方這個 unordered_map 中。
和有些長度固定的 unordered_map 問題一樣，這道題目也可以使用二維 int 數組來代替 unordered_map 來優化時間，但我就不狗尾續貂了，關鍵是學習這種思想。
複制代碼如下：
class Automaton {
string state = "start";
//int state = 0;
unordered_map<string, vector<string>> table = {
{"start", {"start", "signed", "in_number", "end"}},
{"signed", {"end", "end", "in_number", "end"}},
{"in_number", {"end", "end", "in_number", "end"}},
{"end", {"end", "end", "end", "end"}}
};
/*
const int table[4][4] = {
{0,1,2,3},
{3,3,2,3},
{3,3,2,3},
{3,3,3,3}
}; //use a 2-dimensional array to represent the unordered map in the official solution*/
int get_col(char c) {
if (isspace(c)) return 0;
if (c == '+' or c == '-') return 1;
if (isdigit(c)) return 2;
return 3;
}
public:
int sign = 1;
long long ans = 0;
void get(char c) {
state = table[state][get_col(c)];
if (state == "in_number") {
ans = ans * 10 + c - '0';
ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
}
else if (state == "signed")
sign = c == '+' ? 1 : -1;
}
};
class Solution {
public:
int myAtoi(string str) {
Automaton automaton;
for (char c : str){
automaton.get(c);
}
return automaton.sign * automaton.ans;
}
};
這個思路的 Java 實作：
class Solution {
public int myAtoi(String str) {
int curState = 0;
int isPositive = 1;
long res = 0;
for (int i = 0; i < str.length(); ++i){
char ch = str.charAt(i);
curState = state[curState][getState(ch)];
if (curState == 1){
isPositive = (ch == '+') ? 1 : -1;
}
if (curState == 2){
res *= 10L;
res += ch-'0';
if (res >= -(long)(Integer.MIN_VALUE))
break;
/*If the absolute value of result
is more than -INT_MIN,
the result must be overflowed.*/
}
if (curState == 3){
break;
}
}
res *= isPositive;
if (res >= Integer.MAX_VALUE){
return Integer.MAX_VALUE;
}
else if (res <= Integer.MIN_VALUE){
return Integer.MIN_VALUE;
}
return res;
}
final private int [][] state = {
{0,1,2,3},
{3,3,2,3},
{3,3,2,3},
{3,3,3,3}
};
/* 0 for beginning, 1 for the sign(positive or negative),
2 for digits, 3 for terminating further input.*/
private int getState(char ch){
if (ch == ' '){
return 0;
}
else if (ch == '+' || ch == '-'){
return 1;
}
else if (isDigit(ch)){
return 2;
}
return 3;
}
}
和 C++ 文法不一樣的幾個點：
- C++ 中求 string 的長度可以用
str.size()
str.length()
str.length()
- C++ 中獲得字元串某個位置的結果可以使用
str.operator[]()
str.at()
str.charAt()
- C++ 周遊一個
string
char ch : str
- C++ 的
int
INT_MAX
Integer.MAX_VALUE
isdigit(ch)
<cctype>
Character.isDigit(ch)
Character
- C++ 中允許
long
int
static_cast<int>(someLongVariable)
EOF。
![atoi函數_C語言字元串相關函數使用示例 strtok_r strstr strtok atoi[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)