String to Integer

Question

  1. Implement function atoi to convert a string to an integer.
  3. If no valid conversion could be performed, a zero value is returned.
  5. If the correct value is out of the range of representable values,
  6. INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
  8. Example
  9. "10" => 10
  11. "-1" => -1
  13. "123123123123123" => 2147483647
  15. "1.0" => 1

题解

经典的字符串转整数题，边界条件比较多，比如是否需要考虑小数点，空白及非法字符的处理，正负号的处理，科学计数法等。最先处理的是空白字符，然后是正负号，接下来只要出现非法字符(包含正负号，小数点等，无需对这两类单独处理)即退出，否则按照正负号的整数进位加法处理。

Java

  1. public class Solution {
  2.     /**
  3.      * @param str: A string
  4.      * @return An integer
  5.      */
  6.     public int atoi(String str) {
  7.         if (str == null || str.length() == 0) return 0;
  9.         // trim left and right spaces
  10.         String strTrim = str.trim();
  11.         int len = strTrim.length();
  12.         // sign symbol for positive and negative
  13.         int sign = 1;
  14.         // index for iteration
  15.         int i = 0;
  16.         if (strTrim.charAt(i) == '+') {
  17.             i++;
  18.         } else if (strTrim.charAt(i) == '-') {
  19.             sign = -1;
  20.             i++;
  21.         }
  23.         // store the result as long to avoid overflow
  24.         long result = 0;
  25.         while (i < len) {
  26.             if (strTrim.charAt(i) < '0' || strTrim.charAt(i) > '9') {
  27.                 break;
  28.             }
  29.             result = 10 * result + sign * (strTrim.charAt(i) - '0');
  30.             // overflow
  31.             if (result > Integer.MAX_VALUE) {
  32.                 return Integer.MAX_VALUE;
  33.             } else if (result < Integer.MIN_VALUE) {
  34.                 return Integer.MIN_VALUE;
  35.             }
  36.             i++;
  37.         }
  39.         return (int)result;
  40.     }
  41. }

源码分析

符号位使用整型表示，便于后期相乘相加。在 while 循环中需要注意判断是否已经溢出，如果放在 while 循环外面则有可能超过 long 型范围。

复杂度分析

略

Reference