67-把字符串转成整数

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

"42" -> 42

"4123 ddd" > 4123

"words 123" > 0

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

普通遍历方法

可以按照题目叙述直接编写解法，遍历字符，根据不同情况进行处理即可。

    public int strToInt2(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chs = str.toCharArray();
        int idx = 0;
        while(idx < chs.length && chs[idx] == ' '){
            idx++;
        }
        if (idx == chs.length) {
            return 0;
        }
        int start = idx;
        long value = 0;
        boolean isNegative = false;
        if (chs[idx] == '+' || chs[idx] == '-') {
            if (chs[idx] == '-') {
                isNegative = true;
            }
            idx++;
        }
        if (idx == chs.length) {
            return 0;
        }
        while(idx < chs.length && chs[idx] <= '9' && chs[idx] >= '0'){
            value  = value * 10   +  (chs[idx] - '0');
            if (value > Integer.MAX_VALUE + (long)1) {
                value = Integer.MAX_VALUE + (long)1;
            }
            idx++;
        }
        if (idx == start) {
            return 0;
        }
        value = isNegative ? value * -1 : value;

        if (value > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (value < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }
        return (int)value;
    }

有限状态机

有限状态机是指一个系统有若干个状态，通过操作触发状态的转移。

比如上面的状态图，就是A态时，输入1则进入B态，在B态，输入2依然是B态。

有限状态机的关键就是寻找状态和操作，状态之间可能会有一定的重合，不一定是完全正交的，最后确定可接受态。

private char charType(char ch) {
        if (ch >= '0' && ch <= '9') {
            return 'd';
        }else if(ch == ' ' || ch == '+' || ch == '-'){
            return ch;
        }else{
            return 'e';
        }
    }

    public int strToInt(String str) {
        Map<Character,Integer>[] transfer = new Map[]{
                new HashMap<Character,Integer>(){{put(' ',0);put('+',1);put('-',1);put('d',2);}},// 0 空格态
                new HashMap<Character,Integer>(){{put('d',2);}}, //1 符号态
                new HashMap<Character,Integer>(){{put('d',2);put(' ',3);put('+',3);put('-',3);put('e',3);}}, //2 数字态
                new HashMap<Character,Integer>(){{}}, //3 合法结束态 前面有数字

        };
        Integer state = 0;
        char[] chs = str.toCharArray();
        int start = -1,end = -1;
        for (int i = 0; i < chs.length; i++) {
            char ch = chs[i];
            char charType = charType(ch);
            state = transfer[state].get(charType);
            if (state == null) {
                return 0;
            }
            if (state == 3) {
                break;
            }
            if (start == -1 && charType == 'd') {
                start = i;
            }
            if(charType == 'd'){
                end = i;
            }
        }
        if (state != 3 && state != 2) {
            return 0;
        }

        int sign = 1;
        if (start > 0) {
           sign =  chs[start - 1] == '-' ? -1 : sign;
        }
        int idx = start;
        long value = 0;
        while (idx <= end) {
            value = value * 10 + (chs[idx++] - '0');
            if (value > Integer.MAX_VALUE + (long) 1) {
                value = Integer.MAX_VALUE + (long) + 1;
            }
        }
        value = sign * value;
        if (value > Integer.MAX_VALUE) {
            return Integer.MAX_VALUE;
        }
        if (value < Integer.MIN_VALUE) {
            return Integer.MIN_VALUE;
        }

        return (int)value;
    }