No.008：String to Integer (atoi)，no.008atoi

No.008：String to Integer (atoi)，no.008atoi

題目：

Implement atoi to convert a string to an integer.
Hint:
Carefully consider all possible input cases.

官方難度：

Easy

翻譯：

實現atoi算法，將一個字符串轉成整數。

提示：仔細考慮各種可能情況。

補充資料：

atoi函數是C語言庫中的一個函數，百度了一下其實現的功能如下：

Requirements for atoi:
1.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.
2.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.
3.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.
4.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.

atoi函數要求：
1.丟棄所有的空白字符串，直到遇到第一個非空格字符串。從那個非空字符串開始，如果第一個是“+”或“-”，盡可能多的返回之後跟的數字。
2.字符串可以在之前的整數後包含其他字符，忽視它，對函數沒有影響，立即結束函數。
3.如果遇到的第一個非空字符串，不是一個整數，甚至於，字符串根本就是空的或完全由空白鍵組成，返回0。
4.如果不能有效轉化，返回0；如果超出整型的最大/最小值，返回整型數的最大/最小值。

思路：

1.用String.trim()方法完成去空格工作，使用String.toCharArray()方法將字符串拆成字符數組。

2.考慮，去空格字符串長度為0情況。

3.用標志位記錄數組第一位可能是操作符"-"或"+"的情況，然後將操作符的位置置為0，便於以後賦值處理。

4.記錄最高位數，開始循環累加，直到遇上非數字，由於考慮超過int表示范圍的情況，sum被聲明為long型。

5.特殊考慮超出范圍的情況。

解題中可能遇到的困難：

1.比較或賦值的時候，時刻注意是char型的，帶上''。

2.char型的字符數字，轉成數字計算array[i] - '0'。

3.Integer.MAX_VALUE和Integer.MIN_VALUE不是相反數的關系。

解題代碼：

1 private static int method(String str) { 2 // 先去空格 3 char[] array = str.trim().toCharArray(); 4 // 0特殊處理 5 if (array.length == 0) { 6 return 0; 7 } 8 // 正負號標志位 9 int operatorFlag = 1; 10 // 記錄返回數字，超過long表示范圍不考慮 11 long sum = 0; 12 if (array[0] == '+' || array[0] == '-' || (array[0] >= '0' && array[0] <= '9')) { 13 // 操作符置0，便於統一處理 14 if (array[0] == '+') { 15 // 這裡賦值，注意是char型的 16 array[0] = '0'; 17 operatorFlag = 1; 18 } else if (array[0] == '-') { 19 array[0] = '0'; 20 operatorFlag = -1; 21 } 22 // 最高位 23 int maxLevel = 0; 24 // 循環確定最高位 25 for (int i = 0; i < array.length; i++) { 26 if (array[i] >= '0' && array[i] <= '9') { 27 maxLevel++; 28 } else { 29 // 遇到非數字退出 30 break; 31 } 32 } 33 // 需要一個maxLevel的副本來賦值 34 int copyMaxLevel = maxLevel; 35 // 累加賦值，注意其實位置的下標 36 for (int i = 0; i < maxLevel; i++) { 37 // 注意char型的數字，轉成數字的處理 38 sum += (array[i] - '0') * Math.pow(10, --copyMaxLevel); 39 } 40 // 超出范圍處理 41 long realNumber = sum * operatorFlag; 42 if (realNumber > Integer.MAX_VALUE) { 43 return Integer.MAX_VALUE; 44 } 45 if (realNumber < Integer.MIN_VALUE) { 46 return Integer.MIN_VALUE; 47 } 48 return (int) realNumber; 49 } else { 50 return 0; 51 } 52 } View Code

測試代碼地址：

https://github.com/Gerrard-Feng/LeetCode/blob/master/LeetCode/src/com/gerrard/algorithm/easy/Q008.java

LeetCode題目地址：

https://leetcode.com/problems/string-to-integer-atoi/

PS：如有不正確或提高效率的方法，歡迎留言，謝謝！