【 NO.1 学生分数的最小差值】

解题思路

排序，然后枚举每连续的 K 个元素即可。

代码展示

class Solution {

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

       if (nums.length < 2 || k == 1) {

           return 0;

      }

       Arrays.sort(nums);

       int res = nums[k - 1] - nums[0];

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

           res = Math.min(res, nums[i] - nums[i - k + 1]);

      }

       return res;

  }

}

【 NO.2 找出数组中的第 K 大整数】

解题思路

按照数值从大到小排序即可。

代码展示

class Solution {

   public String kthLargestNumber(String[] nums, int k) {

       Arrays.sort(nums, (a, b) -> {

           if (a.length() != b.length()) {

               return b.length() - a.length();

          }

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

               if (a.charAt(i) != b.charAt(i)) {

                   return b.charAt(i) - a.charAt(i);

              }

          }

           return 0;

      });

       return nums[k - 1];

  }

}

【 NO.3 完成任务的最少工作时间段】

解题思路

状态压缩动态规划，另 dp[i] 表示剩余的任务集合为 i 时，需要的最少工作时间段。

状态转移则是枚举下一个工作时间段做哪些任务，即 dp[i] = min(dp[j]) + 1 其中集合 i 减去集合 j 所代表的任务可以在一个工作时间段内完成。

代码展示

class Solution {

   public int minSessions(int[] tasks, int sessionTime) {

       int[] mem = new int[1 << tasks.length];

       Arrays.fill(mem, -1);

       mem[0] = 0;

       return dp((1 << tasks.length) - 1, tasks, sessionTime, mem);

  }

   private int dp(int i, int[] tasks, int sessionTime, int[] mem) {

       if (mem[i] >= 0) {

           return mem[i];

      }

       mem[i] = tasks.length;

       // 枚举这一个时间段完成哪些任务

       for (int j = 1; j < (1 << tasks.length); j++) {

           if ((i | j) != i) {

               continue;

          }

           int tot = 0;

           int ni = i;

           for (int k = 0; k < tasks.length; k++) {

               if (((1 << k) & j) > 0) {

                   tot += tasks[k];

                   ni -= 1 << k;

              }

          }

           if (tot <= sessionTime) {

               mem[i] = Math.min(mem[i], dp(ni, tasks, sessionTime, mem) + 1);

          }

      }

       return mem[i];

  }

}

但是，上面的代码会超时，因此我们增加一个小优化：逆序枚举 j，即优先枚举更大的集合，并且在递归计算前判断，如果一个包含 j 的集合已经被递归过了，则不再进行递归计算 —— 贪心的思想。

class Solution {

   public int minSessions(int[] tasks, int sessionTime) {

       int[] mem = new int[1 << tasks.length];

       Arrays.fill(mem, -1);

       mem[0] = 0;

       return dp((1 << tasks.length) - 1, tasks, sessionTime, mem);

  }

   private int dp(int i, int[] tasks, int sessionTime, int[] mem) {

       if (mem[i] >= 0) {

           return mem[i];

      }

       mem[i] = tasks.length;

       List visited = new ArrayList<>();

       for (int j = (1 << tasks.length) - 1; j > 0; j--) {

           if ((i | j) != i) {

               continue;

          }

           boolean skip = false;

           for (int v : visited) {

               if ((v | j) == v) {

                   skip = true;

                   break;

              }

          }

           if (skip) {

               continue;

          }

           int tot = 0;

           int ni = i;

           for (int k = 0; k < tasks.length; k++) {

               if (((1 << k) & j) > 0) {

                   tot += tasks[k];

                   ni -= 1 << k;

              }

          }

           if (tot <= sessionTime) {

               visited.add(j);

               mem[i] = Math.min(mem[i], dp(ni, tasks, sessionTime, mem) + 1);

          }

      }

       return mem[i];

  }

}

【 NO.4 从子集的和还原数组】

解题思路

这道题目相当于不同的子序列 II 的 follow up

可以先参考这道题目的官方题解

代码展示

class Solution {

   public int numberOfUniqueGoodSubsequences(String binary) {

       final long mod = (long) (1e9 + 7);

       long res = 0;

       long[] last = {0, 0};

       for (char c : binary.toCharArray()) {

           int i = c - '0';

           long cur = (res + i - last[i] + mod) % mod;

           res = (res + cur) % mod;

           last[i] = (last[i] + cur) % mod;

      }

       if (binary.contains("0")) {

           res = (res + 1) % mod;

      }

       return (int) res;

  }

}