引言
题目链接:https://leetcode.com/problems/string-to-integer-atoi/description/
题目大意
实现一个 atoi函数。输入一串字符串,扫描字符串,跳过前面的空格,直到遇上数字或正负符号才开始做转换,而再遇到非数字或字符串结束时('\0')才结束转换,并将结果返回。
- Example
1 2 3 4 5 6 7 8 9 10 11 12 |
Input: "42" Output: 42 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. 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. |
题解
一句话题解:按照题意模拟流程。遇上第一个非空字符判断是否为正负号并标记,后续继续按位来计算结果,当遇到非数字字符,返回当前结果,并加上符号标记(同时处理下0值返回和数据溢出即可)。
复杂度 O(n)
AC代码
c++版本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
class Solution { public: int myAtoi(string str) { int len = str.length(); if (len < 1) { return 0; } int retSymbol = 1; int retNum = 0; int index = 0; while (index < len && str[index] == ' ') { ++index; } if (index < len && (str[index] == '-' || str[index] == '+')) { retSymbol = 1 - 2 * ('-' == str[index++]); } for (; index < len; ++index) { if (str[index] < '0' || str[index] > '9') { break; } if ((retNum > INT_MAX / 10) || (retNum == INT_MAX / 10 && (str[index] - '0') > INT_MAX % 10)) { return 1 == retSymbol ? INT_MAX : INT_MIN; } retNum = retNum * 10 + str[index] - '0'; } return retSymbol * retNum; } }; |
go版本
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
const ( INT32_MAX = int(^uint32(0) >> 1) INT32_MIN = ^INT32_MAX ) func myAtoi(str string) int { lens := len(str) if lens < 1 { return 0 } retSymbol, retNum, index := 1, 0, 0 for index < lens && str[index] == ' ' { index++ } if index < lens && str[index] == '+' { index++ } else if index < lens && str[index] == '-' { retSymbol = -1 index++ } for ; index < lens; index++ { if str[index] < '0' || str[index] > '9' { break } if retNum > INT32_MAX/10 || (retNum == INT32_MAX/10 && int(str[index]-'0') > INT32_MAX%10) { if 1 == retSymbol { return INT32_MAX } return INT32_MIN } retNum = retNum*10 + int(str[index]-'0') } return retNum * retSymbol } |