算法题整理

异或运算有以下三个性质。

任何数和 0做异或运算，结果仍然是原来的数，即 a ⊕ 0=a
任何数和其自身做异或运算，结果是 0，即 a⊕ a=0，a⊕a=0。
异或运算满足交换律和结合律，即 a ⊕ b ⊕ a=b ⊕ a⊕ a=b⊕ (a ⊕ a)=b ⊕0=b

0⊕0⊕⋯⊕0⊕a=a

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

自动机：我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。

class Solution {
    public int myAtoi(String str) {
        Automaton automaton = new Automaton();
        int length = str.length();
        for (int i = 0; i < length; ++i) {
            automaton.get(str.charAt(i));
        }
        return (int) (automaton.sign * automaton.ans);
    }
}

class Automaton {
    public int sign = 1;
    public long ans = 0;
    private String state = "start";
    private Map table = new HashMap() {{
        put("start", new String[]{"start", "signed", "in_number", "end"});
        put("signed", new String[]{"end", "end", "in_number", "end"});
        put("in_number", new String[]{"end", "end", "in_number", "end"});
        put("end", new String[]{"end", "end", "end", "end"});
    }};

    public void get(char c) {
        state = table.get(state)[get_col(c)];
        if ("in_number".equals(state)) {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? Math.min(ans, (long) Integer.MAX_VALUE) : Math.min(ans, -(long) Integer.MIN_VALUE);
        } else if ("signed".equals(state)) {
            sign = c == '+' ? 1 : -1;
        }
    }

    private int get_col(char c) {
        if (c == ' ') {
            return 0;
        }
        if (c == '+' || c == '-') {
            return 1;
        }
        if (Character.isDigit(c)) {
            return 2;
        }
        return 3;
    }
}

length();

char ChatAt(int i);

String toLowerCase();将字符串转为全小写

String toUpperCase();将字符串转为全大写

String trim();返回一个字符串，其值为此字符串，并删除任何前导和尾随空格。

StringBuffer append(char c/char[] str/int…); 将指定类型参数附加到此序列

StringBuffer reverse();序列反转

boolean isdigit(char ch)；确定指定字符是否为数字

boolean isletter(char ch); 确定指定字符是否为字母

boolean isLetterOrDigit(char ch) ；确定字符是否为数字或字母

boolean isLowerCase(char ch);确定字符是否为小写