题面
原题挺长的,还是英文,就不抄了,😄。
给定字符串,可能由若干个空格开头,之后可能会跟一串数组,数字可能由-/+开头,之后会跟有若干其他字母,找出并计算该数字并返回。
Note: 超出INT_MAX 和 INT_MIN 返回它俩。(所以考虑用更大类型来暂存中间结果。)
样例
Example 1:正常例子
Input: "42" Output: 42Example 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 };