• 这几年比赛打少了，感觉自己太菜了，这场手速题证明自己压根儿没有手速
• 第三题想了半天的 dp，有点思路的时候发现不需要取模而且返回值是 int，我去直接暴力可过
• 最后一题赛后五分钟才过，一声叹息

• 题目：

  • 美丽子集的数目
  • 给你一个由正整数组成的数组 nums 和一个 正 整数 k 。
  • 如果 nums 的子集中，任意两个整数的绝对差均不等于 k ，则认为该子数组是一个 美丽 子集。
  • 返回数组 nums 中 非空 且 美丽 的子集数目。
  • nums 的子集定义为：可以经由 nums 删除某些元素（也可能不删除）得到的一个数组。只有在删除元素时选择的索引不同的情况下，两个子集才会被视作是不同的子集。
  • 1 <= nums.length <= 20
  • 1 <= nums[i], k <= 1000

• 解法：

  • 暴力先放到一边，咋们来推 DP
  • 数组先升序排序，然后遍历、将相同元素以及连续相差 k 的元素放在一起，元素通过 HashMap 整理成 g 组，
    • HashMap 的 key 存每组最大的元素，value 存此组所有元素，
    • 遍历元素时，查询等于当前元素、存在则加入该元素，查询小于 k 的元素、存在则加入该元素更新 key，都不存在新建组
  • 然后将 g 组排列在一起（无关顺序），此时相同元素全排在一起，
  • 比任意元素大 k 元素要么不存在、要么一定排在去除它相同元素的后一个
  • 比如：k 为 2，数组可能组成：2 2 4 4 4 1 1 3 3 5 9
  • 然后模拟 01 背包，设计一个 dp[i][j]，i 代表 [0, i] 这些元素，j 仅有 0-不取当前元素、1-取当前元素，
  • 初始化 dp[0][0] == 0，dp[0][1] == 1，递推方程式 dp[i][0] = dp[i-1][0] + dp[i-1][1]，dp[i][1] 需要分类讨论：
    • 为了方便，设计一个 s 数组，代表当前元素前面有多少个与其相同，含当前元素
    • 再设计一个 prefixDp1 数组，代表 dp[i][1] 的前缀和
    • i 比 i-1 元素大 k，i-1 与前面相同的都不选：dp[i][1] = 1 + dp[i-1-s[i-1]][0] + dp[i-1-s[i-1]][1]，i-1-s[i-1] 小于 0 则不需要
    • i 和 i-1 元素相同，可能 i-1 前面存在比 i 小 k 的元素：
      • 如果相同元素前面没有数据了，即 i-s[i] 小于 0：dp[i][1] = 1 + dp[i-1][0] + dp[i-1][1]
      • 如果 i 比 i-s[i] 大 k，先选任意与 i 相同的、然后与上一条一致跳过 i-1 及相同：dp[i][1] = 1 + (dp[i - s[i] + 1][1] + … + dp[i - 1][1]) + (dp[i - s[i] + 1][1] - 1)
      • 否则随意选：dp[i][1] = 1 + dp[i-1][0] + dp[i-1][1]
    • 否则随意选：dp[i][1] = 1 + dp[i-1][0] + dp[i-1][1]
  • 最后注意，如果个数很多结果极可能超过 int，所以添加一个取模
  • 时间复杂度：O(nlogn)，空间复杂度：O（n）

