/**

/**

public boolean isAnagram(String s, String t) {

if (s.length() != t.length())

return false;

int[] alpha = new int[26];

for (int i = 0; i < s.length(); i++) {

alpha[s.charAt(i) - 'a']++;

alpha[t.charAt(i) - 'a']--;

}

// return Arrays.stream(alpha).noneMatch(num -> num != 0); //合并下面操作

for (int i = 0; i < 26; i++) {

if (alpha[i] != 0)

return false;

}

return true;

}

public boolean isAnagram2(String s, String t) {

if (s.length() != t.length()) {

return false;

}

char[] s1 = s.toCharArray();

char[] t2 = t.toCharArray();

Arrays.sort(s1);

Arrays.sort(t2);

for (int i = 0; i < s1.length; i++) {

if (s1[i] != t2[i]) {

return false;

}

}

return true;

}

// Valid anagram

public boolean isAnagram3(String s, String t) {

if (s.length() != t.length()) return false;

int[] a = new int[26];

for (Character c : s.toCharArray()) a[c - 'a']++;

for (Character c : t.toCharArray()) {

if (a[c - 'a'] == 0) return false;

a[c - 'a']--;

}

return true;

}

public boolean isAnagram4(String s1, String s2) {

int[] freq = new int[256];

for (int i = 0; i < s1.length(); i++) freq[s1.charAt(i)]++;

for (int i = 0; i < s2.length(); i++) if (--freq[s2.charAt(i)] < 0) return false;

return s1.length() == s2.length();

}

public boolean isAnagram5(String s, String t) {

char[] sChar = s.toCharArray();

char[] tChar = t.toCharArray();

Arrays.sort(sChar);

Arrays.sort(tChar);

return Arrays.equals(sChar, tChar);

}

/**

public List<List<String>> groupAnagrams(String[] strs) {

HashMap<String, ArrayList<String>> map = new HashMap<>();

for (String s : strs) {

char[] ch = s.toCharArray();

Arrays.sort(ch);

String key = String.valueOf(ch);

if (!map.containsKey(key))

map.put(key, new ArrayList<>());

map.get(key).add(s);

}

return new ArrayList<>(map.values());

}

// 字母异位词分组 2ed 方法

public List<List<String>> groupAnagrams2(String[] strs) {

Map<String, List<String>> map = new HashMap<>();

for (String str : strs) {

char[] chars = str.toCharArray();

Arrays.sort(chars);

map.computeIfAbsent(new String(chars), k -> new ArrayList<>()).add(str);

}

return new ArrayList<>(map.values());

}

// Group Anagrams:

public List<List<String>> groupAnagrams3(String[] strs) {

List<List<String>> res = new ArrayList<>();

HashMap<String, List<String>> map = new HashMap<>();

Arrays.sort(strs);

for (int i = 0; i < strs.length; i++) {

String temp = strs[i];

char[] ch = temp.toCharArray();

Arrays.sort(ch);

if (map.containsKey(String.valueOf(ch))) {

map.get(String.valueOf(ch)).add(strs[i]);

} else {

List<String> each = new ArrayList<>();

each.add(strs[i]);

map.put(String.valueOf(ch), each);

}

}

for (List<String> item : map.values()) {

res.add(item);

}

return res;

}

/**

public List<List<String>> groupAnagrams4(String[] strs) {

return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> {

// 返回 str 排序后的结果。

// 按排序后的结果来grouping by，算子类似于 sql 里的 group by。

char[] array = str.toCharArray();

Arrays.sort(array);

return new String(array);

})).values());

}

/**

public List<List<String>> groupAnagrams5(String[] strs) {

// str -> intstream -> sort -> collect by StringBuilder

return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> str.chars().sorted().collect(StringBuilder::new, StringBuilder::appendCodePoint, StringBuilder::append).toString())).values());

}

/**

public List<List<String>> groupAnagrams6(String[] strs) {

// str -> split -> stream -> sort -> join

return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> Stream.of(str.split("")).sorted().collect(Collectors.joining()))).values());

}

/**

public List<List<String>> groupAnagrams7(String[] strs) {

return new ArrayList<>(Arrays.stream(strs).collect(Collectors.groupingBy(str -> {

int[] counter = new int[26];

for (int i = 0; i < str.length(); i++) {

counter[str.charAt(i) - 'a']++;

}

StringBuilder sb = new StringBuilder();

for (int i = 0; i < 26; i++) {

// 这里的 if 是可省略的，但是加上 if 以后，生成的 sb 更短，后续 groupingBy 会更快。

if (counter[i] != 0) {

sb.append((char) ('a' + i));

sb.append(counter[i]);

}

}

return sb.toString();

})).values());

}

/**

public List<Integer> preorderTraversal(TreeNode root) {

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

if (root == null) return list;

dfs(list, root);

return list;

}

public void dfs(List<Integer> list, TreeNode root) {

if (root == null) return;

list.add(root.val);

dfs(list, root.left);

dfs(list, root.right);

}

/**

/**

public List<Integer> inorderTraversal(TreeNode root) {

List<Integer> res = new ArrayList<Integer>();

dfsInorderTraversal(res, root);

return res;

}

void dfsInorderTraversal(List<Integer> res, TreeNode root) {

if (root == null) {

return;

}

//按照 左-打印-右的方式遍历

dfsInorderTraversal(res, root.left);

res.add(root.val);

dfsInorderTraversal(res, root.right);

}

/**

public List<Integer> preorder(Node root) {

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

helper(root, list);

return list;

}

public void helper(Node root, List<Integer> list) {

if (root == null) return;

list.add(root.val);

for (Node child : root.children) {

helper(child, list);

}

}

/**

public List<Integer> preorder2(Node root) {

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

Deque<Node> stack = new LinkedList<>();

stack.push(root);

if (root == null) return list;

while (!stack.isEmpty()) {

//当前栈顶节点出栈

Node node = stack.pop();

//将值加入列表

list.add(node.val);

int size = node.children.size();

//将当前节点的孩子们从右到左入栈

for (int i = size - 1; i >= 0; i--) {

stack.push(node.children.get(i));

}

}

return list;

}

/**

public List<Integer> postorder(Node root) {

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

if (root == null) return list;

Stack<Node> stack = new Stack<>();

stack.add(root);

while (!stack.isEmpty()) {

root = stack.pop();

list.add(root.val);

for (Node node : root.children)

stack.add(node);

}

Collections.reverse(list);

return list;

}

/**

public List<Integer> postorder2(Node root) {

List<Integer> list = new LinkedList<>();

if (root == null)

return list;

for (Node child : root.children) {

list.addAll(postorder2(child));

}

list.add(root.val);

return list;

}

/**

public List<Integer> postorder3(Node root) {

LinkedList<Integer> list = new LinkedList<Integer>();

if (root == null)

return list;

Stack<Node> stack = new Stack<Node>();

stack.push(root);

while (!stack.isEmpty()) {

Node node = stack.pop();

List<Node> child = node.children;

list.addFirst(node.val);

for (Node no : child) {

stack.push(no);

}

}

return list;

}

/**

public List<List<Integer>> levelOrder(Node root) {

List<List<Integer>> result = new ArrayList<>();

if (root == null) return result;

Queue<Node> queue = new LinkedList<>();

queue.add(root);

while (!queue.isEmpty()) {

List<Integer> level = new ArrayList<>();

int size = queue.size();

for (int i = 0; i < size; i++) {

Node node = queue.poll();

level.add(node.val);

queue.addAll(node.children);

}

result.add(level);

}

return result;

}

/**

public List<List<Integer>> levelOrder2(Node root) {

List<List<Integer>> result = new ArrayList<>();

if (root == null) return result;

List<Node> previousLayer = Arrays.asList(root);

while (!previousLayer.isEmpty()) {

List<Node> currentLayer = new ArrayList<>();

List<Integer> previousVals = new ArrayList<>();

for (Node node : previousLayer) {

previousVals.add(node.val);

currentLayer.addAll(node.children);

}

result.add(previousVals);

previousLayer = currentLayer;

}

return result;

}

/**

public List<List<Integer>> levelOrder3(Node root) {

List<List<Integer>> ans = new ArrayList<>();

if (root == null) return ans;

leveltravel(ans, 0, root);

return ans;

}

private void leveltravel(List<List<Integer>> ans, int level, Node root) {

if (root == null) return;

if (ans.size() < level + 1) ans.add(new ArrayList<Integer>());

ans.get(level).add(root.val);

int childnum = root.children.size();

for (int j = 0; j < childnum; j++)

leveltravel(ans, level + 1, root.children.get(j));

}

/**

public int[] getLeastNumbers(int[] arr, int k) {

int[] vec = new int[k];

Arrays.sort(arr);

for (int i = 0; i < k; ++i) {

vec[i] = arr[i];

}

return vec;

}

/**

public int[] getLeastNumbers2(int[] arr, int k) {

int[] vec = new int[k];

if (k == 0) { // 排除 0 的情况

return vec;

}

PriorityQueue<Integer> queue = new PriorityQueue<Integer>((num1, num2) -> num2 - num1);

for (int i = 0; i < k; ++i) {

queue.offer(arr[i]);

}

for (int i = k; i < arr.length; ++i) {

if (queue.peek() > arr[i]) {

queue.poll();

queue.offer(arr[i]);

}

}

for (int i = 0; i < k; ++i) {

vec[i] = queue.poll();

}

return vec;

}

/**

public int[] getLeastNumbers3(int[] arr, int k) {

if (k == 0 || arr.length == 0)//如果数组为空或者是选取最小的0个数

return new int[0];//直接返回空数组

return quickSort(arr, 0, arr.length - 1, k - 1);//调用quickSort函数输出结果，其中k-1指的是找到下标为k-1的数

}

public int[] quickSort(int[] num, int left, int right, int k) {

int point = partition(num, left, right);//调用partition函数输出划分后分界点的坐标point（point前面的数都比其小，后面的数都比其大）

if (point == k)//如果分界点的坐标正好是k，就说明前k+1个数就是最小的k个数（即0,1,2,...，k）

return Arrays.copyOf(num, k + 1);//调用Arrays方法输出前k+1个数

else

return point > k ? quickSort(num, left, point - 1, k) : quickSort(num, point + 1, right, k);

//根据分界点的坐标继续在两个子区间中的其中一个对其进行划分，直至分界点的坐标恰好为k

}

public int partition(int[] num, int left, int right) {

int l = left, r = right + 1, t = num[left];//以t=num[left]为基准对数组进行划分，即小基准大

while (true)//用while循环完成一次对数组的划分

{

while (++l < right && num[l] < t) ;

while (--r > left && num[r] > t) ;

if (l >= r)//循环结束条件

break;

int temp = num[l];//num[l]比基准大，num[r]比基准小，交换两者

num[l] = num[r];

num[r] = temp;

}

num[left] = num[r];//完成对数组的一次划分后，num[r]比基准小（且是数组中比基准小的最后一个元素），将num[r]和基准交换，

num[r] = t;

return r;//将分界点坐标返回

}

/**

public int[] getLeastNumbers4(int[] arr, int k) {

if (k == 0 || arr.length == 0)

return new int[0];

Queue<Integer> queue = new PriorityQueue<>((v1, v2) -> v2 - v1);//默认小根堆，实现大根堆需要重写比较器（λ函数）

int t = 0, res[] = new int[k];

for (int num : arr) {

if (queue.size() < k)//如果大根堆的规模小于k，就将数组中的数入队

queue.add(num);

else if (queue.peek() > num)

//否则就取出队列中最大的数与数组中的数进行比较，如果队列中的数比较大，就将其出队，将数组中的数入队，最终即可实现队中为数组前k小

{

queue.poll();

queue.add(num);

}

}

for (int num : queue) {//将队列中留下的数输出到数组中，即可得到答案

res[t++] = num;

}

return res;

}

/**

public int[] getLeastNumbers5(int[] arr, int k) {

if (k == 0 || arr.length == 0)

return new int[0];

Queue<Integer> queue = new PriorityQueue<>();//定义小根堆

int t = 0;

int[] res = new int[k];

for (int num : arr)

queue.add(num);

while (t < k) {

res[t++] = queue.poll().intValue();

}

return res;

}

/**

/**

public int nthUglyNumber(int n) {

int a = 0, b = 0, c = 0;

int[] dp = new int[n];

dp[0] = 1;

for (int i = 1; i < n; i++) {

int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;

dp[i] = Math.min(Math.min(n2, n3), n5);

if (dp[i] == n2) a++;

if (dp[i] == n3) b++;

if (dp[i] == n5) c++;

}

return dp[n - 1];

}

/**

public int[] topKFrequent(int[] nums, int k) {

Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();

for (int num : nums) {

occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);

}

// int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数

PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {

public int compare(int[] m, int[] n) {

return m[1] - n[1];

}

});

for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {

int num = entry.getKey(), count = entry.getValue();

if (queue.size() == k) {

if (queue.peek()[1] < count) {

queue.poll();

queue.offer(new int[]{num, count});

}

} else {

queue.offer(new int[]{num, count});

}

}

int[] ret = new int[k];

for (int i = 0; i < k; ++i) {

ret[i] = queue.poll()[0];

}

return ret;

}

/**

public int[] topKFrequent2(int[] nums, int k) {

Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();

for (int num : nums) {

occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);

}

List<int[]> values = new ArrayList<int[]>();

for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {

int num = entry.getKey(), count = entry.getValue();

values.add(new int[]{num, count});

}

int[] ret = new int[k];

qsort(values, 0, values.size() - 1, ret, 0, k);

return ret;

}

public void qsort(List<int[]> values, int start, int end, int[] ret, int retIndex, int k) {

int picked = (int) (Math.random() * (end - start + 1)) + start;

Collections.swap(values, picked, start);

int pivot = values.get(start)[1];

int index = start;

for (int i = start + 1; i <= end; i++) {

if (values.get(i)[1] >= pivot) {

Collections.swap(values, index + 1, i);

index++;

}

}

Collections.swap(values, start, index);

if (k <= index - start) {

qsort(values, start, index - 1, ret, retIndex, k);

} else {

for (int i = start; i <= index; i++) {

ret[retIndex++] = values.get(i)[0];

}

if (k > index - start + 1) {