字符串、状态机

字符串转换整数 (atoi)

有限状态机（deterministic finite automaton，DFA）
此题的考点主要有：
1）字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。所以考点一就是如何避免臃肿代码，通常的解决方案是自动机（状态转移机）。
2）int类型的边界问题， ~ ，即最大值加1会变成负数，所以需要先转换成long型再加1。

(long)Integer.MAX_VALUE + 1

本题的状态转移机可以描述为下：

对应代码如下：

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";
    // 状态机的定义, 状态数组的下标顺序需要和输入类型对应
    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; // 当前状态机的状态
    private int sign; // 正负
    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();
    }

整数转罗马数字

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

}