LeetCode 8 - String to Integer (atoi)


LeetCode – String to Integer (atoi) (Java)
mplement atoi to convert a string to an integer.
Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.
1. null or empty string
2. white spaces
3. +/- sign
4. calculate real value
5. handle min & max


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. If the correct value is out of the range of representable values, INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
http://www.cnblogs.com/grandyang/p/4125537.html
字符串转为整数是很常用的一个函数,由于输入的是字符串,所以需要考虑的情况有很多种。我之前有一篇文章是关于验证一个字符串是否为数字的,参见 Valid Number。在那篇文章中,详细的讨论了各种情况,包括符号,自然数,小数点的出现位置,判断他们是否是数字。个人以为这道题也应该有这么多种情况。但是这题只需要考虑数字和符号的情况:
1. 若字符串开头是空格,则跳过所有空格,到第一个非空格字符,如果没有,则返回0.
2. 若第一个非空格字符是符号+/-,则标记sign的真假,这道题还有个局限性,那就是在c++里面,+-1和-+1都是认可的,都是-1,而在此题里,则会返回0.
3. 若下一个字符不是数字,则返回0. 完全不考虑小数点和自然数的情况,不过这样也好,起码省事了不少。
4. 如果下一个字符是数字,则转为整形存下来,若接下来再有非数字出现,则返回目前的结果。
5. 还需要考虑边界问题,如果超过了整形数的范围,则用边界值替代当前值。
    public int myAtoi(String str) {
        if (str.isEmpty()) return 0;
        int sign = 1, base = 0, i = 0, n = str.length();
        while (i < n && str.charAt(i) == ' ') ++i;
        if (i < n && (str.charAt(i) == '+' || str.charAt(i) == '-')) {
            sign = (str.charAt(i++) == '+') ? 1 : -1;
        }
        while (i < n && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
            if (base > Integer.MAX_VALUE / 10 || (base == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)) {
                return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            base = 10 * base + (str.charAt(i++) - '0');
        }
        return base * sign;
    }
http://www.jiuzhang.com/solutions/string-to-integer-atoi/
   public int myAtoi(String str) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(str == null) {
            return 0;
        }
        str = str.trim();
        if (str.length() == 0) {
            return 0;
        }
            
        int sign = 1;
        int index = 0;
    
        if (str.charAt(index) == '+') {
            index++;
        } else if (str.charAt(index) == '-') {
            sign = -1;
            index++;
        }
        long num = 0;
        for (; index < str.length(); index++) {
            if (str.charAt(index) < '0' || str.charAt(index) > '9')
                break;
            num = num * 10 + (str.charAt(index) - '0');
            if (num > Integer.MAX_VALUE ) {
                break;
            }
        }   
        if (num * sign >= Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (num * sign <= Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int)num * sign;
    }
http://www.programcreek.com/2012/12/leetcode-string-to-integer-atoi/
public int atoi(String str) {
 if (str == null || str.length() < 1)
  return 0;
 
 // trim white spaces
 str = str.trim();
 
 char flag = '+';
 
 // check negative or positive
 int i = 0;
 if (str.charAt(0) == '-') {
  flag = '-';
  i++;
 } else if (str.charAt(0) == '+') {
  i++;
 }
 // use double to store result
 double result = 0; //\\ use long
 
 // calculate value
 while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {//\\
  result = result * 10 + (str.charAt(i) - '0');
  i++;
 }

 if (flag == '-')
  result = -result;

 // handle max and min
 if (result > Integer.MAX_VALUE)
  return Integer.MAX_VALUE;
 if (result < Integer.MIN_VALUE)
  return Integer.MIN_VALUE;
 
 return (int) result;
}
http://blog.csdn.net/linhuanmars/article/details/21145129
这道题还是对于Integer的处理,在Reverse Integer这道题中我有提到,这种题的考察重点并不在于问题本身,而是要注意corner case的处理,整数一般有两点,一个是正负符号问题,另一个是整数越界问题。思路比较简单,就是先去掉多余的空格字符,然后读符号(注意正负号都有可能,也有可能没有符号),接下来按顺序读数字,结束条件有三种情况:(1)异常字符出现(按照C语言的标准是把异常字符起的后面全部截去,保留前面的部分作为结果);(2)数字越界(返回最接近的整数);(3)字符串结束。

public int atoi(String str) {
    if(str==null)
    {
        return 0;
    }
    str = str.trim();
    if(str.length()==0)
        return 0;
    boolean isNeg = false;
    int i = 0;
    if(str.charAt(0)=='-' || str.charAt(0)=='+')
    {
        i++;
        if(str.charAt(0)=='-')
            isNeg = true;
    }
    int res = 0;
    while(i<str.length())
    {
        if(str.charAt(i)<'0'||str.charAt(i)>'9')
            break;
        int digit = (int)(str.charAt(i)-'0');
        if(isNeg && res>-((Integer.MIN_VALUE+digit)/10))//\\
            return Integer.MIN_VALUE;
        else if(!isNeg && res>(Integer.MAX_VALUE-digit)/10)//\\
            return Integer.MAX_VALUE;
        res = res*10+digit;
        i++;
    }
    return isNeg?-res:res;
}
public static int myAtoi(String str) { if (str == null || str.length() == 0) return 0;// str = str.trim(); char firstChar = str.charAt(0); int sign = 1, start = 0, len = str.length(); long sum = 0; if (firstChar == '+') { sign = 1; start++; } else if (firstChar == '-') { sign = -1; start++; } for (int i = start; i < len; i++) { if (!Character.isDigit(str.charAt(i))) return (int) sum * sign; sum = sum * 10 + str.charAt(i) - '0'; if (sign == 1 && sum > Integer.MAX_VALUE) return Integer.MAX_VALUE; if (sign == -1 && (-1) * sum < Integer.MIN_VALUE) return Integer.MIN_VALUE; } return (int) sum * sign; }
http://www.cnblogs.com/springfor/p/3896499.html
因为遇见过了atol,string to long 这样的问题,就不能用这种比当前数据类型长的方法解决。
另一种方法是更加普遍和巧妙的,就是用这样的判断:
1. Integer.MAX_VALUE/10 < result; //当前转换结果比Integer中最大值/10还大(因为这个判断放在while循环最开始,之后还要对result进行*10+当前遍历元素的操作,所以如果还乘10的result已经比Integer.MAX_VALUE/10还大,可想而知,乘了10更大)
2. Integer.MAX_VALUE/10 == result && Integer.MAX_VALUE%10 <(str.charAt(i) - '0') //另外的情况就是,当前result恰跟 Integer.MAX_VALUE/10相等,那么就判断当前遍历的元素值跟最大值的最后一位的大小关系即可
 1   public int atoi(String str) {
 2     if (str == null || str.length() < 1)
 3         return 0;
 4  
 5     // trim white spaces at beginning and end
 6     str = str.trim();
 7  
 8     char flag = '+';
 9  
10     // check negative or positive
11     int i = 0;
12     if (str.charAt(0) == '-') {
13         flag = '-';
14         i++;
15     } else if (str.charAt(0) == '+') {
16         i++;
17     }
18     // use double to store result
19     int result = 0;
20  
21     // calculate value
22     while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
23         if(Integer.MAX_VALUE/10 < result || (Integer.MAX_VALUE/10 == result && Integer.MAX_VALUE%10 < (str.charAt(i) - '0'))) //\\
24             return flag == '-' ? Integer.MIN_VALUE : Integer.MAX_VALUE;
25             
26         result = result * 10 + (str.charAt(i) - '0');
27         i++;
28     }
29  
30     if (flag == '-')
31         result = -result;
32  
33     return result;
34 }

http://jane4532.blogspot.com/2013/09/string-to-integerleetcode.html
http://www.cnblogs.com/springfor/p/3896499.html
Cache/pre-compute Integer.MAX_VALUE/10, Integer.MAX_VALUE%10
另一种方法是更加普遍和巧妙的,就是用这样的判断:
1. Integer.MAX_VALUE/10 < result; //当前转换结果比Integer中最大值/10还大(因为这个判断放在while循环最开始,之后还要对result进行*10+当前遍历元素的操作,所以如果还乘10的result已经比Integer.MAX_VALUE/10还大,可想而知,乘了10更大)
2. Integer.MAX_VALUE/10 == result && Integer.MAX_VALUE%10 <(str.charAt(i) - '0') //另外的情况就是,当前result恰跟 Integer.MAX_VALUE/10相等,那么就判断当前遍历的元素值跟最大值的最后一位的大小关系即可
1   public int atoi(String str) {
 2     if (str == null || str.length() < 1)
 3         return 0;
 4  
 5     // trim white spaces at beginning and end
 6     str = str.trim();
 7  
 8     char flag = '+';
 9  
10     // check negative or positive
11     int i = 0;
12     if (str.charAt(0) == '-') {
13         flag = '-';
14         i++;
15     } else if (str.charAt(0) == '+') {
16         i++;
17     }
18     // use double to store result
19     int result = 0;
20  
21     // calculate value
22     while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
23         if(Integer.MAX_VALUE/10 < result || (Integer.MAX_VALUE/10 == result && Integer.MAX_VALUE%10 < (str.charAt(i) - '0'))) //\\
24             return flag == '-' ? Integer.MIN_VALUE : Integer.MAX_VALUE;
26         result = result * 10 + (str.charAt(i) - '0');
27         i++;
28     }
29  
30     if (flag == '-')
31         result = -result;
32  
33     return result;
34 }
II:
1    public int atoi(String str) {
 2     if (str == null || str.length() < 1)
 3         return 0;
 4  
 5     // trim white spaces
 6     str = str.trim();
 7  
 8     char flag = '+';
 9  
10     // check negative or positive
11     int i = 0;
12     if (str.charAt(0) == '-') {
13         flag = '-';
14         i++;
15     } else if (str.charAt(0) == '+') {
16         i++;
17     }
18     // use double to store result
19     double result = 0;
20  
21     // calculate value
22     while (str.length() > i && str.charAt(i) >= '0' && str.charAt(i) <= '9') {
23         result = result * 10 + (str.charAt(i) - '0');
24         i++;
25     }
26  
27     if (flag == '-')
28         result = -result;
29  
30     // handle max and min
31     if (result > Integer.MAX_VALUE)
32         return Integer.MAX_VALUE;
33  
34     if (result < Integer.MIN_VALUE)
35         return Integer.MIN_VALUE;
36  
37     return (int) result;
38 }

