題目介紹

請你來實現一個?myAtoi(string s)?函數，使其能將字符串轉換成一個 32 位有符號整數。

函數?myAtoi(string s)?的算法如下：

1. 空格：讀入字符串并丟棄無用的前導空格（" "）
2. 符號：檢查下一個字符（假設還未到字符末尾）為?'-'?還是?'+'。如果兩者都不存在，則假定結果為正。
3. 轉換：通過跳過前置零來讀取該整數，直到遇到非數字字符或到達字符串的結尾。如果沒有讀取數字，則結果為0。
4. 舍入：如果整數數超過 32 位有符號整數范圍?[?231,? 231?? 1]?，需要截斷這個整數，使其保持在這個范圍內。具體來說，小于??231?的整數應該被舍入為??231?，大于?231?? 1?的整數應該被舍入為?231?? 1?。

返回整數作為最終結果。

示例?1：

輸入：s = "42"

輸出：42

解釋：加粗的字符串為已經讀入的字符，插入符號是當前讀取的字符。

帶下劃線線的字符是所讀的內容，插入符號是當前讀入位置。
第 1 步："42"（當前沒有讀入字符，因為沒有前導空格）^
第 2 步："42"（當前沒有讀入字符，因為這里不存在 '-' 或者 '+'）^
第 3 步："42"（讀入 "42"）^

示例?2：

輸入：s = " -042"

輸出：-42

解釋：

第 1 步："   -042"（讀入前導空格，但忽視掉）^
第 2 步："   -042"（讀入 '-' 字符，所以結果應該是負數）^
第 3 步："   -042"（讀入 "042"，在結果中忽略前導零）^

示例?3：

輸入：s = "1337c0d3"

輸出：1337

解釋：

第 1 步："1337c0d3"（當前沒有讀入字符，因為沒有前導空格）^
第 2 步："1337c0d3"（當前沒有讀入字符，因為這里不存在 '-' 或者 '+'）^
第 3 步："1337c0d3"（讀入 "1337"；由于下一個字符不是一個數字，所以讀入停止）^

示例 4：

輸入：s = "0-1"

輸出：0

解釋：

第 1 步："0-1" (當前沒有讀入字符，因為沒有前導空格)^
第 2 步："0-1" (當前沒有讀入字符，因為這里不存在 '-' 或者 '+')^
第 3 步："0-1" (讀入 "0"；由于下一個字符不是一個數字，所以讀入停止)^

示例 5：

輸入：s = "words and 987"

輸出：0

解釋：

讀取在第一個非數字字符“w”處停止。

提示：

• 0 <= s.length <= 200
• s?由英文字母（大寫和小寫）、數字（0-9）、' '、'+'、'-'?和?'.'?組成

完整代碼

class Solution {public int myAtoi(String str) {Automaton automaton = new Automaton();int length = str.length();for (int i = 0; i < length; ++i) {automaton.get(str.charAt(i));}return (int) (automaton.sign * automaton.ans);}
}class Automaton {public int sign = 1;public long ans = 0;private String state = "start";private Map<String, String[]> table = new HashMap<String, String[]>() {{put("start", new String[]{"start", "signed", "in_number", "end"});put("signed", new String[]{"end", "end", "in_number", "end"});put("in_number", new String[]{"end", "end", "in_number", "end"});put("end", new String[]{"end", "end", "end", "end"});}};public void get(char c) {state = table.get(state)[get_col(c)];if ("in_number".equals(state)) {ans = ans * 10 + c - '0';ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);} else if ("signed".equals(state)) {sign = c == '+' ? 1 : -1;}}private int get_col(char c) {if (c == ' ') {return 0;}if (c == '+' || c == '-') {return 1;}if (Character.isDigit(c)) {return 2;}return 3;}
}

?思路解析

1. 類?Solution

方法?myAtoi

• 功能：將字符串轉換為整數。
• 參數：str，表示輸入的字符串。
• 返回值：轉換后的整數。

該方法首先創建一個?Automaton?對象，然后遍歷字符串中的每個字符，調用?Automaton?對象的?get?方法進行處理。最后返回經過處理的整數結果。

2. 類?Automaton

成員變量

• sign：表示正負號，默認為 1（正數）。
• ans：存儲轉換后的整數結果。
• state：表示當前狀態，初始為 “start”。
• table：狀態轉移表，用于根據當前狀態和字符類型確定下一個狀態。

方法?get

• 功能：根據當前字符和狀態，更新狀態并處理整數轉換。
• 參數：c，表示當前處理的字符。

該方法首先根據當前狀態和字符類型，從狀態轉移表中獲取下一個狀態。然后根據下一個狀態執行相應的操作：

• 如果狀態為 “in_number”，則將當前字符轉換為整數并累加到?ans?中。同時，檢查?ans?是否超出整數范圍，并進行截斷處理。
• 如果狀態為 “signed”，則根據字符是 ‘+’ 還是 ‘-’ 設置?sign?的值。

方法?get_col

• 功能：根據字符類型返回對應的列索引。
• 參數：c，表示當前處理的字符。
• 返回值：列索引，用于在狀態轉移表中查找下一個狀態。

該方法根據字符類型返回對應的列索引：

• 空格：返回 0
• 正負號：返回 1
• 數字：返回 2
• 其他字符：返回 3

代碼執行流程

1. 創建?Automaton?對象，初始化狀態為 “start”。
2. 遍歷輸入字符串中的每個字符。
3. 調用?Automaton?對象的?get?方法，根據當前字符和狀態進行狀態轉移。
4. 在狀態轉移過程中，如果遇到數字，則累加到?ans?中，并處理整數范圍溢出。
5. 如果遇到正負號，則設置?sign?的值。
6. 遍歷結束后，根據?sign?和?ans?計算最終結果并返回。

知識點精煉

1. 字符串處理：掌握字符串的基本操作，如遍歷和字符類型判斷。
2. 有限狀態機：理解狀態機的概念，能夠根據不同輸入進行狀態轉移。
3. 符號識別：能夠處理正負號，并影響最終結果的符號。
4. 整數累加與范圍控制：在累加過程中注意整數類型的范圍限制，防止溢出。
5. 映射表應用：利用哈希表實現狀態轉移邏輯，提高代碼的可讀性和效率