字符串轉(zhuǎn)換整數(shù) (atoi)

有限狀態(tài)機（deterministic finite automaton，DFA）
此題的考點主要有：
1）字符串處理的題目往往涉及復(fù)雜的流程以及條件情況，如果直接上手寫程序，一不小心就會寫出極其臃腫的代碼。所以考點一就是如何避免臃腫代碼，通常的解決方案是自動機（狀態(tài)轉(zhuǎn)移機）。
2）int類型的邊界問題， ~ ，即最大值加1會變成負(fù)數(shù)，所以需要先轉(zhuǎn)換成long型再加1。

(long)Integer.MAX_VALUE + 1

本題的狀態(tài)轉(zhuǎn)移機可以描述為下：

對應(yīng)代碼如下：

public class Solution {

    private static final String START = "START";
    private static final String SIGNED = "SIGNED";
    private static final String IN_NUMBER = "IN_NUMBER";
    private static final String END = "END";
    // 狀態(tài)機的定義, 狀態(tài)數(shù)組的下標(biāo)順序需要和輸入類型對應(yīng)
    private static final Map<String, String[]> stateMachine = new HashMap<>(); 
    static {
        stateMachine.put(START, new String[]{START, SIGNED, IN_NUMBER, END});
        stateMachine.put(SIGNED, new String[]{END, END, IN_NUMBER, END});
        stateMachine.put(IN_NUMBER, new String[]{END, END, IN_NUMBER, END});
        stateMachine.put(END, new String[]{END, END, END, END});
    }
    public static int getInputType(char c) {
        if (c == ' ') {
            return 0;
        }
        if (c == '+' || c == '-') {
            return 1;
        }
        if (c >= '0' && c <= '9') {
            return 2;
        }
        return 3;
    }

    private String currentState; // 當(dāng)前狀態(tài)機的狀態(tài)
    private int sign; // 正負(fù)
    private long value; // 絕對值

    public int myAtoi(String str) {
        currentState = START;
        sign = 1;
        value = 0;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            int inputType = getInputType(c);
            currentState = stateMachine.get(currentState)[inputType];
            if(currentState.equals(SIGNED)){
                sign = c == '+' ? 1 : -1;
            }else if(currentState.equals(IN_NUMBER)){
                value = value * 10 + (c - '0');
                if(sign == 1){
                    value = Math.min(value, Integer.MAX_VALUE);
                }else {
                    value = Math.min(value, (long)Integer.MAX_VALUE + 1);
                }
            }else if(currentState.equals(END)){
                break;
            }
        }
        return (int) (sign * value);
    }
}

Z 字形變換

    public static String convert(String s, int numRows) {
        int n = s.length();
        if(numRows == 1){
            return s;
        }
        List<StringBuilder> rows = new ArrayList<>();
        for(int i=0; i<numRows; i++){
            rows.add(new StringBuilder());
        }
        int row = 0;
        boolean down = false;
        for(int i=0; i<n; i++){
            rows.get(row).append(s.charAt(i));
            if(row == 0 || row == numRows - 1){
                down = !down;
            }
            row += down ? 1 : -1;
        }
        StringBuilder sb = new StringBuilder();
        for(StringBuilder r : rows){
            sb.append(r);
        }
        return sb.toString();
    }

整數(shù)轉(zhuǎn)羅馬數(shù)字

public class Solution {

    int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
    String[] symbols = {"M","CM","D","CD","C","XC","L","XL","X","IX","V","IV","I"};

    public String intToRoman(int num) {
        StringBuilder sb = new StringBuilder();
        // Loop through each symbol, stopping if num becomes 0.
        for (int i = 0; i < values.length && num >= 0; i++) {
            // Repeat while the current symbol still fits into num.
            while (values[i] <= num) {
                num -= values[i];
                sb.append(symbols[i]);
            }
        }
        return sb.toString();
    }

}