1、扑克牌重新洗牌

代码

import java.util.ArrayList;

public class Solution {

    public int[] fun(int[] nums) {
        ArrayList<Integer>[] lists = new ArrayList[4];
        for (int i = 0; i < lists.length; i++) {
            lists[i] = new ArrayList<>();
        }
        for (int num : nums) {
            lists[num / 20].add(num);
        }

        int index = 0;
        for (ArrayList<Integer> list : lists) {
            for (int num : list) {
                nums[index ++] = num;
            }
        }
        return nums;
    }

}

2、找到和为target的二叉树所有路径

代码

import java.util.ArrayList;
import java.util.List;

public class Solution {

    public static class TreeNode{
        int val;
        TreeNode left;
        TreeNode right;
    }

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

    public List<List<Integer>> fun(TreeNode root, int target) {
        if (root == null) {
            return res;
        }
        dfs(root, target, 0, new ArrayList<>());
        fun(root.left, target);
        fun(root.right, target);
        return res;
    }
    
    private void dfs(TreeNode root, int target, int curSum, List<Integer> curList) {
        if (root == null) {
            return;
        }
        if (curSum == target) {
            res.add(new ArrayList<>(curList));
        }
        if (root.left == null && root.right == null) {
            // 叶子结点
            return;
        }
        curList.add(root.val);
        dfs(root.left, target, curSum + root.val, curList);
        dfs(root.right, target, curSum + root.val, curList);
        curList.remove(curList.size() - 1);
    }

}

3、剧本杀

代码

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

public class Solution {

    public String fun(String str) {

        char[] cs = str.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (char c : cs) {
            int count = map.getOrDefault(c, 0);
            map.put(c, count + 1);
        }
        PriorityQueue<Character> heap = new PriorityQueue<>(Comparator.comparingInt(v -> -map.get(v)));
        for (char c : map.keySet()) {
            heap.add(c);
        }
        char c = heap.element();
        if (map.get(c) > (cs.length + 1) / 2) {
            return "";
        }
        char curChar = 'a';
        int curCount = 0;
        for (int i = 0; i < cs.length; i += 2) {
            if (curCount == 0) {
                curChar = heap.remove();
                curCount = map.get(curChar);
            }
            curCount --;
            cs[i] = curChar;
        }
        for (int i = 1; i < cs.length; i += 2) {
            if (curCount == 0) {
                curChar = heap.remove();
                curCount = map.get(curChar);
            }
            curCount --;
            cs[i] = curChar;
        }
        return new String(cs);
    }

}

4、进阶版剧本杀

上一题的进阶版，
input: 3 4 2 1 3 3
output: 540
假设有6个人a, b, c, d, e, f，每个人可以发言的次数分别为3 4 2 1 3 3，求没有人连着发言的发言次数。

代码

import java.util.Arrays;

public class Solution {

    private static final int INF = 1_000_000_000 + 7;

    public int fun(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        int len = nums.length;
        Arrays.sort(nums);
        int max = nums[len - 1];
        if (nums[len - 2] == max) {
            return (int) factorial(len, len);
        }
        if (nums[len - 2] + 1 < max) {
            return 0;
        }
        int i = len - 2;
        while (i - 1 >= 0 && nums[i - 1] == nums[len - 2]) {
            i --;
        }
        // [i, len-2]之间都是
        int count = len - 2 - i + 1;
        return (int) ((factorial(count + 1, count + 1) - factorial(count, count)) * factorial(len, len - count - 1) % INF);
    }

    /**
     * 计算
     *
     * @param n
     * @param m
     * @return
     */
    private long factorial(int n, int m) {
        long res = 1;
        for (int i = n; i > n - m; i --) {
            res = (res * i) % INF;
        }
        return res;
    }

}