1.题目
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
1.读入字符串并丢弃无用的前导空格
2.检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3.读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4.将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
5.如果整数数超过 32 位有符号整数范围 [−2^31, 2^31 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −2^31 的整数应该被固定为 −2^31 ，大于 2^31 − 1 的整数应该被固定为 2^31 − 1 。
6.返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ’ ’ 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
- 示例1:
- 示例 2：
- 示例3：
- 提示：
- -0 <= s.length <= 200
- s 由英文字母（大写和小写）、数字（0-9）、’ ‘、’+‘、’-’ 和 ‘.’ 组成
2.题解
C# 解法一：及其臃肿的代码
- 官方题解提到的那种 “及其臃肿的代码”的方法，虽然说臃肿，但实际代码量比起官方解法还是要少一些，而且在很多实际工作中的应用场景下，还是避免不了 像这样 大量使用 if else 来处理特殊输入 的 情况，所以这种方法也不失为一种好的方法。
class Solution { public int MyAtoi(string str) { str = str.Trim(); if (str.Length == 0) return 0; //首位不是数字或者正负号，直接返回0 if (!char.IsDigit(str[0]) && str[0] != '-' && str[0] != '+') return 0; // 截取前面的数字串 for (int i = 1; i < str.Length; i++) { if (!char.IsDigit(str[i])) { str = str.Substring(0, i); break; } } //只剩下符号了，直接返回0 if (str == "-" || str == "+" || str == "+-" || str == "-+") return 0; //正常数字求结果 int result = 0; if (int.TryParse(str, out int tryResult2)) { result = tryResult2; } else { if (str.Contains("-")) result = int.MinValue; else result = int.MaxValue; } return result; } }
- 时间复杂度：O(n)
- 对长度为n的字符串进行处理。
- 空间复杂度：O(1)
- 仅用了几个变量, 与n的大小无关。
C# 解法二：DFA（确定有穷自动机）
- 该方法使用了DFA（确定有穷自动机）算法，对于输入值str，使用 自动机 来依次处理每个字符，在这个过程中不断的改变自动机的状态，以及当前结果值，来得到最终结果。
根据题目示例分析，可以将自动机的状态总结为4个：start（开始），signed（符号），in_number（数字）,end（结束） . 自动机的初始状态为start ，在处理输入字符的过程中不断的转变状态，当状态变为end时，即可得到最终结果。
依据题意可以建立如下图所示的自动机
为了表示方便，我们可以使用int型来表示这4个状态，0表示start，1表示signed，2表示in_number,3表示end。 所以对应上面的自动机状态表格，在代码中可以使用二维int数组来表示：
public readonly int[,] table = new int[4, 4] { { 0,1,2,3 }, { 3,3,2,3 }, { 3,3,2,3 }, { 3,3,3,3 } };
- 根据这个table，我们就可以使用 当前状态 以及 输入字符类型 来获取到下一个状态。比如当前状态为0 start，输入字符类型为 1 +/-，则下一个状态为 table[0][1] ，即 1 signed 。
由题意知 【假设我们的环境只能存储 32 位大小的有符号整数】，但是官方题解的python解法 由于python的数字类型问题 而 没有处理 int型的范围溢出 问题，官方题解的c++解法则直接使用了long long 来跳过对溢出问题的处理。虽然本文解法考虑了这一点，并进行了处理，但官方解法的这种处理也是可以通过的。
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
class Solution { public class Automaton { /// <summary> /// 0 start , 1 signed , 2 in_number , 3 end /// </summary> public int state = 0; public int sign = 1; public int result = 0; public readonly int[,] table = new int[4, 4] { { 0,1,2,3 }, { 3,3,2,3 }, { 3,3,2,3 }, { 3,3,3,3 } }; public int GetCol(char c) { if (char.IsWhiteSpace(c)) return 0; if (c == '+' || c == '-') return 1; if (char.IsDigit(c)) return 2; return 3; } public void Get(char c) { this.state = this.table[this.state, this.GetCol(c)]; var INT_MAX = int.MaxValue; var INT_MIN = int.MinValue; // 0 start , 1 signed , 2 in_number , 3 end if (this.state == 2) { var cInt = Convert.ToInt32(c.ToString()); if (this.sign == 1) { if (result > INT_MAX / 10 || (result == INT_MAX / 10 && cInt > 7)) this.result = INT_MAX; else this.result = this.result * 10 + cInt; } else { if (result < INT_MIN / 10 || (result == INT_MIN / 10 && cInt > 8)) this.result = INT_MIN; else this.result = this.result * 10 - cInt; } } else if (this.state == 1) { this.sign = 1; if (c == '-') this.sign = -1; } } } public int MyAtoi(string str) { Automaton automaton = new Automaton(); foreach (var c in str) automaton.Get(c); return automaton.result; } }
- 时间复杂度：O(n)
- 对长度为n的字符串进行处理。
- 空间复杂度：O(1)
- 仅用了几个变量, 与n的大小无关。
