确定有限状态自动机

喜欢这个充满蒸汽朋克感觉的名字，只是它本身一点也不朋克。

还是有关Integer的操作，特别拿出一章来说这个DFA

DFA，Deterministic finite automaton。刚到美国的时候学Network 201，全都是这种东西，后来学Transportation Systems Analysis，还是这玩意，说白了就是一种表示状态转移的一种图。大概长这样：

65. Valid Number

在Leetcode论坛上，投票数第一的答案只有一句抱怨：The worst problem i have ever met in this oj. The description do not give a clear explantion of the definition of a valid Number, we just use more and more trick to get the right solution. It's too bad, it's waste of my time，连代码都没有。我能感受他的痛苦。

这题看一眼就会发现要考虑的各种奇葩 case 实在是太多了。

对于这类需要 parse 的同时考虑 N 多种不同状态的字符串处理问题，就用到 DFA 吧，要不会被折磨疯的。

记得先把输入字符 trim 一下，免得前后空格不好处理。

状态列表，每一个独立状态用一个 char 表示；

• s : 还未看到 + / - 号的起始状态

• S : 已看到符号的起始状态

• N : 读到数字了，还没遇到 '.' 或 'e'

• d : 首次碰到 '.'，后面还没有遇到数字

• D : 已碰到 '.' 并且后面有数字

• e : 首次碰到 'e'，后面还没有数字

• E : 已碰到 'e' 并且后面有数字

• F : 违法状态，一定为 false;

DFA 结构如图 所有没画出来的边都是 'F'，以红色圈结束(小写字母)的也都是 'F'

只要把DFA状态转移逻辑想清楚，把图画出来，代码很简单没什么可说的，专门一个函数实现DFA，然后一个个char转移状态就行了。

public class Solution {
    public boolean isNumber(String s) {
        s = s.trim();
        char curState = 's';
        for (int i = 0; i < s.length(); ++i) {
            curState = dfa(curState, s.charAt(i));
            if (curState == 'F') return false;
        }
        return (curState == 's' || curState == 'd' || curState == 'e') ? false : true;
    }
    private char dfa(char curState, char ch) {
        switch (curState) {
            case 's':
                if (ch == '-' || ch == '+') return 'S';
                else if (Character.isDigit(ch)) return 'N';
                else if (ch == '.') return 'd';
                else return 'F';
            case 'S':
                if (Character.isDigit(ch)) return 'N';
                else if (ch == '.') return 'd';
                else return 'F';
            case 'N':
                if (Character.isDigit(ch)) return 'N';
                else if (ch == '.') return 'D';
                else if (ch == 'e') return 'e';
                else return 'F';
            case 'd':
                if (Character.isDigit(ch)) return 'D';
                else return 'F';
            case 'e':
                if (ch == '-' || ch == '+') return 'e';
                else if (Character.isDigit(ch)) return 'E';
                else return 'F';
            case 'D':
                if (Character.isDigit(ch)) return 'D';
                else if (ch == 'e') return 'e';
                else return 'F';
            case 'E':
                if (Character.isDigit(ch)) return 'E';
                else return 'F';
            default:
                return 'F';
        }
    }
}

8. String to Integer (atoi)

先trim

一个意思，就是 DFA 结构稍微变了点，有一个正负数的区别，再就是处理overflow的问题。

检查 overflow 简便方法：

• next = cur * 10 + newVal;

• if(next / 10 != cur), overflow

public class Solution {
    public int myAtoi(String str) {
        str = str.trim();

        int sign = 1;
        int num = 0;
        char curState = 's';

        for (int i = 0; i < str.length(); ++i) {
            curState = transition(curState, str.charAt(i));
            if (curState == 'N') sign = -1;
            if (curState == 'F') return num * sign;

            if (curState == 'S') {
                int val = (int) str.charAt(i) - '0';
                int next = num * 10 + val;
                if (next / 10 != num) return sign == 1 ? Integer.MAX_VALUE : Integer.MIN_VALUE;
                num = next;
            }
        }
        if (curState == 'P' || curState == 'N' || curState == 's') return 0;
        return num * sign;
    }
    private char transition(char curState, char cur){
        switch(curState){
            case 's':
                if(cur == '+') return 'P';
                else if(cur == '-') return 'N';
                else if(Character.isDigit(cur)) return 'S';
                else return 'F';
            case 'S':
                if(Character.isDigit(cur)) return 'S';
                else return 'F';
            case 'N':
                if(Character.isDigit(cur)) return 'S';
                else return 'F';
            case 'P':
                if(Character.isDigit(cur)) return 'S';
                else return 'F';
            default:
                return 'F';
        }
    }
}

7. Reverse Integer

模糊的印象中是一道很常见的面试题。

检查 overflow 简便方法：

• next = cur * 10 + newVal;

• if(next / 10 != cur), overflow

真的很实用

public class Solution {
    public int reverse(int x) {
        int num = 0;

        while (x != 0) {
            int val = x % 10;
            int next = num * 10 + val;
            if (next / 10 != num) return 0;
            num = next;
            x /= 10;
        }
        return num;
    }
}