把字符串转换成整数

1、状态机

1.解题思路

边界条件：

数据上下 溢出

空字符串

只有正负号

有无正负号

错误标志输出

2.代码

public class Solution {
    private final int acceptNum = 1;
    private final int acceptNumAndAddSub = 2;
    private final int acceptNothing = 3;
    private final int isAdd = 1;
    private final int isSub = 2;
    private int state = 1;
    public int StrToInt(String str) {
        long result = 0;
        int len = str.length();
        if(str == null || len==0) return 0;
        char [] list = str.toCharArray();
        int base = 1;
        boolean isNegative = false;
        for(int i=len-1;i>=0;i--){
            if(state == acceptNum){
                //处理倒数第一个字符，只接受数字
                int num = checkNum(list[i]);
                if(num == -1){
                    //不是数字,则非法
                    result = 0;
                    break;
                }else{
                    //是数字，计算数字
                    result = result + num * base;
                    base = base * 10;
                    state = acceptNumAndAddSub; //状态从acceptNum--->acceptNumAndAddSub
                }
            }else if(state == acceptNumAndAddSub){
                int isAddSub = isAddSub(list[i]);
                int num = checkNum(list[i]);
                if(isAddSub == isSub){
                    //接收了一个“-”，状态从acceptNumAndAddSub--->acceptNothing
                    isNegative = true;
                    state = acceptNothing;
                }else if(isAddSub == isAdd){
                    //接收了一个“+”，状态从acceptNumAndAddSub--->acceptNothing
                    isNegative = false;
                    state = acceptNothing;
                }else if(num != -1){
                    //接收一个“0---9”的数字，状态从acceptNumAndAddSub--->acceptNumAndAddSub,继续接收
                    result += num * base;
                    base = base * 10;
                    state = acceptNumAndAddSub;
                }else{
                    // 非数字、非“+”，非“-”
                    result = 0;
                    break;
                }
            }else if(state == acceptNothing){
                // 这里是什么都不接受的状态:acceptNothing
                //若接收了字符则非法
                result = 0;
                break;
            }
        }
        // 处理最大正数，最大负数
        if(isNegative == true && (-result) < (-2147483648))
            return 0;
        else if(isNegative == false && result > 2147483647 )
            return 0;
        return isNegative?(int)(-result):(int)result;
    }
    private int checkNum(char c){
        // 是0--9，则返回（int）0--9,否则返回-1
        int num = c - '0';
        if(0 <= num && num <=9)
            return num;
        return -1;
    }
    private int isAddSub(char c){
        //判断是否接受到“+”或“-”
        //不是则返回-1
        if(c == '-')
            return isSub;
        else if(c == '+')
            return isAdd;
        else
            return -1;
    }
}

代码简化：

public class Solution {
     public int StrToInt(String str) {
        if (str == null || str.length() == 0)
            return 0;
        boolean isNegative = str.charAt(0) == '-';
        long ret = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (i == 0 && (c == '+' || c == '-'))  /* 符号判定 */
                continue;
            if (c < '0' || c > '9')                /* 非法输入 */
                return 0;
            ret = ret * 10 + (c - '0');
        }
        // 处理最大正数，最大负数
        if(isNegative == true && (-ret) < (-2147483648))
            return 0;
        else if(isNegative == false && ret > 2147483647 )
            return 0;
        return isNegative ? (int)(-ret) : (int)ret;
    }
}

3.复杂度

• 时间复杂度：O(n)
• 空间复杂度：O(1)

4.遇到的坑