// 常用的 get put replace 操作
    Map<Character, Integer> map = new HashMap<>();
    char[] chars = s.toCharArray();
    for (char ele : chars) {
        if (map.containsKey(ele)) {
            map.replace(ele, map.get(ele)+1); 
        } else {
            map.put(ele, 1);
        }
    }

    // 不同的遍历方法
    // 迭代Entry
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
    }
    
    // 迭代键
    for (Integer key : map.keySet()) {
        System.out.println("Key = " + key);
    }

    // 迭代值
    for (Integer value : map.values()) {
        System.out.println("Value = " + value);
    }
    
    // 迭代器
    Iterator<Map.Entry<Integer, Integer>> entries = map.entrySet().iterator();
    while (entries.hasNext()) {
        Map.Entry<Integer, Integer> entry = entries.next();
        System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
    }

    // list 默认排序方式
    Collections.sort(list);
    
    // 同样的，继承了List接口的也有内置排序方法可以使用。
    Collections.sort(list, (o1, o2) -> {return o1.val - o2.val;});
    
    // list to array 
    List<String> result = new ArrayList<>();
    result.toArray(new String[result.size()]);
    
    // 迭代器
    List<Integer> list = new LinkedList<>();
    Iterator<Integer> iterator = list.iterator();
    while (iterator.hasNext()) {
        Integer ele = iterator.next();
    }

   // 队列常用的API：offer，poll，peek
   // 并且优先队列有时候需要根据元素配置比较规则，一般使用匿名表达式非常简洁,
   // 其中 o1 - o2 就是小顶堆，反正就是大顶堆
   PriorityQueue<ListNode> pq = new PriorityQueue<>((o1, o2) -> {return o1.val - o2.val;});

    // 数组的内置排序方式，默认从小到大
    int[] arrays = new int[n];
    Arrays.sort(arrays);
    
    // 可以自己配置比较规则，这里对二维数组尤其有用
    int[][] tasks = new int[n][m];
    // 通过lambda表达式来进行比较规则的设置
    Arrays.sort(tasks, (x,y)->x[0]-y[0]);
    
    // Java高维数组定义，就直接定义就好，如下面三维数组
    int[][][] threeArray = new int[n][m][l];
    

    // 得到String中某一指定位置的char
    String.charAt(index);

    // 得到将包含整个String的char数组
    String.toCharArray()
    
    // 单个char转换为String
    String s = String.valueOf('c');
    
    //将一个char数组转换成String
    String s = String.valueOf(new char[]{'c'});
    
    //将char数组的一部分转换为String
    // 剑指 Offer 05. 替换空格 有用到这个技巧
    String s = new String(array, 0, size);
    
    // char与int类型计算，需要强制转换
    char incre = (char) (chars[i] - '0');
    chars[i] = (char)(chars[i-1] + incre);
    
    // 解数独那题遇到一个数值的问题，需要
    // (char) ('0' + i) OK，(char)(i) 就不OK

StringBuilder res = new StringBuilder();
for(String s : strings)
    res.append(s); // append(string s) append(char c) 都可
return res.toString();

// 还有insert(offset, ele)、delete(start, end)、deleteCharAt(index)、reverse等API

public interface Comparable<T> {
    public int compareTo(T o);
}

// 对于需要保留小数点的，需要加上一个小数，比如0.0
int temp = 5;
int dist = 2;
// left = 2.0
double left = temp / dist;
// left = 2.5
double left = temp / (dist + 0.0);

// Integer.parseInt() 具有自动去除前缀零的功能
String a = "001"
// b = 1
int b = Integer.parseInt(a)

public int searchInsert(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;
    int result = -1;
    while (left <= right) {
        int mid = left + ((right - left) >> 1);
        if (nums[mid] >= target) {
            if (mid == 0 || nums[mid-1] < target) {
                result = mid;
                break;
            }
            right = mid - 1;
        } else {
            left = mid + 1;
        }
    }

    if (result == -1) {
        return nums.length;
    } else {
        return result;
    }
}

class Node {
    public int val;
    public Node left;
    public Node right; // 多叉树便是 List<Node> children;
}

class TreeDFS {
    // 前序遍历-递归
    public void preorder(Node root, List<Integer> result) {
        if (root != null) {
            // 具体操作，可以换成其它
            result.add(root.val);
            for (int i = 0; i < root.children.size(); i++) {
                preorder(root.children.get(i), result);
            }
        }
    }
    
