【 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<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];}
}
【 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;}
}