每日一道 LeetCode (50)：字符串轉(zhuǎn)換整數(shù) (atoi)

?

每天 3 分鐘，走上算法的逆襲之路。

?

前文合集

每日一道 LeetCode 前文合集

代碼倉庫

GitHub：https://github.com/meteor1993/LeetCode

Gitee：https://gitee.com/inwsy/LeetCode

題目：最長回文子串

難度：「中等」

題目來源：https://leetcode-cn.com/problems/string-to-integer-atoi/

請你來實現(xiàn)一個 atoi 函數(shù)，使其能將字符串轉(zhuǎn)換成整數(shù)。

首先，該函數(shù)會根據(jù)需要丟棄無用的開頭空格字符，直到尋找到第一個非空格的字符為止。接下來的轉(zhuǎn)化規(guī)則如下：

• 如果第一個非空字符為正或者負號時，則將該符號與之后面盡可能多的連續(xù)數(shù)字字符組合起來，形成一個有符號整數(shù)。
• 假如第一個非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來，形成一個整數(shù)。
• 該字符串在有效的整數(shù)部分之后也可能會存在多余的字符，那么這些字符可以被忽略，它們對函數(shù)不應該造成影響。

注意：假如該字符串中的第一個非空格字符不是一個有效整數(shù)字符、字符串為空或字符串僅包含空白字符時，則你的函數(shù)不需要進行轉(zhuǎn)換，即無法進行有效轉(zhuǎn)換。

在任何情況下，若函數(shù)不能進行有效的轉(zhuǎn)換時，請返回 0 。

提示：

• 本題中的空白字符只包括空格字符 ' ' 。
• 假設我們的環(huán)境只能存儲 32 位大小的有符號整數(shù)，那么其數(shù)值范圍為?[?2^31, ?2^31 ? 1]。如果數(shù)值超過這個范圍，請返回 ?INT_MAX (2^31 ? 1) 或 INT_MIN (?2^31) 。

示例?1:

輸入:?"42"
輸出:?42

示例?2:

輸入:?"???-42"
輸出:?-42
解釋:?第一個非空白字符為?'-', 它是一個負號。
?????我們盡可能將負號與后面所有連續(xù)出現(xiàn)的數(shù)字組合起來，最后得到?-42 。

示例?3:

輸入:?"4193?with?words"
輸出:?4193
解釋:?轉(zhuǎn)換截止于數(shù)字?'3'?，因為它的下一個字符不為數(shù)字。

示例?4:

輸入:?"words?and?987"
輸出:?0
解釋:?第一個非空字符是?'w', 但它不是數(shù)字或正、負號。
?????因此無法執(zhí)行有效的轉(zhuǎn)換。

示例?5:

輸入:?"-91283472332"
輸出:?-2147483648
解釋:?數(shù)字?"-91283472332"?超過 32 位有符號整數(shù)范圍。?
?????因此返回 INT_MIN (?231)?。

解題方案：有限狀態(tài)機

這道題單純的做出來，并不是很難，純暴力的解法肯定搞得定，除了邏輯復雜一點，判斷多一點，各種 flag 多立幾個，做肯定是做得出來的。

這道題的難度定成中等，肯定不是要我們用暴力解法把它解出來的，不然沒必要搞成中等難度，簡單難度就夠了，除了邏輯復雜點，這種方案找不到任何難點，這不符合力扣的尿性，一定有我不知道的解法。

果然，在答案中我看到了一個新名詞，叫做「狀態(tài)機」。

狀態(tài)機的基本定義：狀態(tài)機是有限狀態(tài)自動機的簡稱，是現(xiàn)實事物運行規(guī)則抽象而成的一個數(shù)學模型。

狀態(tài)機里面有 4 個概念：

第一個是 State ，狀態(tài)。一個狀態(tài)機至少要包含兩個狀態(tài)。

第二個是 Event ，事件。事件就是執(zhí)行某個操作的觸發(fā)條件或者口令。

第三個是 Action ，動作。事件發(fā)生以后要執(zhí)行動作。

第四個是 Transition ，變換。也就是從一個狀態(tài)變化為另一個狀態(tài)。

套到這道題里就是我們的程序在每個時刻有一個狀態(tài) s ，每次從序列中輸入一個字符 c ，并根據(jù)字符 c 轉(zhuǎn)移到下一個狀態(tài) s' 。這樣，我們只需要建立一個覆蓋所有情況的從 s 與 c 映射到 s' 的表格即可解決題目中的問題。

答案中給出的示例圖是這樣的：

接下來就是把這一個構(gòu)件的狀態(tài)機寫成代碼：

public?class?Automaton?{
????//?正負
????public?int?sign?=?1;
????//?數(shù)值
????public?long?ans?=?0;
????private?String?state?=?"start";

????private?Map?table?=?new?HashMap()?{{
????????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;
????}
}

然后我們在主方法里面調(diào)用這個狀態(tài)機：

public?int?myAtoi(String?str)?{
????Automaton?automaton?=?new?Automaton();
????char[]?c?=?str.toCharArray();
????for?(int?i?=?0;?i?????????automaton.get(c[i]);
????}
????return?(int)?(automaton.sign?*?automaton.ans);
}

參考

https://zhuanlan.zhihu.com/p/47434856