题目描述

原题

Description:
Implement atoi which converts a string to an integer.

The function first discards as many whitespace characters as necessary until the first non-whitespace character is found.

Then, starting from this character, takes an optional initial plus or minus sign followed by as many numerical digits as possible, and interprets them as a numerical value.

The string can contain additional characters after those that form the integral number, which are ignored and have no effect on the behavior of this function.

If the first sequence of non-whitespace characters in str is not a valid integral number, or if no such sequence exists because either str is empty or it contains only whitespace characters, no conversion is performed.

If no valid conversion could be performed, a zero value is returned.

Note:
Only the space character ‘ ‘ is considered as whitespace character.

Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^(31), 2^(31) − 1].

If the numerical value is out of the range of representable values, INT_MAX (2^(31) − 1) or INT_MIN (−2^(31)) is returned.

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:

Input: “-91283472332”
Output: -2147483648
Explanation: The number “-91283472332” is out of the range of a 32-bit signed integer.
Thefore INT_MIN (−2^(31)) is returned.

原题翻译

Description:
实现将字符串转换为整数的atoi。

该函数首先丢弃所需数量的空白字符，直到找到第一个非空白字符。

然后，从该字符开始，采用可选的初始加号或减号，后跟尽可能多的数字，并将它们解释为数值。

字符串可以包含在形成整数之后的其他字符，这些字符将被忽略并且对此函数的行为没有影响。

如果str中的第一个非空白字符序列不是有效的整数，或者由于str是空的或者只包含空白字符而不存在这样的序列，则不执行转换。

如果无法执行有效转换，则返回零值。

Note:
只有空格字符’ ‘被视为空格字符。

假设我们正在处理一个只能在32位有符号整数范围内存储整数的环境：[-2^(31), 2^(31) - 1]。

如果数值超出可表示值的范围，则返回INT_MAX（2^(31)-1）或INT_MIN（-2^(31)）。

例1:

输入: “42”
输出: 42

例2:

输入: “ -42”
输出: -42
解释: 第一个非空白字符是’ - ‘，这是减号。
然后取尽可能多的数字，得到42。

Example 3:

Input: “4193 with words”
Output: 4193
Explanation: 转换在数字’3’处停止，因为下一个字符不是数字。

Example 4:

Input: “words and 987”
Output: 0
Explanation: 第一个非空白字符是’w’，它不是数字或+/-符号。
因此，无法执行有效的转换。

Example 5:

Input: “-91283472332”
Output: -2147483648
Explanation: 数字“-91283472332”超出32位有符号整数的范围。
返回INT_MIN（-2^(31)）之前。

解法一(mine)

运行速度：超过了100%的解答。

内存使用：超过了100%的解答。

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
37
38
39
40
41
42
43
44
45
46
public class Solution {
    public int myAtoi(String str) {
        if (str.equals(""))
            return 0;
        char[] chars = str.toCharArray();
        int len = chars.length;
        int result = 0;
        int i = 0;
        while (i != len - 1 && (chars[i] == '\0' || chars[i] == ' ')) {
            ++i;
        }
        boolean flag = true; //结果是否为正
        if (i == len)
            return 0;
        if (chars[i] == '-') {
            flag = false;
            ++i;
        } else if (chars[i] == '+') {
            ++i;
        }
        while (i < chars.length && chars[i] != '\0' && chars[i] != ' ') {
            if (chars[i] >= '0' && chars[i] <= '9') {
                // 验证是否超过int的最大值
                int now = chars[i] - '0';
                int temp = result * 10 + now;
                if ((temp > 0 && result < 0) || (temp < 0 && result > 0)
                    || result != (temp - now) / 10) {
                    if (flag) {
                        return Integer.MAX_VALUE;
                    } else {
                        return Integer.MIN_VALUE;
                    } 
                }
                result = temp;
            } else {
                break;
            }
            ++i;
        }
        if (flag) {
            return result;
        } else {
            return -result;
        }
    }
}

解法二

第一名答案

运行速度：超过了100%的解答。

内存使用：超过了100%的解答。

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
37
public class Solution {
    public int myAtoi(String str) {
        if (str == null) 
            return 0;

        str = str.trim();

        if (str.length() == 0) 
             return 0;

        char[] chArray = str.toCharArray();
        int sign = 1;
        int i = 0;
        if (chArray[0] == '+') {
            sign = 1;
            i++;
        } else if (chArray[0] == '-') {
             sign = -1;
             i++;
        }

        int result = 0;
        while (i < chArray.length) {
            int digit = chArray[i] - '0';
            if (digit < 0 || digit > 9) {
                return sign * result;
            }
            if (result > Integer.MAX_VALUE / 10 || 
                (result == Integer.MAX_VALUE / 10 && Integer.MAX_VALUE % 10 < digit)) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            result = result * 10 + digit;
            i++;
        }
        return sign * result;
    }
}