⭐算法入门⭐《模拟》中等01 —— LeetCode 8. 字符串转换整数_2个 加1个 等于72, 表是一个数字,是几

一、题目

1、题目描述

  实现一个myAtoi(string s)函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。函数 myAtoi(string s) 的算法如下：
  1）读入字符串并丢弃无用的前导空格；
  2）检查下一个字符为正还是负号，读取该字符。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
  3）读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。将前面步骤读入的这些数字转换为整数。如果没有读入数字，则整数为 0 。
  4）如果整数超过 32 位有符号整数范围 $[-2^{31},2^{31}-1]$，需要截断这个整数，使其保持在这个范围内。具体来说，小于 $-2^{31}$ 的整数应该被固定为 $-2^{31}$ ，大于 $2^{31}-1$ 的整数应该被固定为 $2^{31}-1$。
  返回整数作为最终结果。
  样例输入1： “+123”
  样例输出1： 123

  样例输入2："   -123"
  样例输出2： $-123$

  样例输入3： “hahaha 996”
  样例输出3： 0

  样例输入4："-9231243283324473242332"，
  样例输出4： -2147483648

  样例输入5： “-+1”
  样例输出5： 0

2、基础框架

• c++ 版本给出的基础框架代码如下，给定一个字符串，返回一个整数。

class Solution {
public:
    int myAtoi(string s) {
    }
};
1
2
3
4
5

3、原题链接

LeetCode 8. 字符串转换整数 (atoi)

二、解题报告

1、思路分析

  这个就是一个典型的模拟题，题目很简单，就是给定一个字符串，我们需要将它转换成整型返回。然而要考虑很多的点，接下来我们一一分析：
  1）需要去除前导空格；
  2）判断第一个字符：
   2.a）如果第 1 个符号是'+'，则取从第 2 个符号开始的子串；
   2.b）如果第 1 个符号是'-'，则取从第 2 个符号开始的子串，并且记录符号位；
   2.c）否则，什么都不做；
  3）遍历得到的字符串，不断计算累加和，如果等到的数超出int范围，按照最大值还是最小值分情况返回，或者遇到不是数字的字符，就跳出循环；
  4）返回当前的累加和 乘上 符号位 的结果。

2、时间复杂度

• 基本所有的操作都是一层for循环枚举，所以时间复杂度为 $O(n)$。

3、代码详解

class Solution {
public:
    string trim(string s) {                               // (1)
        string ret;
        int notEmptyIdx = s.size();
        for(int i = 0; i < s.size(); ++i) {
            if( s[i] == ' ' ) {
                continue;
            }else {
                notEmptyIdx = i;
                break;
            }
        }
        for(int i = notEmptyIdx; i < s.size(); ++i) {
            ret.push_back( s[i] );
        }
        return ret;
    }
    string positiveCheck(string s) {                      // (2)
        string ret;
        for(int i = 1; i < s.size(); ++i) {
            ret.push_back(s[i]);
        }
        return ret;
    }
    string negtaiveSplit(string s, int &flag) {           // (3)
        if(s.size() == 0) {
            flag = 1;
            return s;
        }
        if(s[0] == '-') {
            flag = -1;
            string ret;
            for(int i = 1; i < s.size(); ++i) {
                ret.push_back(s[i]);
            }
            return ret;
        }
        flag = 1;
        return s;
    }

    int myAtoi(string s) {
        int flag = 1;
        long long sum = 0;                              // (4)
        s = trim(s);
        if(s.size() == 0) {
            return 0;
        }

        if(s[0] == '+')
            s = positiveCheck(s);
        else if(s[0] == '-')
            s = negtaiveSplit(s, flag);

 
        long long minv = INT_MIN;
        long long maxv = INT_MAX;
        for(int i = 0; i < s.size(); ++i) {
            if(s[i] >= '0' && s[i] <= '9') {
                sum = sum * 10 + s[i] - '0';
                if(sum * flag < minv) {
                    return minv;                       // (5)
                }
                if(sum * flag > maxv) {
                    return maxv;                       // (6)
                }
            }else {
                break;                                 // (7)
            }
        }
        return sum * flag;                             // (8)

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75

• $(1)$ string trim(string s)这个函数就是传入字符串s，返回一个去掉前导空格的字符串，这一步的时间复杂度为 $O(n)$。
• $(2)$ string positiveCheck(string s)函数的作用，是去掉第一个字符为'+'的情况，并且返回字符串，这一步的时间复杂度也为 $O(n)$。
• $(3)$ string negtaiveSplit(string s, int &flag)函数的作用，是对于负数的处理，将符号存储到 flag变量中，并且通过引用返回。
• $(4)$ 用long long是因为需要考虑int越界的情况；
• $(5)$ 超过int最小值；
• $(6)$ 超过int最大值；
• $(7)$ 出现非法符号；
• $(8)$ 考虑负数的存在，所以需要乘上flag。

---

三、本题小知识

int越界的情况，可以使用long long来化解。

---

四、加群须知

  相信看我文章的大多数都是「 大学生 」，能上大学的都是「 精英 」，那么我们自然要「 精益求精 」，如果你还是「 大一 」，那么太好了，你拥有大把时间，当然你可以选择「 刷剧 」，然而，「 学好算法 」，三年后的你自然「 不能同日而语 」。
  那么这里，我整理了「 几十个基础算法 」 的分类，点击开启：

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/87216