public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
    static final float DEFAULT_LOAD_FACTOR = 0.75f;
    /**
     * The bin count threshold for using a tree rather than list for a
     * bin.  Bins are converted to trees when adding an element to a
     * bin with at least this many nodes. The value must be greater
     * than 2 and should be at least 8 to mesh with assumptions in
     * tree removal about conversion back to plain bins upon
     * shrinkage.
     * **单个拉链达到阈值时使用TreeNode实现拉链**
     */
    static final int TREEIFY_THRESHOLD = 8;
    /**
     *  When allocated, length is always a power of two.
     *  分配时长度总是2的幂.
     */
    transient Node<K,V>[] table;
    transient int size;
    /**
     * The number of times this HashMap has been structurally modified
     * Structural modifications are those that change the number of mappings in
     * the HashMap or otherwise modify its internal structure (e.g.,
     * rehash).  This field is used to make iterators on Collection-views of
     * the HashMap fail-fast.  (See ConcurrentModificationException).
     * HashMap被结构性修改的次数
     */
    transient int modCount;
    /**
     * The next size value at which to resize (capacity * load factor).
     */
    int threshold;
    ...
}

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;
        ...
}

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  // red-black tree links
        TreeNode<K,V> left;
        TreeNode<K,V> right;
        TreeNode<K,V> prev;    // needed to unlink next upon deletion
        boolean red;
        ...
}

public class LinkedHashMap<K,V> extends HashMap<K,V>
    implements Map<K,V> {
    static class Entry<K,V> extends HashMap.Node<K,V> {
            Entry<K,V> before, after;
            ...
    }
}

/**
 * Associates the specified value with the specified key in this map.
 * If the map previously contained a mapping for the key, the old
 * value is replaced.
 *插入元素key相同时,后者key会替换前者key.
 */
public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
}

/**
 * Implements Map.put and related methods
 *
 * @param hash hash for key
 * @param key the key
 * @param value the value to put
 * @param onlyIfAbsent if true, don't change existing value
 * @param evict if false, the table is in creation mode.
 * @return previous value, or null if none
 */
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        // 槽位没有元素时就直接插入
        tab[i] = newNode(hash, key, value, null);
    else {
        // 槽位已存在元素
        Node<K,V> e; K k;
        if (p.hash == hash &&
            ((k = p.key) == key || (key != null && key.equals(k))))
            // 新插入元素与已有元素的key相同时
            e = p;
        else if (p instanceof TreeNode)
            // 槽位元素已是TreeNode类型,就在红黑树中直接插入
            e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
        else {
            for (int binCount = 0; ; ++binCount) {
                if ((e = p.next) == null) {
                    p.next = newNode(hash, key, value, null);
                    if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                    // 拉链个数>8时,将拉链的链表转为红黑树
                        treeifyBin(tab, hash);
                    break;
                }
                if (e.hash == hash &&
                    ((k = e.key) == key || (key != null && key.equals(k))))
                    break;
                p = e;
            }
        }
        if (e != null) { // existing mapping for key
            V oldValue = e.value;
            // onlyIfAbsent=false, key元素已存在时新插入元素的值直接覆盖旧值
            if (!onlyIfAbsent || oldValue == null)
                e.value = value;
            afterNodeAccess(e);
            return oldValue;
        }
    }
    ++modCount;
    if (++size > threshold)
        // threshold容量阈值,默认为16
        // 大于容量时启动扩容
        resize();
    afterNodeInsertion(evict);
    return null;
}

/**
 * Replaces all linked nodes in bin at index for given hash unless
 * table is too small, in which case resizes instead.
 * 替换bin中给定哈希下标的所有的链接节点
 */
final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        ...
}

