LeetCode題集-8 - 字符串轉換整數 (atoi)
題目：請你來實現一個 myAtoi(string s) 函數，使其能將字符串轉換成一個 32 位有符號整數。
01、手動處理每個字符法
最簡單的方法永遠是腦海中第一個想到的方法，也是最暴力的方法，而這一題我們只需要安裝題目要求一個一個字符處理即可，其實整個解法相當簡單。
我們梳理一下解題思路，大致可分為以下三步：
（1）處理開頭空格，通過while循環把開頭的所有空格都去除掉；
（2）處理正負符號，判斷是否包含+/-號，并做下標記；
（3）處理數字，首先判斷當前字符是否為數值，如果是則計算出其值，并且檢測是否溢出，在未溢出的情況下，通過x*10+digit的方式累計結果；
（4）最后根據正負號返回正確結果。
具體代碼如下：
//解法 1：手動處理每個字符（經典解法）
public static int MyAtoi1(string s)
{
//結果
var result = 0;
//當前處理字符索引
var index = 0;
//標記正負數
var sign = 1;
//字符串長度
var length = s.Length;
//去除開頭的空格
while (index < length && s[index] == ' ')
{
//處理下一個字符
index++;
}
//處理正負符號
if (index < length && (s[index] == '+' || s[index] == '-'))
{
//標記正負數
sign = s[index] == '-' ? -1 : 1;
//處理下一個字符
index++;
}
//轉換數字字符為數字
while (index < length && char.IsDigit(s[index]))
{
//計算當前字符數值
var digit = s[index] - '0';
//檢查是否溢出
if (result > (int.MaxValue - digit) / 10)
{
return sign == 1 ? int.MaxValue : int.MinValue;
}
//累積當前字符至結果中
result = result * 10 + digit;
//處理下一個字符
index++;
}
//返回結果
return sign * result;
}
02、正則表達式法
還有一種比較簡潔的方式，可以直接通過正則表達式匹配出滿足條件的字符，然后再通過BigInteger.TryParse進行類型轉換，之所以選擇BigInteger類型是因為其他值類型都可能導致溢出情況。
根據上一題的解題思路，我們來嘗試一步一步用正則表達式實現。
首先需要匹配開頭的空白字符。
^：表示一個錨點，匹配字符串的開頭；
\s：表示特殊字符，匹配空白字符，包括空格、制表符、換行符等；
*：表示量詞，表示其前面元素可以出現零次或多次；
因此可以通過^\s*來實現字符串開頭的空格處理。
[]：定義一個字符類，表示匹配方括號中的任意一個字符；
+-：表示加號和減號，即正數和負數符號；
？：表示量詞，表示其前面元素可以出現零次或一次；
因此可以通過[+-]?來實現匹配正負號。
\d：表示匹配一個數字字符，范圍為0-9；
+：表示量詞，表示其前面元素可以出現一次或多次；
因此可以通過\d+來實現連續數字字符匹配。
下面看看具體實現代碼：
//解法 2：正則表達式法
public static int MyAtoi2(string s)
{
//使用正則表達式匹配符合要求的部分
//^\s*：表示匹配字符串開頭的零個或多個空白字符（空格、制表符等）。
//[+-]?：表示符號（+ 或 -）可選。
//\d+：表示一個或多個數字。
var match = System.Text.RegularExpressions.Regex.Match(s, @"^\s*[+-]?\d+");
//匹配成功，并且可以轉換為數值
if (match.Success && BigInteger.TryParse(match.Value, out var result))
{
//大于int最大值
if (result > int.MaxValue)
{
return int.MaxValue;
}
//小于int最小值
if (result < int.MinValue)
{
return int.MinValue;
}
//返回結果
return (int)result;
}
return 0;
}
03、狀態機法
此題還有一種經典解法，即狀態機法，狀態機的核心思想是在一組有限的狀態中，并通過輸入觸發狀態之間的轉移。
我們以此題為例，假設在處理字符串的過程中，一直存在一個狀態state，而每次處理的當前字符則可以觸發當狀態state轉移到下一個狀態state1，如此我們只需要枚舉出所有state和當前字符關于state1的映射關系即可。
我們可以建立如下圖所示狀態機：
如上圖，如果當前state為“開始”，并且當前字符為“空格”，則state1為“開始”，如果當前字符為“數字”，則state1為“處理數字”，以此類推，而state1則會絕對當前字符具體的處理方法。
我們也可以用以下表格來表示這個狀態機：
有了狀態機狀態關系映射表，我們就可以進行代碼實現了，其邏輯也很簡單，大致分為以下四步：
（1）構建狀態機狀態表；
（2）獲取當前字符對應狀態；
（3）通過狀態轉移確定當前字符處理邏輯；
（4）對要處理的字符串進行遍歷處理得到最終結果；
具體實現代碼如下：
//解法 3：狀態機法
public int MyAtoi3(string s)
{
Automaton automaton = new Automaton();
return automaton.Atoi(s);
}
public class Automaton
{
//0:"開始"狀態
private const int Start = 0;
//1:"標記符號"狀態
private const int Signed = 1;
//2:"處理數字"狀態
private const int InNumber = 2;
//3:"結束"狀態
private const int End = 3;
//符號:1為正數，0為負數
private int _sign = 1;
//數值結果
private long _answer = 0;
//記錄當前處理狀態
private int _state = Start;
//狀態表
private readonly Dictionary<int, int[]> _table = new Dictionary<int, int[]>()
{
{Start,new int[]{ Start, Signed, InNumber, End}},
{Signed,new int[]{ End, End, InNumber, End}},
{InNumber,new int[]{ End, End, InNumber, End}},
{End,new int[]{ End, End, End, End}},
};
//處理當前字符
private void Handle(char c)
{
//獲取當前狀態
var currentState = GetState(c);
//轉移狀態
_state = _table[_state][currentState];
switch (_state)
{
//處理數字
case InNumber:
_answer = _answer * 10 + c - '0';
//溢出判斷
_answer = _sign == 1 ? Math.Min(_answer, int.MaxValue) : Math.Min(_answer, -(long)int.MinValue);
break;
//處理正負號
case Signed:
_sign = c == '+' ? 1 : -1;
break;
case Start:
case End:
break;
}
}
//獲取當前字符對應狀態
private static int GetState(char c)
{
//空格
if (char.IsWhiteSpace(c))
{
return Start;
}
//正負號
if (c == '+' || c == '-')
{
return Signed;
}
//數字
if (char.IsDigit(c))
{
return InNumber;
}
//其他
return End;
}
//字符串轉換為整數
public int Atoi(string s)
{
var length = s.Length;
for (int i = 0; i < length; ++i)
{
Handle(s[i]);
}
return (int)(_sign * _answer);
}
}
注：測試方法代碼以及示例源碼都已經上傳至代碼庫，有興趣的可以看看。https://gitee.com/hugogoos/Planner
浙公網安備 33010602011771號