    // 后序遍历-递归
    public void postorder(Node root, List<Integer> result) {
        if (root != null) {
            for (int i = 0; i < root.children.size(); i++) {
                postorder(root.children.get(i), result);
            }
            // 具体操作，可以换成其它
            result.add(root.val);
        }
    }
    
    // 二叉树中序遍历-递归
    public void inorder(Node root, List<Integer> result) {
        if (root != null) {
            inorder(root.left, result);
            // 具体操作，可以换成其它
            result.add(root.val);
            inorder(root.right, result);
        }
    }
    
    // 栈实现多叉树的前序遍历-迭代，二叉树则是children变成左右子树即可
    public void preorder(Node root, List<Integer> result) {
        if (root != null) {
            Stack<Node> stack = new Stack<>();
            stack.push(root);
            while(!stack.isEmpty()) {
                Node node = stack.pop();
                // 具体操作，可以换成其它
                result.add(node.val);
                // 保证左右顺序，栈需要反着放
                for (int i = node.children.size() - 1; i >= 0; i--) { 
                    stack.push(node.children.get(i));
                }
            }
        }
    }
     
     // 栈实现多叉树的后序遍历-迭代   
     // 前序遍历顺序是中左右 后序是左右中，因此后序可以通过前序转换过来：
     // 中右左：stack入栈先入左，可以得到；-> 左右中：最后result进行reverse   
     public void postorder(Node root, List<Integer> result) {
        if (root == null) {
            return rseult;
        }
        
        Stack<Node> stack = new Stack<>();
        stack.push(root);
        List<Integer> reverseResult = new ArrayList<>();
        while (!stack.isEmpty()) {
            Node node = stack.pop();
            // 具体操作，可以换成其它
            reverseResult.add(node.val);
            // 顺序就是右左
            for (int i = 0; i < node.children.size() - 1; i++) {
                stack.push(node.children.get(i));
            }
        }
        
        for (int i = 0; i < reverseResult.size(); i++) {
            result.add(reverseResult.get(i));
        }
     }
     
    // 栈实现二叉树的中序遍历-迭代
    public void inorder(Node root, List<Integer> result) {
        Stack<Integer> stack = new Stack<>();
        Node cur = root;
        while (cur != null || !stack.isEmpty()) {
            if (cur != null) {
                stack.push(cur);
                cur = cur.left;
            } else {
                cur = stack.pop();
                // 具体操作，可以换成其它
                result.add(cur.val);
                cur = cur.right;
            }
        }
    }
}

class TreeBFS {
    // 队列实现树的广度遍历
    public void BFS(Node root, List<Integer> result) {
        Queue<Node> queue = new LinkedList<>();
        if(root != null) {
            queue.offer(root);
        }
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node node = queue.poll();
                result.add(node.val);
                for (int i = 0; i < root.children.size(); i++) {
                    queue.offer(root.children.get(i));
                }
            }
        }
    }
}

class BSTNode {
    public int val;
    public Node left;
    public Node right;
    // 维护左子树大小，优化查询第k个数时间复杂度
    public int leftSize;
}

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果
    }
}

    // 递归
    private int recursive(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
    
        return recursive(n - 1) + recursive(n - 2);
    }

    // 自顶向下
    public int fib(int n) {
        int[] memo = new int[n+1]; // 备忘录
        return up2down(n, memo);
    }
    
    private int up2down(int n, int[] memo) {
        if (n == 0 || n == 1) {
            return n;
        }
    
        if (memo[n] != 0) {
            return memo[n];
        }
        
        memo[n] = up2down(n - 1, memo) + up2down(n - 2, memo);
        return memo[n];
    }

    // 自低向上
    private int down2up(int n) {
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    // 穷举回溯的解法，会超时 复杂度 O(S^n) S为coins数量，n为每个coin在amount下可取的最大值
    private int result = -1;
    public int coinChange(int[] coins, int amount) {
        int size = 0;
        backtracking(0, size, coins, amount);
        return result;
    }

    private void backtracking(int startIndex, int size, int[] coins, int amount) {
        if (amount == 0) {
            if (result == -1 || size < result) {
                result = size;
            }
            return;
        }

        for (int i = startIndex; i < coins.length; i++) {
            if (result != -1 && size > result) {
                continue;
            }
            if (amount >= coins[i]) {
                size++;
                backtracking(i, size, coins, amount - coins[i]);
                size--;
            }
        }
    }

    // 动态规划-自上而下，备忘录的形式
    public int coinChange(int[] coins, int amount) {
        if (amount < 1) {
            return 0;
        }
        return coinChange(coins, amount, new int[amount]);
    }

    private int coinChange(int[] coins, int rem, int[] memo) {
        if (rem < 0) {
            return -1;
        }

        if (rem == 0) {
            return 0;
        }

        if (memo[rem - 1] != 0) {
            return memo[rem - 1];
        }

        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, rem - coin, memo);
            if (res >= 0 && res < min) {
                min = 1 + res;
            }
        }
        memo[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }

    // 动态规划-自下而上
    public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];
        int max = amount + 1;
        Arrays.fill(dp, max);
        dp[0] = 0;
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }

