字符串转换整数

题目信息

将字符串转换成一个 32 位有符号整数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

示例 1：

输入：s = "42"
输出：42

示例 2：
输入：s = " -42"
输出：-42

示例 3：

输入：s = "04193 with words"
输出：4193

示例 4：

输入：s = "words and 987"
输出：0

示例 5：

输入：s = "-91283472332"
输出：-2147483648

解题思路

1. 暴力破解：
   1. 判断首位合法字符：“0 ～ 9”，“+”，“-”，“ ”
   2. 继续判断后续连续的字符是否满足：“0～9”， “ ”
   3. 拼合数字，判断是否溢出
2. 无效操作分析：大量if...else...状态判断
3. 优化方法：确定有限状态机（deterministic finite automaton, DFA）

	' '	+/-	number	other
start	start	signed	in_number	end
signed	end	end	in_number	end
in_number	end	end	in_number	end
end	end	end	end	end

4. 考虑边界：只有一位符号，不满足数字
5. 编码实现

代码

常规解法

class Solution {
    public int myAtoi(String s) {
        // 处理边界
        if (s == null || s.trim().length() == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();
        int res = 0;
        int i = 0;
        int flag = 1;
        // 处理空格
        while(chars[i] == ' ') {
            i++;
        }
        // 处理正负号
        if(chars[i] == '-') {
            flag = -1;
        }
        if(chars[i] == '+' || chars[i] == '-') {
            i++;
        }
        // 处理后续满足条件的数字字符
        while(i < s.length() && Character.isDigit(chars[i])) {
            int r = chars[i] - '0';
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && r > Integer.MAX_VALUE % 10)) {
                return flag > 0 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
            }
            res = res * 10 + r;
            i++;
        }
        return flag > 0 ? res : -res;
    }
}

状态机

class Solution {
    public int myAtoi(String str) {
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            automaton.get(str.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }
}

/**
 * 创建状态机
 */
class Automaton {
    public int sign = 1;
    public long ans = 0;
    private String state = "start";
    private Map<String, String[]> table = new HashMap<String, String[]>() {{
        put("start", new String[]{"start", "signed", "in_number", "end"});
        put("signed", new String[]{"end", "end", "in_number", "end"});
        put("in_number", new String[]{"end", "end", "in_number", "end"});
        put("end", new String[]{"end", "end", "end", "end"});
    }};

    public void get(char c) {
        state = table.get(state)[get_col(c)];
        if ("in_number".equals(state)) {
            ans = ans * 10 + c - '0';
            // 溢出条件判断
            ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
        } else if ("signed".equals(state)) {
            sign = c == '+' ? 1 : -1;
        }
    }

    private int get_col(char c) {
        if (c == ' ') {
            return 0;
        }
        if (c == '+' || c == '-') {
            return 1;
        }
        if (Character.isDigit(c)) {
            return 2;
        }
        return 3;
    }
}

题目来源：力扣（LeetCode）
题目链接：https://leetcode-cn.com/problems/string-to-integer-atoi

商业转载请联系官方授权，非商业转载请注明出处。