/**
 * Tree version of putVal.
 */
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab,
                                       int h, K k, V v) {
                                       ...

}

    /**
     * Initializes or doubles table size.  If null, allocates in
     * accord with initial capacity target held in field threshold.
     * Otherwise, because we are using power-of-two expansion, the
     * elements from each bin must either stay at same index, or move
     * with a power of two offset in the new table.
     *
     * @return the table
     */
    final Node<K,V>[] resize() {
        Node<K,V>[] oldTab = table;
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        int oldThr = threshold;
        int newCap, newThr = 0;
        if (oldCap > 0) {
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                // 扩容一倍
                newThr = oldThr << 1; // double threshold
        }
        else if (oldThr > 0) // initial capacity was placed in threshold
            newCap = oldThr;
        else {               // zero initial threshold signifies using defaults
            newCap = DEFAULT_INITIAL_CAPACITY;
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        if (newThr == 0) {
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        // 设置扩容后新的阈值
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        if (oldTab != null) {
            for (int j = 0; j < oldCap; ++j) {
                // 依次搬移所有已存在的数据
                Node<K,V> e;
                if ((e = oldTab[j]) != null) {
                    oldTab[j] = null;
                    if (e.next == null)
                        // 槽位只有一个元素时重新计算新槽位并放入
                        newTab[e.hash & (newCap - 1)] = e;
                    else if (e instanceof TreeNode)
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // preserve order
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        do {
                            next = e.next;
                            // 按位与(&)计算原有数据元素落入新数组中的哪个槽内
                            // 例如原容量为4时
                            // 1111 & 0011 ==> 0011:3
                            // 1011 & 0011 ==> 0011:3
                            // 扩容为8
                            // 1111 & 0111 ==> 0111:7
                            // 1011 & 0111 ==> 0011:3
                            // ((e.hash & oldCap) == 0) 当遍历到原始的第3个槽时
                            // 1111 & 0100 ==> 0100: 3+4(oldCap) 
                            // 1011 & 0100 ==> 0000: 3
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                        if (loTail != null) {
                            loTail.next = null;
                            newTab[j] = loHead;
                        }
                        if (hiTail != null) {
                            hiTail.next = null;
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        return newTab;
    }

/**
 * Returns the value to which the specified key is mapped,
 * or {@code null} if this map contains no mapping for the key.
 */
public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
}

/**
 * Implements Map.get and related methods
 */
final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        ...
}

/**
 * Calls find for root node.
 */
final TreeNode<K,V> getTreeNode(int h, Object k) {
    return ((parent != null) ? root() : this).find(h, k, null);
}

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char[] char1 = s.toCharArray();
        char[] char2 = t.toCharArray();
        Arrays.sort(char1);
        Arrays.sort(char2);
        return Arrays.equals(char1, char2);
    }
}

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        int[] alphm = new int[26];
        for (int i = 0; i < s.length(); i++) {
            alphm[s.charAt(i) - 'a'] ++;
            alphm[t.charAt(i) - 'a'] --;
        }
        for (int i = 0; i < 26; i++) {
            if (alphm[i] != 0) {
                return false;
            }
        }
        return true;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            for (int j = i + 1; j < nums.length; j++) {
                if (temp == nums[j]) {
                    return new int[] {i, j};
                }
            }
        }
        return null;
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int temp = target - nums[i];
            if (map.containsKey(temp)) {
                return new int[] {map.get(temp), i};
            }
            map.put(nums[i], i);
        }
        return null;
    }
}

/*
// Definition for a Node.
class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
};
*/

class Solution {
    private List<Integer> list = new ArrayList();
    public List<Integer> preorder(Node root) {
        if (root == null) {
            return list;
        }
        list.add(root.val);
        for (int i = 0; i < root.children.size(); i++) {
            preorder(root.children.get(i));
        }
        return list;
    }
}

class Solution {
    public List<Integer> preorder(Node root) {
        List<Integer> list = new ArrayList();
        if (root == null) {
            return list;
        }
        Stack<Node> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            Node temp = stack.pop();
            list.add(temp.val);
            for (int i = temp.children.size() - 1; i >= 0; i--) {
                stack.push(temp.children.get(i));
            }
        }
        return list;
    }
}

class Solution {
    public List<Integer> preorder(Node root) {
        LinkedList<Node> stack = new LinkedList<>();
        LinkedList<Integer> output = new LinkedList<>();
        if (root == null) {
            return output;
        }
        stack.add(root);
        while (!stack.isEmpty()) {
            Node node = stack.pollLast();
            output.add(node.val);
            Collections.reverse(node.children);
            for (Node item : node.children) {
                stack.add(item);
            }
        }
        return output;
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // 基于散列表,key为strs中排序后的字符串,list为value来存放
        List<List<String>> list = new ArrayList();
        if (strs == null) {
            return list;
        }
        Map<String, List<String>> map = new HashMap();
        for (int i = 0; i < strs.length; i++) {
            char[] chars = strs[i].toCharArray();
            Arrays.sort(chars);
            String key = String.valueOf(chars);
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList());
            }
            map.get(key).add(strs[i]);
        }
        list.addAll(map.values());
        return list;
    }
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        List<List<String>> list = new ArrayList();
        if (strs == null) {
            return list;
        }
        Map<String, List<String>> map = new HashMap();
        int[] ints = new int[26];
        for (int i = 0; i < strs.length; i++) {
            Arrays.fill(ints, 0);
            char[] chars = strs[i].toCharArray();
            for (int j = 0; j < chars.length; j++) {
                ints[chars[j] - 'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for (int j = 0; j < 26; j++) {
                sb.append(ints[j]);
            }
            String key = sb.toString();
            if (!map.containsKey(key)) {
                map.put(key, new ArrayList());
            }
            map.get(key).add(strs[i]);
        }
        list.addAll(map.values());
        return list;
    } 
}

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs.length == 0) return new ArrayList();
        Map<String, List> ans = new HashMap<String, List>();
        int[] count = new int[26];
        for (String s : strs) {
            Arrays.fill(count, 0);
            for (char c : s.toCharArray()) count[c - 'a']++;
            StringBuilder sb = new StringBuilder("");
            for (int i = 0; i < 26; i++) {
                sb.append('#');
                sb.append(count[i]);
            }
            String key = sb.toString();
            if (!ans.containsKey(key)) ans.put(key, new ArrayList());
            ans.get(key).add(s);
        }
        return new ArrayList(ans.values());
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    private List<Integer> list = new ArrayList();

    public List<Integer> inorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        inorderTraversal(root.left);
        list.add(root.val);
        inorderTraversal(root.right);
        return list;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList();
        Stack<TreeNode> stack = new Stack();
        TreeNode current = root;
        while (current != null || !stack.isEmpty()) {
            while (current != null) {
                stack.push(current);
                current = current.left;
            }
            current = stack.pop();
            list.add(current.val);
            current = current.right;
        } 
        return list;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private List<Integer> list = new ArrayList();
    public List<Integer> preorderTraversal(TreeNode root) {
        if (root == null) {
            return list;
        }
        list.add(root.val);
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return list;
    }
}

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList();
        if (root == null) {
            return list;
        }
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode temp = stack.pop();
            list.add(temp.val);
            if (temp.right != null) {
                stack.push(temp.right);
            }
            if (temp.left != null) {
                stack.push(temp.left);
            }
        }
        return list;
    }
}