private boolean[] visited = new boolean[g.numVertexes];

public void DFSTraverse(Graph g) {
    // 图遍历需要每个节点都过一遍
    for (int i = 0; i < g.numVertexes; i++) {
        if (!visited[i]) {
            DFS(g, i);
        }
    }
}

public void DFS(Graph g, int i) {
    visited[i] = true;
    for(int j : G.adj(i)) { // 递归访问临近节点
        if(!visited[j]) {
            DFS(g, j); 
        }
    }
}

public void BFSTraverse(Graph g) {
    Deque<Node> queue = new Deque<>();
    for (int i = 0; i < g.numVertexes; i++) {
        if (!visited[i]) {
            visited[i] = true;
            queue.addLast(i);
            while(!queue.isEmpty()) {
                int i = queue.removeFirst();
                for (int j : G.adj(i)) {
                    if (!visited[j]) {
                        visited[j] = true;
                        queue.addLast(j);
                    }
                }
            }
        }
    }
}

interface UF {
    void union(int p, int q); // 在 p、q之间添加一条连接
    boolean connected(int p, int q); // 如果p、q存在于同一个分量，则返回true
    int find(int p); // 返回p所在的分量的标识符
    int count(); // 返回当前联通分量的数量
}

private int find(int x) {
    while(parent[x] != x) {
        // 进行路径压缩
        parent[x] = parent[parent[x]];
        x = parent[x];
    }
    return x;
}

int result = 0;
for (int i = 0; i < 32; i++) {
    if ((n & bit) != 0) {
        result++;
    }
    bit <<= 1;
}

// 或者数字左移动
int result = 0;
for (int j = 0; j < 32; j++) {
    result += (n & 1);
    n >>>= 1;
}

int bit = 1;
while ((n & bit) == 0) {
    bit <<= 1;
}

int res = 0;
while(n != 0) {
    res++;
    n &= n - 1;
}
return res;

int left = 0, right = 0;
while (right < s.size()) {
    // 增大窗口
    window.add(s[right]);
    right++;  
    while (window needs shrink) {
        // 缩小窗口
        window.remove(s[left]);
        left++;
    }
}

class PrefixSum {
    // 前缀和数组
    private int[] prefix;

    /* 输入一个数组，构造前缀和 */
    public PrefixSum(int[] nums) {
        prefix = new int[nums.length + 1];
        // 计算 nums 的累加和
        for (int i = 1; i < prefix.length; i++) {
            prefix[i] = prefix[i - 1] + nums[i - 1];
        }
    }

    /* 查询闭区间 [i, j] 的累加和 */
    public int query(int i, int j) {
        return prefix[j + 1] - prefix[i];
    }
}

int[] diff = new int[nums.length];
// 构造差分数组
diff[0] = nums[0];
for (int i = 1; i < nums.length; i++) {
    diff[i] = nums[i] - nums[i - 1];
}

int[] res = new int[diff.length];
// 根据差分数组构造结果数组
res[0] = diff[0];
for (int i = 1; i < diff.length; i++) {
    res[i] = res[i - 1] + diff[i];
}

class Difference {
    // 差分数组
    private int[] diff;

    public Difference(int[] nums) {
        assert nums.length > 0;
        diff = new int[nums.length];
        // 构造差分数组
        diff[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            diff[i] = nums[i] - nums[i - 1];
        }
    }

    /* 给闭区间 [i,j] 增加 val（可以是负数）*/
    public void increment(int i, int j, int val) {
        diff[i] += val;
        // 当j+1 >= diff.length时，说明是对nums[i]及以后的整个数组都进行修改，
        // 那么就不需要再给diff数组减val了。
        if (j + 1 < diff.length) {
            diff[j + 1] -= val;
        }
    }

    public int[] result() {
        int[] res = new int[diff.length];
        // 根据差分数组构造结果数组
        res[0] = diff[0];
        for (int i = 1; i < diff.length; i++) {
            res[i] = res[i - 1] + diff[i];
        }
        return res;
    }
}