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

2023-12-28 13:16:22

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:
    1

  • 示例 2:
    2

  • 示例3:
    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;
    }
}

1

  • 时间复杂度:O(n)
    • 对长度为n的字符串进行处理。
  • 空间复杂度:O(1)
    • 仅用了几个变量, 与n的大小无关。

C# 解法二:DFA(确定有穷自动机)

  • 该方法使用了DFA(确定有穷自动机)算法,对于输入值str,使用 自动机 来依次处理每个字符,在这个过程中不断的改变自动机的状态,以及当前结果值,来得到最终结果。
    根据题目示例分析,可以将自动机的状态总结为4个:start(开始),signed(符号),in_number(数字),end(结束) . 自动机的初始状态为start ,在处理输入字符的过程中不断的转变状态,当状态变为end时,即可得到最终结果。
    依据题意可以建立如下图所示的自动机
    1
    为了表示方便,我们可以使用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;
    }
}

2

  • 时间复杂度:O(n)
    • 对长度为n的字符串进行处理。
  • 空间复杂度:O(1)
    • 仅用了几个变量, 与n的大小无关。

文章来源:https://blog.csdn.net/backlighting2015/article/details/135180587
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。