NO.1 The minimum difference of students’ scores

Their thinking

Sort, then enumerate each consecutive K elements.

The code shown

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; }}Copy the code

NO.2 Find the KTH large integer in array

Their thinking

Sort them in order of the largest to the smallest number.

The code shown

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]; }}Copy the code

No.3 Minimum working time to complete tasks

Their thinking

In addition, dp[I] represents the minimum working time required when the remaining task set is I.

The state transition is to enumerate what tasks to do in the next working period, that is, dp[I] = min(dp[j]) + 1 where the tasks represented by set I minus set j can be completed in a working period.

The code shown

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]; }}Copy the code
However, the above code would time out, so we added a small optimization: enumerating j in reverse order, that is, enumerating larger sets first, and determining, before recursing, that if a set containing J has already been recursed, no recursion will be performed - greedy thinking.Copy the code
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<Integer> 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];
  }
} 
Copy the code

No.4 Restoring an array from the sum of subsets

Their thinking

This problem is equivalent to the follow up of different subsequences II

You can first refer to the official solution of this problem

The code shown

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; }}Copy the code