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

上岸算法 · 发表于 2021-8-30 23:30:33

登录后可回复主题

您需要登录才可以下载或查看，没有帐号？注册账号

x

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

}

}

帐号		自动登录	找回密码
密码			注册账号

[吹水聊天] 上岸算法 LeetCode Weekly Contest 256解题报告

登录后可回复主题