# 【上岸算法】LeetCode Weekly Contest 256解题报告

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

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 完成任务的最少工作时间段】

class Solution {
public int minSessions(int[] tasks, int sessionTime) {
int[] mem = new int[1 << tasks.length];
Arrays.fill(mem, -1);
mem[0] = 0;
}

private int dp(int i, int[] tasks, int sessionTime, int[] mem) {
if (mem[i] >= 0) {
return mem[i];
}
// 枚举这一个时间段完成哪些任务
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) {
ni -= 1 << k;
}
}
if (tot <= sessionTime) {
mem[i] = Math.min(mem[i], dp(ni, tasks, sessionTime, mem) + 1);
}
}
return mem[i];
}
}

class Solution {
public int minSessions(int[] tasks, int sessionTime) {
int[] mem = new int[1 << tasks.length];
Arrays.fill(mem, -1);
mem[0] = 0;
}

private int dp(int i, int[] tasks, int sessionTime, int[] mem) {
if (mem[i] >= 0) {
return mem[i];
}
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) {
ni -= 1 << k;
}
}
if (tot <= sessionTime) {
mem[i] = Math.min(mem[i], dp(ni, tasks, sessionTime, mem) + 1);
}
}
return mem[i];
}
}

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

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