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();
        char curState = 's';
        char[] arr = s.toCharArray();
        for(char c : arr){
            curState = transition(curState, c);
            if(curState=='F') return false;
        }
        return (curState == 'd' || curState == 's' || curState == 'e') ? false: true;
    }

    public char transition(char curState, char c){
        switch(curState){
            case 's':
                if(c=='+'|| c=='-') return 'S';
                else if(c>='0'&&c<='9') return 'N';
                else if(c=='.') return 'd';
                else return 'F';
            case 'S':
                if(Character.isDigit(c)) return 'N';
                else if(c == '.') return 'd';
                else return 'F';
            case 'N':
                if(c>='0'&&c<='9') return 'N';
                else if(c=='.') return 'D';
                else if(c=='e') return 'e';
                else return 'F';
            case 'd':
                if(c>='0'&&c<='9') return 'D';
                else return 'F';
            case 'D':
                if(c>='0'&&c<='9') return 'D';
                else if(c == 'e') return 'e';
                else return 'F';
            case 'e':
                if(c=='+'|| c=='-') return 'e';
                else if(c>='0'&&c<='9') return 'E';
                else return 'F';
            case 'E':
                if(c>='0'&&c<='9') 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. 或 if(next%10!=newval), overflow

• start开始后四种状态,positive, negative, number, false

• 实际上因为状态简单, 不用构造DFA

• 核心就在处理space, overflow上, 想起当时google面试, 自己答的确实不好

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

简单版

public class Solution {
    public int myAtoi(String str) {
        //handle space
        str = str.trim(); 
        //handle str.length==0
        if(str.length()==0) return 0;

        //handle sign
        int sign = 1;int i=0;
        if(str.charAt(i)=='-') {sign = -1;i++;}
        else if(str.charAt(i)=='+') i++;

        //handle overflow and space 
        int num = 0;
        for(;i<str.length();i++){
            char c = str.charAt(i);
            if(Character.isDigit(c)){
                int cur = (c-'0');
                num=num*10+cur;
                if(num%10!=cur) // handl overflow
                    return (sign==1)?Integer.MAX_VALUE:Integer.MIN_VALUE;
            }
            else //handle non-digit
                break;
        }

        return num*sign;
    }
}

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