前言
「……我真的不需要。拜讬妳们别闹了。 我好不容易在各方面都死心了，才不想留下眷恋。」 珂朵莉静静说道。
「这样啊。」 艾瑟雅落寞地笑了笑，没多说什么就望向窗外了。
「……嗯。」 奈芙莲微微点头，然后同样什么也没说就翻开了手上的书。
整体评价
这场质量蛮高的，每一题都不容易解，t2是hash计数+滑窗，t3是dp+单调队列优化，t4是离线算法+并查集。强推推荐VP.
VP入口：第 220 场周赛
更多解题报告详见： 珂朵莉MM的解题报告汇总
T1. 重新格式化电话号码
t1一般考察字符串处理，主要是API调用。
思路的话，还是分类讨论， 主要是谈论分歧点，在于末尾的处理
Java
class Solution {
public String reformatNumber(String number) {
char[] buf = number.replaceAll("\\-", "").replaceAll("\\s+", "").toCharArray();
StringBuilder sb = new StringBuilder();
int i = 0;
while ((buf.length - i) >= 5) {
sb.append(new String(buf, i, 3)).append("-");
i += 3;
}
if (buf.length - i == 4) {
sb.append(new String(buf, i, 2)).append("-").append(new String(buf, i + 2, 2));
} else if (buf.length - i <= 3) {
sb.append(new String(buf, i, buf.length - i));
}
return sb.toString();
}
}T2. 删除子数组的最大得分
经典滑窗+Hash计数题, 这边hash只是记录字母对应最后一个出现位置, 用于快速判定滑窗区间满足条件。
喜欢滑动的同学，不容错过.
Java
class Solution {
// *) 滑窗的应用
public int maximumUniqueSubarray(int[] nums) {
Map<Integer, Integer> hash = new HashMap<>();
int n = nums.length;
int j = 0;
long tsum = 0, ans = 0;
for (int i = 0; i < n; i++) {
tsum += nums[i];
int idx = hash.getOrDefault(nums[i], -1);
while (j <= idx) {
tsum -= nums[j];
j++;
}
ans = Math.max(ans, tsum);
hash.put(nums[i], i);
}
return (int)ans;
}
}T3. 跳跃游戏 VI
一眼就是DP题
时间复杂度为
不过这个k,n的范围为, 因此这里面必须进行优化。
那一般这类DP怎么优化呢？ 可以往单调队列，斜率优化等等上面去碰瓷。刚好这边固定窗口大小的单调队列（单调递减），可以满足需求。
Java
class Solution {
// *) 有意思的题
public int maxResult(int[] nums, int k) {
// 基于单调队列的DP优化
int n = nums.length;
long[] opt = new long[n];
Deque<Integer> deq = new LinkedList<>();
opt[0] = nums[0];
deq.addLast(0);
for (int i = 1; i < n; i++) {
// 固定窗口限制
while (!deq.isEmpty() && deq.peekFirst() + k < i) {
deq.pollFirst();
}
// 单调递减，所以队首是最大的值
long tv = opt[deq.peekFirst()];
opt[i] = tv + nums[i];
// 添加元素，并维护单调性
while (!deq.isEmpty() && opt[deq.peekLast()] <= opt[i]) {
deq.pollLast();
}
deq.addLast(i);
}
return (int)opt[n - 1];
}
}由于区间最值维护问题， 实际上引入RMQ的数据结构，其实是最方便的。
比如线段树，树状数组等等。
T4. 检查边长度限制的路径是否存在
这题也很经典，权重限制到连通性，可以引入并查集的思想。
而对于查询的不确定性，可以离线做法，并按顺序处理增量处理，避免重复的计算。
关于类似的题，312场周赛T4 好路径的数目可供参考。
Java
class Solution {
int findSet(int[] bset, int a) {
if (bset[a] == -1) return a;
return bset[a] = findSet(bset, bset[a]);
}
void unionSet(int[] bset, int a, int b) {
int ai = findSet(bset, a);
int bi = findSet(bset, b);
if (ai != bi) {
bset[ai] = bi;
}
}
// 离线算法 + 并查集
public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
int m = queries.length;
Integer[] arr = IntStream.range(0, m).boxed().toArray(Integer[]::new);
Arrays.sort(arr, Comparator.comparing(x -> queries[x][2]));
// 并查集
int[] bset = new int[n];
Arrays.fill(bset, -1);
// 优先队列/数组排序，都可以
PriorityQueue<int[]> pp = new PriorityQueue<>(Comparator.comparing(x -> x[2]));
for (int[] e: edgeList) {
pp.offer(e);
}
boolean[] res = new boolean[m];
for (int i = 0; i < m; i++) {
int qx = arr[i];
int[] qs = queries[qx];
while (!pp.isEmpty() && pp.peek()[2] < qs[2]) {
int[] e = pp.poll();
unionSet(bset, e[0], e[1]);
}
if (findSet(bset, qs[0]) == findSet(bset, qs[1])) {
res[qx] = true;
}
}
return res;
}
}写在最后
评论 (0)