代码：

    /*** 数组先升序排序，然后遍历、将相同元素以及连续相差 k 的元素放在一起，元素通过 HashMap 整理成 g 组，*     HashMap 的 key 存每组最大的元素，value 存此组所有元素，*     遍历元素时，查询等于当前元素、存在则加入该元素，查询小于 k 的元素、存在则加入该元素更新 key，都不存在新建组* 然后将 g 组排列在一起（无关顺序），此时相同元素全排在一起，* 比任意元素大 k 元素要么不存在、要么一定排在去除它相同元素的后一个* 比如：k 为 2，数组可能组成：2 2 4 4 4 1 1 3 3 5 9* 然后模拟 01 背包，设计一个 dp[i][j]，i 代表 [0, i] 这些元素，j 仅有 0-不取当前元素、1-取当前元素，* 初始化 dp[0][0] == 0，dp[0][1] == 1，递推方程式 dp[i][0] = dp[i-1][0] + dp[i-1][1]，dp[i][1] 需要分类讨论：*     为了方便，设计一个 s 数组，代表当前元素前面有多少个与其相同，含当前元素*     再设计一个 prefixDp1 数组，代表 dp[i][1] 的前缀和*     i 比 i-1 元素大 k，i-1 与前面相同的都不选：dp[i][1] = 1 + dp[i-1-s[i-1]][0] + dp[i-1-s[i-1]][1]，i-1-s[i-1] 小于 0 则不需要*     i 和 i-1 元素相同，可能 i-1 前面存在比 i 小 k 的元素：*         如果相同元素前面没有数据了，即 i-s[i] 小于 0：dp[i][1] = 1 + dp[i-1][0] + dp[i-1][1]*         如果 i 比 i-s[i] 大 k，先选任意与 i 相同的、然后与上一条一致跳过 i-1 及相同：dp[i][1] = 1 + (dp[i - s[i] + 1][1] + ... + dp[i - 1][1]) + (dp[i - s[i] + 1][1] - 1)*         否则随意选：dp[i][1] = 1 + dp[i-1][0] + dp[i-1][1]*     否则随意选：dp[i][1] = 1 + dp[i-1][0] + dp[i-1][1]*/private int solution(int[] nums, int k) {// 数据比较大则结果需要对大质数取模int mod = 1_000_000_007;int len = nums.length;// 相同元素全排在一起，比任意元素大 k 元素要么不存在、要么一定排在去除它相同元素的后一个int[] groupNums = groupKNums(nums, k);int[] same = new int[len];same[0] = 1;int[][] dp = new int[len][2];dp[0][1] = 1;int[] prefixDp1 = new int[len];prefixDp1[0] = 1;for (int i = 1; i < groupNums.length; i++) {dp[i][0] = (dp[i - 1][0] + dp[i - 1][1])%mod;if (groupNums[i] == groupNums[i - 1]) {same[i] = same[i - 1] + 1;} else {same[i] = 1;}
//            System.out.print(groupNums[i] + " ");if (groupNums[i] - groupNums[i - 1] == k) {int difi1 = i - 1 - same[i - 1];if (difi1 < 0) {
//                    System.out.print("01 ");dp[i][1] = 1;} else {
//                    System.out.print("02 ");dp[i][1] = 1 + dp[difi1][0] + dp[difi1][1];}} else if (groupNums[i] == groupNums[i - 1]) {int difi = i - same[i];if (difi < 0) {
//                    System.out.print("03 ");dp[i][1] = 1 + dp[i - 1][0] + dp[i - 1][1];} else if (groupNums[i] - groupNums[difi] == k) {
//                    System.out.print("04 ");dp[i][1] = 1 + (prefixDp1[i - 1] - prefixDp1[difi] + mod) % mod + (dp[difi + 1][1] - 1);} else {
//                    System.out.print("05 ");dp[i][1] = 1 + dp[i - 1][0] + dp[i - 1][1];}} else {
//                System.out.print("06 ");dp[i][1] = 1 + dp[i - 1][0] + dp[i - 1][1];}dp[i][1] %= mod;
//            System.out.println(dp[i][1]);prefixDp1[i] = (prefixDp1[i - 1] + dp[i][1]) % mod;}
//        System.out.println(Arrays.toString(same));
//        System.out.println(Arrays.toString(prefixDp1));
//        for (int i = 0; i < dp.length; i++) {
//            System.out.println(dp[i][0] + ":" + dp[i][1]);
//        }return (dp[len - 1][0] + dp[len - 1][1]) % mod;}private int[] groupKNums(int[] nums, int k) {// 升序排序Arrays.sort(nums);// 按照 k 拆分 g 组到 HasaMapMap> groupMap = new HashMap<>((nums.length << 2) / 3);for (int num : nums) {List numList = groupMap.getOrDefault(num, null);if (numList != null) {numList.add(num);continue;}int preNum = num - k;List preNumList = groupMap.getOrDefault(num - k, null);if (preNumList != null) {preNumList.add(num);groupMap.put(num, preNumList);groupMap.put(preNum, null);continue;}numList = new ArrayList<>();numList.add(num);groupMap.put(num, numList);}
//        groupMap.forEach((key, val) -> {System.out.println(key + ":" + val);});int[] groupNums = new int[nums.length];int index = 0;// g 组排列在一起for (Map.Entry> entry : groupMap.entrySet()) {List groupList = entry.getValue();if (groupList == null) {continue;}for (Integer groupNum : groupList) {groupNums[index] = groupNum;index++;}}
//        System.out.println(Arrays.toString(groupNums));return groupNums;}