Leetcode算法系列| 8. 字符串转换整数 (atoi)

目录

• 1.题目
• 2.题解
• • C# 解法一：及其臃肿的代码
  • C# 解法二：DFA（确定有穷自动机）

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的大小无关。