题面

原题挺长的,还是英文,就不抄了,😄。

给定字符串,可能由若干个空格开头,之后可能会跟一串数组,数字可能由-/+开头,之后会跟有若干其他字母,找出并计算该数字并返回。

Note: 超出INT_MAX 和 INT_MIN 返回它俩。(所以考虑用更大类型来暂存中间结果。)

样例

Example 1:正常例子

Input: "42"
Output: 42

Example 2:由空格开头的例子

Input: "   -42"
Output: -42
Explanation: The first non-whitespace character is '-', which is the minus sign.
             Then take as many numerical digits as possible, which gets 42.

Example 3:后方还有其他元素的例子

Input: "4193 with words"
Output: 4193
Explanation: Conversion stops at digit '3' as the next character is not a numerical digit.

Example 4:前方有其他元素的例子

Input: "words and 987"
Output: 0
Explanation: The first non-whitespace character is 'w', which is not a numerical 
             digit or a +/- sign. Therefore no valid conversion could be performed.

Example 5:带符号的大数,测试INT_MAX 和 INT_MIN

Input: "-91283472332"
Output: -2147483648
Explanation: The number "-91283472332" is out of the range of a 32-bit signed integer.
             Thefore INT_MIN (−231) is returned.

思路

本题不能从后往前扫的方法来做。考虑的太复杂就会像我一样卡几个小时...

1. 从前往后遍历,先找到第一个不是空格的字符,如果它是“- / +” 记录数字的符号(1/-1);

2. 之后就会是一串数字,我们使用while循环,找出连续的数字,并将其加入到res中(res = res*10 + (str[i]-'0'))

3. 返回res。

这样一来,我们就避开了判断 字符串开始是其他元素(除去正负和数字),以及数字后面还跟有其他元素的情况。该情况需要直接返回0。

时间复杂度:O(n)

源码

 1 class Solution {
 2 public:
 3     int myAtoi(string str) {
 4         int len = str.length();
 5         if(len == 0)
 6             return 0;
 7         
 8         int i = 0, flag = 1;
 9         long res = 0;
10         while(i < len && str[i] == ' ')
11             i++;
12         if(i < len)
13         {
14             if(str[i] == '-' || str[i] == '+')
15             {
16                 flag = (str[i] == '-') ? -1 : 1;
17                 i++;
18             }
19             while(i < len && str[i] >= '0' && str[i] <= '9')
20             {
21                 res = res*10 + (str[i]-'0');
22                 if(res*flag > INT_MAX)
23                     return INT_MAX;
24                 if(res*flag <= INT_MIN)
25                     return INT_MIN;
26                 i++;
27             }
28         }
29         return res*flag;
30     }
31 };