https://leetcode.com/discuss/8886/my-simple-solution
I think we only need to handle four cases:
  1. discards all leading whitespaces
  2. sign of the number
  3. overflow
  4. invalid input
public static int myAtoi(String str) { if (str.isEmpty()) return 0; int sign = 1, base = 0, i = 0; while (str.charAt(i) == ' ') i++; if (str.charAt(i) == '-' || str.charAt(i) == '+') sign = str.charAt(i++) == '-' ? -1 : 1; while (i < str.length() && str.charAt(i) >= '0' && str.charAt(i) <= '9') { if (base > Integer.MAX_VALUE / 10 || (base == Integer.MAX_VALUE / 10 && str.charAt(i) - '0' > 7)) { return (sign == 1) ? Integer.MAX_VALUE : Integer.MIN_VALUE; } base = 10 * base + (str.charAt(i++) - '0'); } return base * sign; }
http://n00tc0d3r.blogspot.com/2013/06/string-to-integer-atoi.html
If we are allowed to use Java regex (FYI, here is a tutorial of Java Regex), then we can remove leading whitespace and trailing invalid characters using replaceAll method of String class.
 public int atoi(String str) {  
   // use regex to validate the input  
   String pattern = "(^\\s*)([+-]?[0-9]+)(.*$)";  
   if (!str.matches(pattern)) return 0;  
   // trim the string to [+-]?[0-9]+  
   String numstr = str.replaceAll(pattern, "$2");  
   
   // convert string to integer  
   int sign = (numstr.charAt(0) == '-') ? -1 : 1;  
   long res = 0;  
   for (int i = (numstr.charAt(0) == '+' || numstr.charAt(0) == '-') ? 1 : 0; i<numstr.length(); ++i) {  
     res = res * 10 + (numstr.charAt(i) - '0');  
     if (sign > 0 && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;  
     else if (sign < 0 && res * (-1) < Integer.MIN_VALUE) return Integer.MIN_VALUE;  
   }  
   return (int)res*sign;  
 }
If we are not allowed to use replaceAll method, we need to iterate the input string character by character.
 public int atoi(String str) {  
   long res = 0; int index = 0;  
   // trim leading whitespace  
   while (index < str.length() && str.charAt(index) == ' ') ++index;  
   if (index == str.length()) return (int)res;  
   // get sign  
   int sign = 1;  
   if (str.charAt(index) == '-') {  
     ++index;  
     sign = -1;  
   } else if (str.charAt(index) == '+') {  
     ++index;  
   }  
   
   // convert digits  
   while (index < str.length() && Character.isDigit(str.charAt(index))) {  
     res = res * 10 + (str.charAt(index++) - '0');  
     if (sign > 0 && res > Integer.MAX_VALUE) return Integer.MAX_VALUE;  
     else if (sign < 0 && res * (-1) < Integer.MIN_VALUE) return Integer.MIN_VALUE;  
   }  
   return (int)res*sign;  
 }
Read full article from LeetCode – String to Integer (atoi) (Java)

Labels

LeetCode (1432) GeeksforGeeks (1122) LeetCode - Review (1067) Review (882) Algorithm (668) to-do (609) Classic Algorithm (270) Google Interview (237) Classic Interview (222) Dynamic Programming (220) DP (186) Bit Algorithms (145) POJ (141) Math (137) Tree (132) LeetCode - Phone (129) EPI (122) Cracking Coding Interview (119) DFS (115) Difficult Algorithm (115) Lintcode (115) Different Solutions (110) Smart Algorithm (104) Binary Search (96) BFS (91) HackerRank (90) Binary Tree (86) Hard (79) Two Pointers (78) Stack (76) Company-Facebook (75) BST (72) Graph Algorithm (72) Time Complexity (69) Greedy Algorithm (68) Interval (63) Company - Google (62) Geometry Algorithm (61) Interview Corner (61) LeetCode - Extended (61) Union-Find (60) Trie (58) Advanced Data Structure (56) List (56) Priority Queue (53) Codility (52) ComProGuide (50) LeetCode Hard (50) Matrix (50) Bisection (48) Segment Tree (48) Sliding Window (48) USACO (46) Space Optimization (45) Company-Airbnb (41) Greedy (41) Mathematical Algorithm (41) Tree - Post-Order (41) ACM-ICPC (40) Algorithm Interview (40) Data Structure Design (40) Graph (40) Backtracking (39) Data Structure (39) Jobdu (39) Random (39) Codeforces (38) Knapsack (38) LeetCode - DP (38) Recursive Algorithm (38) String Algorithm (38) TopCoder (38) Sort (37) Introduction to Algorithms (36) Pre-Sort (36) Beauty of Programming (35) Must Known (34) Binary Search Tree (33) Follow Up (33) prismoskills (33) Palindrome (32) Permutation (31) Array (30) Google Code Jam (30) HDU (30) Array O(N) (29) Logic Thinking (29) Monotonic Stack (29) Puzzles (29) Code - Detail (27) Company-Zenefits (27) Microsoft 100 - July (27) Queue (27) Binary Indexed Trees (26) TreeMap (26) to-do-must (26) 1point3acres (25) GeeksQuiz (25) Merge Sort (25) Reverse Thinking (25) hihocoder (25) Company - LinkedIn (24) Hash (24) High Frequency (24) Summary (24) Divide and Conquer (23) Proof (23) Game Theory (22) Topological Sort (22) Lintcode - Review (21) Tree - Modification (21) Algorithm Game (20) CareerCup (20) Company - Twitter (20) DFS + Review (20) DP - Relation (20) Brain Teaser (19) DP - Tree (19) Left and Right Array (19) O(N) (19) Sweep Line (19) UVA (19) DP - Bit Masking (18) LeetCode - Thinking (18) KMP (17) LeetCode - TODO (17) Probabilities (17) Simulation (17) String Search (17) Codercareer (16) Company-Uber (16) Iterator (16) Number (16) O(1) Space (16) Shortest Path (16) itint5 (16) DFS+Cache (15) Dijkstra (15) Euclidean GCD (15) Heap (15) LeetCode - Hard (15) Majority (15) Number Theory (15) Rolling Hash (15) Tree Traversal (15) Brute Force (14) Bucket Sort (14) DP - Knapsack (14) DP - Probability (14) Difficult (14) Fast Power Algorithm (14) Pattern (14) Prefix Sum (14) TreeSet (14) Algorithm Videos (13) Amazon Interview (13) Basic Algorithm (13) Codechef (13) Combination (13) Computational Geometry (13) DP - Digit (13) LCA (13) LeetCode - DFS (13) Linked List (13) Long Increasing Sequence(LIS) (13) Math-Divisible (13) Reservoir Sampling (13) mitbbs (13) Algorithm - How To (12) Company - Microsoft (12) DP - Interval (12) DP - Multiple Relation (12) DP - Relation Optimization (12) LeetCode - Classic (12) Level Order Traversal (12) Prime (12) Pruning (12) Reconstruct Tree (12) Thinking (12) X Sum (12) AOJ (11) Bit Mask (11) Company-Snapchat (11) DP - Space Optimization (11) Dequeue (11) Graph DFS (11) MinMax (11) Miscs (11) Princeton (11) Quick Sort (11) Stack - Tree (11) 尺取法 (11) 挑战程序设计竞赛 (11) Coin Change (10) DFS+Backtracking (10) Facebook Hacker Cup (10) Fast Slow Pointers (10) HackerRank Easy (10) Interval Tree (10) Limited Range (10) Matrix - Traverse (10) Monotone Queue (10) SPOJ (10) Starting Point (10) States (10) Stock (10) Theory (10) Tutorialhorizon (10) Kadane - Extended (9) Mathblog (9) Max-Min Flow (9) Maze (9) Median (9) O(32N) (9) Quick Select (9) Stack Overflow (9) System Design (9) Tree - Conversion (9) Use XOR (9) Book Notes (8) Company-Amazon (8) DFS+BFS (8) DP - States (8) Expression (8) Longest Common Subsequence(LCS) (8) One Pass (8) Quadtrees (8) Traversal Once (8) Trie - Suffix (8) 穷竭搜索 (8) Algorithm Problem List (7) All Sub (7) Catalan Number (7) Cycle (7) DP - Cases (7) Facebook Interview (7) Fibonacci Numbers (7) Flood fill (7) Game Nim (7) Graph BFS (7) HackerRank Difficult (7) Hackerearth (7) Inversion (7) Kadane’s Algorithm (7) Manacher (7) Morris Traversal (7) Multiple Data Structures (7) Normalized Key (7) O(XN) (7) Radix Sort (7) Recursion (7) Sampling (7) Suffix Array (7) Tech-Queries (7) Tree - Serialization (7) Tree DP (7) Trie - Bit (7) 蓝桥杯 (7) Algorithm - Brain Teaser (6) BFS - Priority Queue (6) BFS - Unusual (6) Classic Data Structure Impl (6) DP - 2D (6) DP - Monotone Queue (6) DP - Unusual (6) DP-Space Optimization (6) Dutch Flag (6) How To (6) Interviewstreet (6) Knapsack - MultiplePack (6) Local MinMax (6) MST (6) Minimum Spanning Tree (6) Number - Reach (6) Parentheses (6) Pre-Sum (6) Probability (6) Programming Pearls (6) Rabin-Karp (6) Reverse (6) Scan from right (6) Schedule (6) Stream (6) Subset Sum (6) TSP (6) Xpost (6) n00tc0d3r (6) reddit (6) AI (5) Abbreviation (5) Anagram (5) Art Of Programming-July (5) Assumption (5) Bellman Ford (5) Big Data (5) Code - Solid (5) Code Kata (5) Codility-lessons (5) Coding (5) Company - WMware (5) Convex Hull (5) Crazyforcode (5) DFS - Multiple (5) DFS+DP (5) DP - Multi-Dimension (5) DP-Multiple Relation (5) Eulerian Cycle (5) Graph - Unusual (5) Graph Cycle (5) Hash Strategy (5) Immutability (5) Java (5) LogN (5) Manhattan Distance (5) Matrix Chain Multiplication (5) N Queens (5) Pre-Sort: Index (5) Quick Partition (5) Quora (5) Randomized Algorithms (5) Resources (5) Robot (5) SPFA(Shortest Path Faster Algorithm) (5) Shuffle (5) Sieve of Eratosthenes (5) Strongly Connected Components (5) Subarray Sum (5) Sudoku (5) Suffix Tree (5) Swap (5) Threaded (5) Tree - Creation (5) Warshall Floyd (5) Word Search (5) jiuzhang (5)

Popular Posts