描述

题目描述

就是手写一个$atoiatoi$函数, 满足一下规则

算法流程:

1. 去掉前面的空格
2. 判断第一个非空字符是什么
3. 找尽可能多的数字位
4. 在INT_MIN - 1 到 INT_MAX之间

题解

解法一

实现思路

其实这个题目就是一个大模拟, 我们只需要按照步骤模拟即可, 这里面会有几个坑点, 就是我们返回值的时候, 要根据我们的正负号来决定返回什么, 而不简单的是$INT\mathrm{\_}MININT\backslash \_MIN$和$INT\mathrm{\_}MAXINT\backslash \_MAX$, 然后可以利用$longlonglong\; long$简化

代码实现

class Solution {
   public:
    int StrToInt(string s) {
        int pos = -1;
        for (int i = 0; i < s.size(); i++) {
            if (s[i] != ' ') {
                pos = i;
                break;
            }
        }
        // 找到第一个非零的下标
        if (isdigit(s[pos]) and s[pos] != '+' and s[pos] != '-') pos -= 1;
        // 判断这个下标属于哪一种情况
        long long res = 0;
        bool flag = false;
        // 标记是因为什么退出循环
        for (int i = pos + 1; i < s.size(); i++) {
            if (isdigit(s[i])) {
                res = res * 10 + (s[i] - '0');
                if (res > INT_MAX) {
                    flag = true;
                    break;
                }
                // 如果大于了INT_MAX直接跳出循环
            }
            else break;
        }
        res = min(res, 1ll * INT_MAX);
        if (pos == -1) return res;
        else{
            if (s[pos] == '+' or s[pos] == ' ') return res;
            else if (s[pos] == '-') {
                if (flag) {
                    if (res == INT_MAX) return INT_MIN;
                } else {
                    if (res == INT_MAX) return -1 * INT_MAX;
                    else return res * -1;
                }
            } else {
                return 0;
            }
        }  
        // 这里特判一下各种跳出来的情况就可以
        return 0;
    }
};

时空复杂度分析

本题而言

时间复杂度: $O(1)O(1)$

理由如下: 字符串的长度最大$100100$

空间复杂度: $O(1)O(1)$

理由如下: 少量常数级别变量空间

代码而言

时间复杂度: $O(n)O(n)$

理由如下: 遍历字符串的长度

空间复杂度: $O(1)O(1)$

理由如下: 少量常数级别变量空间

解法二：

实现思路

我们可以使用Python来解决这个问题，因为Python本身就是带有大整数

代码分析

class Solution:
    def StrToInt(self, s: str) -> int:
        if len(s) == 0: return 0
        pos = -1
        for i in range(0, len(s)):
            if s[i] != ' ':
                pos = i
                break
#         找打第一个非空的字符
        flag = 0
        if s[pos].isdigit():
            flag = 1
            pos -= 1
        else:
            if s[pos] != '-' and s[pos] != '+':
                flag = 1
                pos -= 1
#         判断这个字符是什么
        res = 0
        for i in range(pos + 1, len(s)):
            if not s[i].isdigit():
                break
            res = res * 10 + ord(s[i]) - 48
            
#         求取值
        if flag != 0: pos += 1
        if s[pos] == '-':
            if res > 2**31:
                return -2**31
            else:
                return -res
        else:
            if res > 2**31 - 1:
                return 2**31 - 1
            else:
                return res
#         根据不同值和符号判断
        return 0
            

时空复杂度分析

本题而言

时间复杂度: $O(1)O(1)$

理由如下: 字符串的长度最大$100100$

空间复杂度: $O(1)O(1)$

理由如下: 少量常数级别变量空间

代码而言

时间复杂度: $O(n)O(n)$

理由如下: 遍历字符串的长度

空间复杂度: $O(1)O(1)$

理由如下: 少量常数级别变量空间