题目地址：

https://leetcode.com/problems/string-to-integer-atoi/

给定一个字符串$s$，实现atoi函数。如果得数大于了$2^{31}-1$则返回$2^{31}-1$，如果得数小于了$-2^{31}$则返回$-2^{31}$。

先略过空格，再判断正负，然后开始parse字符串。在不使用long long的前提下，我们需要判断溢出。假设当前得到的数是$n$（不考虑符号，即$n\ge 0$），当前看到的字符的数是$x$，那么当$10n+x>2^{31}-1$的时候发生正溢出，这个等价于$n>\lfloor \frac{2^{31}-1-x}{10}\rfloor$；当$-10n-x<-2^{31}$的时候发生负溢出，等价于$-n<\lfloor \frac{-2^{31}+x}{10}\rfloor$。另外还需要注意一点，当$n$被parse成$2^{31}$的时候也会发生溢出，因为int的范围正数比负数少$1$个数，所以如果在没发生溢出的情况下，出现了$n$变成$2^{31}$的情况，也需要返回$-2^{31}$。代码如下：

class Solution {
 public:
  int myAtoi(string s) {
    int k = 0;
    while (k < s.size() && s[k] == ' ') k++;
    if (k == s.size()) return 0;

    int sign = 1;
    if (s[k] == '-') sign = -1, k++;
    else if (s[k] == '+') k++;

    int res = 0;
    for ( ; k < s.size() && '0' <= s[k] && s[k] <= '9'; k++) {
      int x = s[k] - '0';
      if (sign == 1 && res > (INT_MAX - x) / 10) return INT_MAX;
      if (sign == -1 && -res < (INT_MIN + x) / 10) return INT_MIN;
      if (-res * 10 - x == INT_MIN) return INT_MIN;
      res = res * 10 + x;
    }
    return sign * res;
  }
};

时间复杂度$O(l_s)$，空间$O(1)$。