Algorithm String to Integer

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: [−231, 231 − 1]. If the numerical value is out of the range of representable values, INT_MAX (231 − 1) or INT_MIN (−231) is returned.

Example1

Input "42"
Output 42

Example2

Input " -42"
Output 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 is return

Submission

public class Atoi {
  public int myAtoi(String str) {
    str = str.trim();
    if (str.length() == 0) {
      return 0;
    }
    int index = 0;
    int res = 0;
    boolean negative = false;

    if (str.charAt(0) == '-') {
      negative = true;
      index ++;
    } else if (str.charAt(0) == '+') {
      negative = false;
      index ++;
    }
    while (index < str.length()) {
      if (isDigit(str.charAt(index))) {
        int val = str.charAt(index) - '0';
        // detect over-flow
        if (res > (Integer.MAX_VALUE - val) / 10) {
          return negative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
        }
        res = res * 10 + val;
      } else {
        break;
      }
      index ++;
    }
    return negative ? -res : res;

  }

  private static boolean isDigit(char s) {
    if (s < '0' || s > '9') {
      return false;
    }
    return true;
  }
}

Solution

将给定的字符串转换为数字类型，但是根据描述规定，有几个特殊的地方需要注意

从左到右遍历，进行trim处理，空格忽略掉

遇见非 whitespace的char时，如果不满足数字的要求，即，既非数字也不是+ - 符号，此时直接返回 0

截掉字符串序列在数字后非数字的字符，只对有效字符进行解析

代码逻辑是

对遇到的第一个非空格字符进行判断，用以标记数字的正负值，默认为正

根据index递增继续遍历，基于 res = res * 10 + value, 其中 value为当前遍历到的字符对应的十进制数值

需要注意的是，必须判断是否会发生溢出，即要求 res * 10 + value < Integer.MAX_VALUE，所以我们先判断 res 是否是 res > (Integer.MAX_VALUE) - value / 10，如果即将溢出，直接返回对应正负值的最大最小值