每日一道 LeetCode (50)：字符串轉(zhuǎn)換整數(shù) (atoi)
?每天 3 分鐘，走上算法的逆襲之路。
?
前文合集
代碼倉(cāng)庫(kù)
GitHub：https://github.com/meteor1993/LeetCode
Gitee：https://gitee.com/inwsy/LeetCode
題目：最長(zhǎng)回文子串
難度：「中等」
題目來(lái)源：https://leetcode-cn.com/problems/string-to-integer-atoi/
請(qǐng)你來(lái)實(shí)現(xiàn)一個(gè) atoi 函數(shù)，使其能將字符串轉(zhuǎn)換成整數(shù)。
首先，該函數(shù)會(huì)根據(jù)需要丟棄無(wú)用的開(kāi)頭空格字符，直到尋找到第一個(gè)非空格的字符為止。接下來(lái)的轉(zhuǎn)化規(guī)則如下：
如果第一個(gè)非空字符為正或者負(fù)號(hào)時(shí)，則將該符號(hào)與之后面盡可能多的連續(xù)數(shù)字字符組合起來(lái)，形成一個(gè)有符號(hào)整數(shù)。 假如第一個(gè)非空字符是數(shù)字，則直接將其與之后連續(xù)的數(shù)字字符組合起來(lái)，形成一個(gè)整數(shù)。 該字符串在有效的整數(shù)部分之后也可能會(huì)存在多余的字符，那么這些字符可以被忽略，它們對(duì)函數(shù)不應(yīng)該造成影響。
注意：假如該字符串中的第一個(gè)非空格字符不是一個(gè)有效整數(shù)字符、字符串為空或字符串僅包含空白字符時(shí)，則你的函數(shù)不需要進(jìn)行轉(zhuǎn)換，即無(wú)法進(jìn)行有效轉(zhuǎn)換。
在任何情況下，若函數(shù)不能進(jìn)行有效的轉(zhuǎn)換時(shí)，請(qǐng)返回 0 。
提示：
本題中的空白字符只包括空格字符 ' ' 。 假設(shè)我們的環(huán)境只能存儲(chǔ) 32 位大小的有符號(hào)整數(shù)，那么其數(shù)值范圍為?[?2^31, ?2^31 ? 1]。如果數(shù)值超過(guò)這個(gè)范圍，請(qǐng)返回 ?INT_MAX (2^31 ? 1) 或 INT_MIN (?2^31) 。
示例?1:
輸入:?"42"
輸出:?42
示例?2:
輸入:?"???-42"
輸出:?-42
解釋:?第一個(gè)非空白字符為?'-', 它是一個(gè)負(fù)號(hào)。
?????我們盡可能將負(fù)號(hào)與后面所有連續(xù)出現(xiàn)的數(shù)字組合起來(lái)，最后得到?-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)。
?????因此無(wú)法執(zhí)行有效的轉(zhuǎn)換。
示例?5:
輸入:?"-91283472332"
輸出:?-2147483648
解釋:?數(shù)字?"-91283472332"?超過(guò) 32 位有符號(hào)整數(shù)范圍。?
?????因此返回 INT_MIN (?231)?。
解題方案：有限狀態(tài)機(jī)
這道題單純的做出來(lái)，并不是很難，純暴力的解法肯定搞得定，除了邏輯復(fù)雜一點(diǎn)，判斷多一點(diǎn)，各種 flag 多立幾個(gè)，做肯定是做得出來(lái)的。
這道題的難度定成中等，肯定不是要我們用暴力解法把它解出來(lái)的，不然沒(méi)必要搞成中等難度，簡(jiǎn)單難度就夠了，除了邏輯復(fù)雜點(diǎn)，這種方案找不到任何難點(diǎn)，這不符合力扣的尿性，一定有我不知道的解法。
果然，在答案中我看到了一個(gè)新名詞，叫做「狀態(tài)機(jī)」。
狀態(tài)機(jī)的基本定義：狀態(tài)機(jī)是有限狀態(tài)自動(dòng)機(jī)的簡(jiǎn)稱，是現(xiàn)實(shí)事物運(yùn)行規(guī)則抽象而成的一個(gè)數(shù)學(xué)模型。
狀態(tài)機(jī)里面有 4 個(gè)概念：
第一個(gè)是 State ，狀態(tài)。一個(gè)狀態(tài)機(jī)至少要包含兩個(gè)狀態(tài)。
第二個(gè)是 Event ，事件。事件就是執(zhí)行某個(gè)操作的觸發(fā)條件或者口令。
第三個(gè)是 Action ，動(dòng)作。事件發(fā)生以后要執(zhí)行動(dòng)作。
第四個(gè)是 Transition ，變換。也就是從一個(gè)狀態(tài)變化為另一個(gè)狀態(tài)。
套到這道題里就是我們的程序在每個(gè)時(shí)刻有一個(gè)狀態(tài) s ，每次從序列中輸入一個(gè)字符 c ，并根據(jù)字符 c 轉(zhuǎn)移到下一個(gè)狀態(tài) s' 。這樣，我們只需要建立一個(gè)覆蓋所有情況的從 s 與 c 映射到 s' 的表格即可解決題目中的問(wèn)題。
答案中給出的示例圖是這樣的：
| '' | +/- | number | other | |
|---|---|---|---|---|
| start | start | signed | in_number | end |
| signed | end | end | in_number | end |
| in_number | end | end | in_number | end |
| end | end | end | end | end |
接下來(lái)就是把這一個(gè)構(gòu)件的狀態(tài)機(jī)寫(xiě)成代碼：
public?class?Automaton?{
????//?正負(fù)
????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;
????}
}
然后我們?cè)谥鞣椒ɡ锩嬲{(diào)用這個(gè)狀態(tài)機(jī)：
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
