DFA Parse Integer

Valid Number

这题看一眼就会发现要考虑的各种奇葩 case 实在是太多了。。。对于这类需要 parse 的同时考虑 N 多种不同状态的字符串处理问题，就老老实实用 DFA (Deterministic Finite Automata) 吧，要不会被折磨疯的。

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

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

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

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

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

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

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

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

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

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

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

public class Solution {
    public boolean isNumber(String s) {
        s = s.trim();
        int N = s.length();

        char curState = 's';
        for(int i = 0; i < N; i++){
            curState = transition(curState, s.charAt(i));
            if(curState == 'F') return false;
        }

        return (curState == 'd' || curState == 's' || curState == 'e') ? false: true;
    }

    private char transition(char curState, char chr){
        switch(curState){
            case 's':
                if(chr == '-' || chr == '+') return 'S';
                else if(Character.isDigit(chr)) return 'N';
                else if(chr == '.') return 'd';
            case 'S':
                if(Character.isDigit(chr)) return 'N';
                else if(chr == '.') return 'd';
                else return 'F';
            case 'N':
                if(Character.isDigit(chr)) return 'N';
                else if(chr == '.') return 'D';
                else if(chr == 'e') return 'e';
                else return 'F';
            case 'd':
                if(Character.isDigit(chr)) return 'D';
                else return 'F';
            case 'D':
                if(Character.isDigit(chr)) return 'D';
                else if(chr == 'e') return 'e';
                else return 'F';
            case 'e':
                if(chr == '-' || chr == '+') return 'e';
                else if(Character.isDigit(chr)) return 'E';
                else return 'F';
            case 'E':
                if(Character.isDigit(chr)) return 'E';
                else return 'F';
            case 'F':
                return 'F';
            default:
                return 'F';
        }
    }
}

String to Integer (atoi)

一个意思，就是 DFA 结构稍微变了点。

检查 overflow 简便方法：

• next = cur * 10 + newVal;

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

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

        int num = 0;
        int sign = 1;
        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 == 's' || curState == 'P' || curState == 'N') 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';
        }
    }
}

Reverse Integer

刷题刷到现在我才深切体会到当初 bloomberg 面试题是多么的傻逼。。

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;
    }
}