前言
在太阳西斜的这个世界，置身天上之森。
等这场战争结束后，不归之人与望眼欲穿的众人，人人本着正义之名，长存不灭的过去，逐渐消逝的未来。
我回来了，纵使日薄西山，即使看不见未来，此时此刻的光辉，盼君勿忘。
整体评价
t2思维题，不过恢复构造有些麻烦，不错的题。
t3的题意，稍有些歧义，如果理解不对，那这题太难了。
t4中规中矩的DP题，稍显水的压轴题。
更多解题报告详见：珂朵莉MM的解题报告汇总
1. 盒子中小球的最大数量
因为t1，数据规模较小，就用了Brute Force。
不过这里需要注意，返回的数量，而不是具体盒子的编号。
如果这题范围放大，那就麻烦了
Java
class Solution {
int compute(int v) {
int res = 0;
while (v > 0) {
res += v % 10;
v /= 10;
}
return res;
}
public int countBalls(int lowLimit, int highLimit) {
int ans = 0;
Map<Integer, Integer> hash = new HashMap<>();
for (int i = lowLimit; i <= highLimit; i++) {
int t = compute(i);
hash.put(t, hash.getOrDefault(t, 0) + 1);
if (hash.get(t) > ans) {
ans = hash.get(t);
}
}
return ans;
}
}2. 从相邻元素对还原数组
这题就是寻找数组的第一个元素，最末尾的元素。这两个数有个特点，就是出现的次数为奇数。
那接下来，问题是如何恢复 ？
感觉还是要模拟建图，反正珂朵莉MM是这么做的，总觉得写复杂了，菜菜T_T.
Java
class Solution {
static class Tx {
int v;
int idx;
public Tx(int v, int idx) {
this.v = v;
this.idx = idx;
}
}
public int[] restoreArray(int[][] adjacentPairs) {
// 找规律
TreeMap<Integer, Deque<Tx>> hash = new TreeMap<>();
for (int i = 0; i < adjacentPairs.length; i++) {
int[] e = adjacentPairs[i];
hash.computeIfAbsent(e[0], (x) -> new LinkedList<>()).add(new Tx(e[1], i));
hash.computeIfAbsent(e[1], (x) -> new LinkedList<>()).add(new Tx(e[0], i));
}
Integer first = null, last = null;
// 找到奇数出现
for (Map.Entry<Integer, Deque<Tx>> e: hash.entrySet()) {
if (e.getValue().size() % 2 == 1) {
if (first == null) first = e.getKey();
else if (last == null) last = e.getKey();
}
}
boolean[] used = new boolean[adjacentPairs.length];
// 这边有个复原的过程
int target = first;
List<Integer> result = new ArrayList<>();
while (result.size() < adjacentPairs.length) {
Deque<Tx> deq = hash.get(target);
while (!deq.isEmpty()) {
Tx cur = deq.pollFirst();
if (!used[cur.idx]) {
used[cur.idx] = true;
result.add(target);
target = cur.v;
break;
}
}
}
result.add(target);
return result.stream().mapToInt(Integer::valueOf).toArray();
}
}3. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？
题意真的有争议，或者是珂朵莉MM自我加戏了。
本意上，寻找最快/最慢吃完对应的上下界，如果在范围内，则一定是可解的。
有个预处理，就是前缀和加速。
这样的时间复杂度就是
Java
class Solution {
// *) 画风不对呀, 感觉
public boolean[] canEat(int[] candiesCount, int[][] queries) {
int n = candiesCount.length;
// 求两个最值
long[] presum = new long[n + 1];
for (int i = 0; i < candiesCount.length; i++) {
presum[i + 1] = presum[i] + candiesCount[i];
}
int m = queries.length;
boolean[] res = new boolean[m];
for (int i = 0; i < m; i++) {
int[] q = queries[i];
int t = q[0];
// 这是一个条件
if (presum[t + 1] < q[1] + 1) {
res[i] = false;
} else {
long last = (presum[t] + q[2] - 1) / q[2];
// 这里有个边界，需要注意
if (last > q[1] + 1 || last == q[1] + 1 && presum[t] % q[2] == 0) {
res[i] = false;
} else {
res[i] = true;
}
}
}
return res;
}
}4. 回文串分割 IV
先做一个预处理，就是计算子数组的回文串，需要.
结果做一个枚举，枚举第二回文子串的起点和终点，这样时间复杂度为。
就这么简单。
Java
class Solution {
// 预处理计算 计算子数组是否为回文串
boolean[][] prehandle(char[] buf) {
int n = buf.length;
boolean[][] opt = new boolean[n][n];
for (int w = 0; w < n; w++) {
for (int i = 0; i + w < n; i++) {
opt[i][i + w] = (buf[i] == buf[i + w]) && (w < 2 || opt[i + 1][i + w - 1]);
}
}
return opt;
}
public boolean checkPartitioning(String s) {
char[] buf = s.toCharArray();
int n = buf.length;
boolean[][] opt = prehandle(buf);
// 枚举第二个回文子串的起点和终点即可
for (int i = 1; i < n - 1; i++) {
if (!opt[0][i - 1]) continue;
for (int j = i; j < n - 1; j++) {
if (opt[i][j] && opt[j+1][n - 1]) return true;
}
}
return false;
}
}写在最后
评论 (0)
