共计 2339 个字符，预计需要花费 6 分钟才能阅读完成。
【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;}
}
