前言
哎，算了。
反正也没有什么好隐瞒，我告诉你。
你刚才的第二个问题，就是第一个问题的答案。
第一个问题则是第二个问题的答案。
整体评价
t3是道有趣的题，想到并查集容易，但是处理最后的结果稍显麻烦。t4是道经典的题，算求配对最优的dfs技巧把。
推荐VP， 大赛链接入口： 第 223 场周赛
更多解题报告详见： 珂朵莉MM的解题报告汇总
T1. 解码异或后的数组
经典异或位运算技巧，偶数次为0，奇数次为本身
Java
class Solution {
public int[] decode(int[] encoded, int first) {
int n = encoded.length;
int[] res = new int[n + 1];
res[0] = first;
for (int i = 1; i <= n; i++) {
res[i] = res[i - 1] ^ encoded[i - 1];
}
return res;
}
}T2. 交换链表中的节点
怎么方便怎么来吧， ^_^.
如果是面试题，则会统计链的长度，在反推倒数第k个节点。
单向链表的话，大概需要2次遍历。
Java
class Solution {
public ListNode swapNodes(ListNode head, int k) {
List<ListNode> arr = new ArrayList<>();
ListNode cur = head;
while (cur != null) {
arr.add(cur);
cur = cur.next;
}
int fk = k - 1;
int lk = arr.size() - k;
if (fk == lk) return head;
int t = arr.get(fk).val;
arr.get(fk).val = arr.get(lk).val;
arr.get(lk).val = t;
return head;
}
}T3. 执行交换操作后的最小汉明距离
并查集好想，而且同一组内，元素可以迅速完成交换。
就是分好组后， 对比source和target归属的列表差异。
这个问题，就变成另一个经典问题，就是排好序的两个链表，求并/交/差集？
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 int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
int[] bset = new int[n];
Arrays.fill(bset, -1);
for (int[] r: allowedSwaps) {
unionSet(bset, r[0], r[1]);
}
Integer[] arr = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(arr, (a, b) -> {
int ai = findSet(bset, a);
int bi = findSet(bset, b);
if (ai != bi) return ai < bi ? -1 : 1;
return Integer.compare(source[a], source[b]);
});
Integer[] brr = IntStream.range(0, n).boxed().toArray(Integer[]::new);
Arrays.sort(brr, (a, b) -> {
int ai = findSet(bset, a);
int bi = findSet(bset, b);
if (ai != bi) return ai < bi ? -1 : 1;
return Integer.compare(target[a], target[b]);
});
int diff = 0;
for (int i = 0; i < n; ) {
// 1. 求同组的区间
int grp = findSet(bset, arr[i]);
int j = i + 1;
while (j < n && findSet(bset, arr[j]) == grp) {
j++;
}
// 2. 两个排序好的链表求差集
int k = i;
for (int s = i; k < j && s < j; ) {
if (source[arr[k]] == target[brr[s]]) {
k++; s++;
} else if (source[arr[k]] < target[brr[s]]) {
diff++;
k++;
} else {
s++;
}
}
if (k < j) {
diff += (j - k);
}
i = j;
}
return diff;
}
}感觉写复杂了， 不过确实，这个解法省空间吧。
T4. 完成所有工作的最短时间
这边用了二分， 因为求最大值的最小化的语义。不过事后发现，这题完全不用二分解法。
这边主要对 ，给出了一个DFS解，感觉lc蛮多这种类似的。
这边需要注意几个小技巧，可以避免大量的重复计算。
-
就是匹配拓展时，最多拓展一个空slot，而且必须邻近的。
-
最好对数据进行排序，大的放前面。
-
把第一个元素，固定分配给第一个slot.
这题也可以状压解，不过需要用到子集枚举技巧。
Java
class Solution {
int[] jobs;
int k;
boolean dfs(int[] workers, int idx, int limit) {
if (idx >= jobs.length) return true;
for (int i = 0; i < k; i++) {
if (workers[i] > 0 && workers[i] + jobs[idx] <= limit) {
workers[i] += jobs[idx];
if (dfs(workers, idx + 1, limit)) {
return true;
}
workers[i] -= jobs[idx];
}
if (workers[i] == 0) {
// 开辟新的
workers[i] = jobs[idx];
if (dfs(workers, idx + 1, limit)) {
return true;
}
workers[i] = 0;
break;
}
}
return false;
}
public int minimumTimeRequired(int[] jobs, int k) {
this.jobs = jobs;
this.k = k;
int r = Arrays.stream(jobs).sum();
int l = Arrays.stream(jobs).max().getAsInt();
Arrays.sort(jobs);
for (int i = 0, j = jobs.length - 1; i < j; i++, j--) {
int t = jobs[i];
jobs[i] = jobs[j];
jobs[j] = t;
}
int ans = 0;
while (l <= r) {
int m = l + (r - l) / 2;
int[] arr = new int[k];
arr[0] = jobs[0];
if (dfs(arr, 1, m)) {
ans = m;
r = m - 1;
} else {
l = m + 1;
}
}
return ans;
}
}写在最后
评论 (2)