class Solution {

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        // 1.使用队列记录按层的放入顺序
        // 2.每加入新一层前,先取完上一层的元素
        LinkedList<Node> queue = new LinkedList();
        queue.add(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList();
            result.add(level);
            // 一定要用局部变量来记录
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Node temp = queue.remove();
                level.add(temp.val);
                queue.addAll(temp.children);
            }
        }
        return result;
    }
}

class Solution {

    public List<List<Integer>> levelOrder(Node root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) return result;
        // 递归处理
        recursion(root, 0, result);
        return result;
    }

    private void recursion(Node root, int depth, List<List<Integer>> result) {
        if (result.size() <= depth) {
            result.add(new ArrayList());
        }
        // 终止条件 叶子节点为止
        // 递推公式 根-->左-->右
        result.get(depth).add(root.val);
        for (Node node : root.children) {
            recursion(node, depth + 1, result);
        }
    }

}

class Solution {
    public int nthUglyNumber(int n) {
        if (n == 0) return 0;
        int[] dp = new int[n];
        dp[0] = 1;
        int a = 0, b = 0, c = 0;
        for (int i = 1; i < n; i++) {
            int dpa = dp[a] * 2;
            int dpb = dp[b] * 3;
            int dpc = dp[c] * 5;
            int min = Math.min(Math.min(dpa, dpb), dpc);
            dp[i] = min;
            if (min == dpa) a++;
            if (min == dpb) b++;
            if (min == dpc) c++;
        }
        return dp[n - 1];
    }
}

class Solution {
    public int nthUglyNumber(int n) {
        PriorityQueue priorityQueue = new PriorityQueue();
        Set<Long> set = new HashSet();
        long[] factors = new long[] {2, 3, 5};
        for (long factor : factors) {
            priorityQueue.offer(factor);
            set.add(factor);
        }
        long result = 1;
        for (int i = 1; i < n; i++) {
            result = (long)priorityQueue.poll();
            for (int j = 0; j < 3; j++) {
                long temp = result * factors[j];
                if (!set.contains(temp)) {
                    priorityQueue.offer(temp);
                    set.add(temp);
                }
            }
        }
        return (int)result;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1.HashMap先为每个元素的个数计数
        // 2.利用小顶堆记录频率最高的前k个元素
        // 3.从小顶堆中取出数据进行组装
        Map<Integer, Integer> map = new HashMap();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        PriorityQueue<Integer> littleHeap = new PriorityQueue((n1 ,n2) -> map.get(n1) - map.get(n2));
        for (int count : map.keySet()) {
            littleHeap.add(count);
            if (littleHeap.size() > k) {
                littleHeap.poll();
            }
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (!littleHeap.isEmpty()) {
            list.add(littleHeap.poll());
        }
        Collections.reverse(list);
        int[] top_k = new int[k];
        for (int i = 0; i < k; i++) {
            top_k[i] = list.get(i);
        }
        return top_k;
    }
}

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1.使用字典统计个数
        // 2.根据个数作为下标存入List中
        // 3.整理数据输出
        Map<Integer, Integer> map = new HashMap();
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        List<Integer>[] list = new ArrayList[nums.length + 1];
        for (Integer num: map.keySet()) {
            if (list[map.get(num)] == null) {
                list[map.get(num)] = new ArrayList<>();
            }
            list[map.get(num)].add(num);
        }
        List<Integer> result = new ArrayList();
        for (int i = nums.length; i >= 0 && result.size() < k; i--) {
            if (list[i] == null) continue;
            result.addAll(list[i]);
        }
        int[] top_k = new int[k];
        for (int i = 0; i < k; i++) {
            top_k[i] = result.get(i);
        }
        return top_k;
    }
}