题目描述

请你写一个函数 StrToInt，实现把字符串转换成整数这个功能。

当然，不能使用 atoi 或者其他类似的库函数。

样例

输入："123"

输出：123

注意:

你的函数应满足下列条件：

1. 忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/−’ - 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
2. 整数后可能有任意非数字字符，请将其忽略；
3. 如果整数长度为 0，则返回 0；
4. 如果整数大于 INT_MAX(231−1)，请返回 INT_MAX；如果整数小于INT_MIN(−231) ，请返回 INT_MIN；

算法

(模拟) $O(n)$

按照函数要求进行模拟

分情况讨论

1. 去行首空格
2. 判断是负数还是正数，$is\_minus$ 做标记，除了 ‘+’ ‘-‘ 数字前不能有任何其他字符
3. 对数字字符转换成字符串
4. 处理结束，如果是负数加负号
5. 如果答案超过 $INT\_MAX$ 或 $INT\_MIN$，答案就更新为 $INT\_MAX$ 或 $INT\_MIN$
   注意：答案可能超过 $int$ 所以用 $long \; long$ 存，如果是负数记得加负号

时间复杂度

k 最多遍历整个字符串，所以时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    int strToInt(string str) {
        long long res = 0;
        bool is_minus = false;

        int k = 0;
        while (k < str.size() && str[k] == ' ') k ++ ;

        if (k < str.size() && str[k] == '+') k ++ ;
        if (k < str.size() && str[k] == '-') k ++ , is_minus = true;

        while (k < str.size() && str[k] >= '0' && str[k] <= '9')
        {
            res = res * 10 + str[k] - '0';
            k ++ ;
        }

        if (is_minus) res = -res;
        if (res > INT_MAX) res = INT_MAX;
        if (res < INT_MIN) res = INT_MIN;
        return res;
    }
};