[劍指offer]面試題第[67]題[Leetcode][JAVA][第8題] 字元串轉換整數 (atoi)[字元串]

【問題描述】

請你來實作一個 atoi 函數，使其能将字元串轉換成整數。

首先，該函數會根據需要丢棄無用的開頭空格字元，直到尋找到第一個非空格的字元為止。接下來的轉化規則如下：

如果第一個非空字元為正或者負号時，則将該符号與之後面盡可能多的連續數字字元組合起來，形成一個有符号整數。
假如第一個非空字元是數字，則直接将其與之後連續的數字字元組合起來，形成一個整數。
該字元串在有效的整數部分之後也可能會存在多餘的字元，那麼這些字元可以被忽略，它們對函數不應該造成影響。
注意：假如該字元串中的第一個非空格字元不是一個有效整數字元、字元串為空或字元串僅包含空白字元時，則你的函數不需要進行轉換，即無法進行有效轉換。

在任何情況下，若函數不能進行有效的轉換時，請傳回 0 。

提示：

本題中的空白字元隻包括空格字元 ' ' 。
假設我們的環境隻能存儲 32 位大小的有符号整數，那麼其數值範圍為 [−231,  231 − 1]。如果數值超過這個範圍，請傳回  INT_MAX (231 − 1) 或 INT_MIN (−231) 。

示例:

輸入: "-91283472332"
輸出: -2147483648
解釋: 數字 "-91283472332" 超過 32 位有符号整數範圍。 
     是以傳回 INT_MIN (−231) 。
           

【解答思路】

1. 考慮所有情況 空格 符号 是否數字 上界

時間複雜度：O(N) 空間複雜度：O(1)

特别注意：

1、由于題目中說「環境隻能儲存 32 位整數」，是以這裡在每一輪循環之前先要檢查乘以 1010 以後是否溢出，具體細節請見編碼。

2、Java 、Python 和 C++ 字元串的設計都是不可變的，即使用 trim() 會産生新的變量，是以我們盡量不使用庫函數，使用一個變量 index 去做周遊，這樣周遊完成以後就得到轉換以後的數值。

威威的工程代碼

public class Solution {

    public int myAtoi(String str) {
        int len = str.length();
        // str.charAt(i) 方法回去檢查下标的合法性，一般先轉換成字元數組
        char[] charArray = str.toCharArray();

        // 1、去除前導空格
        int index = 0;
        while (index < len && charArray[index] == ' ') {
            index++;
        }

        // 2、如果已經周遊完成（針對極端用例 "      "）
        if (index == len) {
            return 0;
        }

        // 3、如果出現符号字元，僅第 1 個有效，并記錄正負
        int sign = 1;
        char firstChar = charArray[index];
        if (firstChar == '+') {
            index++;
        } else if (firstChar == '-') {
            index++;
            sign = -1;
        }

        // 4、将後續出現的數字字元進行轉換
        // 不能使用 long 類型，這是題目說的
        int res = 0;
        while (index < len) {
            char currChar = charArray[index];
            // 4.1 先判斷不合法的情況
            if (currChar > '9' || currChar < '0') {
                break;
            }

            // 題目中說：環境隻能存儲 32 位大小的有符号整數，是以，需要提前判：斷乘以 10 以後是否越界
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (currChar - '0') > Integer.MAX_VALUE % 10)) {
                return Integer.MAX_VALUE;
            }
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (currChar - '0') > -(Integer.MIN_VALUE % 10))) {
                return Integer.MIN_VALUE;
            }

            // 4.2 合法的情況下，才考慮轉換，每一步都把符号位乘進去
            res = res * 10 + sign * (currChar - '0');
            index++;
        }
        return res;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String str = "2147483646";
        int res = solution.myAtoi(str);
        System.out.println(res);

        System.out.println(Integer.MAX_VALUE);
        System.out.println(Integer.MIN_VALUE);
    }
}

作者：liweiwei1419
連結：https://leetcode-cn.com/problems/string-to-integer-atoi/solution/jin-liang-bu-shi-yong-ku-han-shu-nai-xin-diao-shi-/

           

2. 時間複雜度：O(N) 空間複雜度：O(1)

甜姨的刀法

public class Solution {
    public int myAtoi(String str) {
        char[] chars = str.toCharArray();
        int n = chars.length;
        int idx = 0;
        while (idx < n && chars[idx] == ' ') {
            // 去掉前導空格
            idx++;
        }
        if (idx == n) {
            //去掉前導空格以後到了末尾了
            return 0;
        }
        boolean negative = false;
        if (chars[idx] == '-') {
            //遇到負号
            negative = true;
            idx++;
        } else if (chars[idx] == '+') {
            // 遇到正号
            idx++;
        } else if (!Character.isDigit(chars[idx])) {
            // 其他符号
            return 0;
        }
        int ans = 0;
        while (idx < n && Character.isDigit(chars[idx])) {
            int digit = chars[idx] - '0';
            if (ans > (Integer.MAX_VALUE - digit) / 10) {
                // 本來應該是 ans * 10 + digit > Integer.MAX_VALUE
                // 但是 *10 和 + digit 都有可能越界，所有都移動到右邊去就可以了。
                return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            ans = ans * 10 + digit;
            idx++;
        }
        return negative? -ans : ans;
    }
}

作者：sweetiee
連結：https://leetcode-cn.com/problems/string-to-integer-atoi/solution/java-zi-fu-chuan-zhuan-zheng-shu-hao-dong-by-sweet/

           

3.思路

class Solution {
    public int strToInt(String str) {
        char[] c = str.trim().toCharArray();
        if(c.length == 0) return 0;
        int res = 0, bndry = Integer.MAX_VALUE / 10;
        int i = 1, sign = 1;
        if(c[0] == '-') sign = -1;
        else if(c[0] != '+') i = 0;
        for(int j = i; j < c.length; j++) {
            if(c[j] < '0' || c[j] > '9') break;
            //c[j] > '7' 這裡處理很巧妙，判斷 > '7' , 看似沒有考慮 MIN, 但其實無論是 = '8' ,還是 >'8',傳回的都是MIN。 學習了
            if(res > bndry || res == bndry && c[j] > '7') return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            res = res * 10 + (c[j] - '0');
        }
        return sign * res;
    }
}

作者：jyd
連結：https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/solution/mian-shi-ti-67-ba-zi-fu-chuan-zhuan-huan-cheng-z-4/
來源：力扣（LeetCode）

           

【總結】

1.威威&&甜姨工作心得

-有現成的工具和類庫需盡量使用，因為它們是性能更優，且經過更嚴格測試，是相對可靠的；

-能抽取成工具類、工具方法的盡量抽取，以突出主幹邏輯、友善以後代碼複用；

-不得不寫得比較繁瑣、冗長的時候，需要寫清楚注釋、展現邏輯層次，以便上線以後排查問題和後續維護

-等真正工作以後，盡可能地調用jdk的方法，比如Character.isDigit。如果沒有你想要的api，也要盡量使用guava，apache common等常見的utils包，盡量不要自己造輪子

2. 提前量思想（生活也得如此）

判斷越界 可以考慮打提前量

if (ans > (Integer.MAX_VALUE - digit) / 10) {
                // 本來應該是 ans * 10 + digit > Integer.MAX_VALUE
                // 但是 *10 和 + digit 都有可能越界，所有都移動到右邊去就可以了。
                return negative? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }