Poison

8. String to Integer (atoi)

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int myAtoi(String s) {
        int res = 0;

        int i = 0;

        // skip whitespace
        while (i < s.length() && s.charAt(i) == ' ') {
            i++;
        }

        if (i == s.length()) {
            return res;
        }

        int sign = 1;

        // skip sign
        if (s.charAt(i) == '+') {
            i++;
        } else if (s.charAt(i) == '-') {
            sign = -1;
            i++;
        }

        if (i == s.length()) {
            return res;
        }

        while (i < s.length() && Character.isDigit(s.charAt(i))) {
            int num = s.charAt(i) - '0';
            
            if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && num > 7)) {
                return Integer.MAX_VALUE;
            }
            if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && num > 8)) {
                return Integer.MIN_VALUE;
            }

            res = res * 10 + sign * num;
            i++;
        }

        return res;
    }
}
Automaton
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Solution {
    private enum State {
        //        |   ' '   |  '+'/'-'  |  '0'-'9'  |  OTHER  |
        // INIT   |   INIT  |   SIGN    |  NUMBER   |   END   |
        // SIGN   |   END   |   END     |  NUMBER   |   END   |
        // NUMBER |   END   |   END     |  NUMBER   |   END   |
        // END    |   END   |   END     |   END     |   END   |
        INIT, SIGN, NUMBER, END
    }

    private static class Automaton {
        private static final Map<State, State[]> STATE_TO_STATES_MAP = new HashMap<>();

        static {
            STATE_TO_STATES_MAP.put(State.INIT, new State[]{State.INIT, State.SIGN, State.NUMBER, State.END});
            STATE_TO_STATES_MAP.put(State.SIGN, new State[]{State.END, State.END, State.NUMBER, State.END});
            STATE_TO_STATES_MAP.put(State.NUMBER, new State[]{State.END, State.END, State.NUMBER, State.END});
            STATE_TO_STATES_MAP.put(State.END, new State[]{State.END, State.END, State.END, State.END});
        }

        private int sign = 1;
        private int num;
        private State state = State.INIT;

        private void action(char c) {
            state = STATE_TO_STATES_MAP.get(state)[getStateIndex(c)];
            if (state == State.SIGN) {
                if (c == '-') {
                    sign = -1;
                }
            } else if (state == State.NUMBER) {
                if (sign > 0) {
                    if (num > Integer.MAX_VALUE / 10 || (num == Integer.MAX_VALUE / 10 && c > '7')) {
                        num = Integer.MAX_VALUE;
                        return;
                    }
                } else {
                    if (num < Integer.MIN_VALUE / 10 || (num == Integer.MIN_VALUE / 10 && c > '8')) {
                        num = Integer.MIN_VALUE;
                        return;
                    }
                }

                num = num * 10 + sign * (c - '0'); // 注意此处使用了 sign 与数字相乘，以使最后返回 num 即可
            }
        }

        private int getStateIndex(char c) {
            if (c == ' ') {
                return 0;
            } else if (c == '+' || c == '-') {
                return 1;
            } else if (c >= '0' && c <= '9') {
                return 2;
            } else {
                return 3;
            }
        }
    }

    public int myAtoi(String s) {
        Automaton automaton = new Automaton();
        for (int i = 0; i < s.length(); i++) {
            automaton.action(s.charAt(i));
        }
        return automaton.num;
    }
}
Reference

8. String to Integer (atoi)