【 NO.1 将字符串拆分为若干长度为 k 的组】
解题思路
签到题。
代码展现
class Solution {
public String[] divideString(String s, int k, char fill) {
String[] res = new String[(s.length() + k - 1) / k]; for (int i = 0; i < res.length; i++) { if (k * i + k <= s.length()) { res[i] = s.substring(k * i, k * i + k); } else { res[i] = s.substring(k * i) + repeat(fill, k - (s.length() - k * i)); } } return res;}
private String repeat(char fill, int i) {
StringBuilder sb = new StringBuilder(); for (; i > 0; i--) { sb.append(fill); } return sb.toString();}
}
【 NO.2 失去目标值的起码口头次数】
解题思路
逆序贪婪，优先用除法。
代码展现
class Solution {
public int minMoves(int target, int maxDoubles) {
if (target == 1) { return 0; } if (maxDoubles == 0) { return target - 1; } if (target % 2 == 1) { return minMoves(target - 1, maxDoubles) + 1; } return minMoves(target / 2, maxDoubles - 1) + 1;}
}
【 NO.3 解决智力问题】
解题思路
动静布局，定义状态 f[i] 示意解决问题 i 时，前 i 个问题最多失去的分数
则有状态转移方程 f[i] = max(f[j]) + score[i], 其中 j 满足 forbid[j] + j < i
应用 TreeMap 保护 forbid[j] + j 即可
代码展现
class Solution {
public long mostPoints(int[][] questions) {
long[] f = new long[questions.length]; f[0] = questions[0][0]; TreeMap<Integer, Long> cand = new TreeMap<>(); cand.put(questions[0][1], f[0]); long max = 0; for (int i = 1; i < f.length; i++) { while (!cand.isEmpty() && cand.firstKey() < i) { var e = cand.pollFirstEntry(); max = Math.max(max, e.getValue()); } f[i] = questions[i][0] + max; int key = questions[i][1] + i; cand.put(key, Math.max(cand.getOrDefault(key, 0L), f[i])); } return Arrays.stream(f).max().getAsLong();}
}
【 NO.4 同时运行 N 台电脑的最长工夫】
解题思路
二分答案，详见正文。
代码展现
class Solution {
public long maxRunTime(int n, int[] batteries) {
long l = 1, r = Arrays.stream(batteries).mapToLong(i -> i).sum() / n; while (l + 1 < r) { long mid = (l + r) / 2; if (check(n, batteries, mid)) { l = mid; } else { r = mid; } } return check(n, batteries, r) ? r : l;}
// 判断电池是否供应 n 台电脑应用 time 分钟
// 相当于每块电池最多应用 time 分钟
// 如果一块电池容量小于 time 分钟，那么它须要和其余电池拼一起能力组成 time 分钟
// 如果一块电池容量多于 time 分钟，那么能够认为它将被节约，能够认为这个电池容量只有 time 分钟
// 因为换电池是不耗费工夫的，所以只需查看电池容量之和是否达到了 time * n 即可
private boolean check(int n, int[] batteries, long time) {
return Arrays.stream(batteries).mapToLong(i -> Math.min((long) i, time)).sum() >= n * time;}
}