首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >高频原题——LeetCode题目8:字符串转换整数 (atoi)

高频原题——LeetCode题目8:字符串转换整数 (atoi)

作者头像
二环宇少
发布2020-08-13 15:27:07
2910
发布2020-08-13 15:27:07
举报

原题描述

+

请你来实现一个atoi函数,使其能将字符串转换成整数。

首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下:

  • 如果第一个非空字符为正或者负号时,则将该符号与之后面尽可能多的连续数字字符组合起来,形成一个有符号整数。
  • 假如第一个非空字符是数字,则直接将其与之后连续的数字字符组合起来,形成一个整数。
  • 该字符串在有效的整数部分之后也可能会存在多余的字符,那么这些字符可以被忽略,它们对函数不应该造成影响。

注意:假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时,则你的函数不需要进行转换,即无法进行有效转换。

在任何情况下,若函数不能进行有效的转换时,请返回0。

提示:

  • 本题中的空白字符只包括标准的空格字符。
  • 假设我们的环境只能存储32位大小的有符号整数,那么其数值范围为 。如果数值超过这个范围,请返回 或 。

示例 1

输入:"42"

输出:42

示例 2

输入:"-42"

输出:-42

示例 3

输入:"4193 with words"

输出:4193

示例 4

输入:"words and 987"

输出:0

解释:非法输入

示例 5

输入:"-91283472332"

输出:-2147483648

解释:下溢出

原题链接:https://leetcode-cn.com/problems/string-to-integer-atoi

思路解析

+

这道题可是大公司面试常客,我希望你能够一次性搞明白。

如果你上来就开始根据规则制定if else的逻辑,那么你大概率会死在各种corner case上。从20.4%的通过率也能看出这一点,明明是一道中等难度题,硬生生的做成了困难题。

其实对编程语言的处理可比这道题复杂多了,如果套用一堆if else,那么这一坨代码就太可怕了。所以在编译原理的课中我们学习到了有限自动机(DFA)这种东西,我们只要抽象出几种状态,以及状态转换的规则,然后在代码中用table存起来,就可以非常容易的handle各种各样的边界条件和corner case,也十分容易理解。

对于这道题来说,我们可以抽象出以下四种state:start(起始), sign(符号), num(数字), end(结束)。DFA每读入一个字符,就有可能发生状态的转移,这就是我们所说的action。根据题干给定的规则,action可以有'+','-',' ', digit和其他非法字符other。

所有的状态转换关系我们可以绘制如下图所示。

好了,把这个DFA以哈希表的形式初始化到你的class中吧~

复杂度分析

+

  • 时间复杂度:
  • 空间复杂度: ,DFA和问题规模无关

C++参考代码

+

class DFA {
public:
    int get_col(char c) {
        if (c == ' ') return 0;
        else if (c == '+' || c == '-') return 1;
        else if (isdigit(c)) return 2;
        else return 3;
    }

    void transform(char c) {
        cur_state = table[cur_state][get_col(c)];
        if (cur_state == "sign") {
            sign = c == '+' ? 1: -1;
        } else if (cur_state == "num") {
            abs = abs * 10 + (c - '0');
            abs = sign == 1 ? min(abs, (long)INT_MAX) : min(abs, -(long)INT_MIN);
        }
    }

    map<string, vector<string>> table = {
        {"start", {"start", "sign", "num", "end"}},
        {"sign", {"end", "end", "num", "end"}},
        {"num", {"end", "end", "num", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };

    string cur_state = "start";
    int sign = 1;
    long abs = 0;
};

class Solution {
public:
    int myAtoi(string str) {
        DFA dfa;
        for (int i = 0; i < str.size(); ++i) {
            dfa.transform(str[i]);
        }
        return dfa.abs * dfa.sign;
    }
};
本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2020-05-20,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 互联网西门二少 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档