LeetCode 第 223 场周赛
source link: https://xienaoban.github.io/posts/45902.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
LeetCode 第 223 场周赛
发表于
2021-01-10
阅读次数：
评论次数：
本文字数：
2.8k
阅读时长 ≈
3 分钟
5649. 解码异或后的数组
异或运算可逆, 所以直接异或回去.
class Solution {
public int[] decode(int[] encoded, int first) {
int[] res = new int[encoded.length + 1];
res[0] = first;
for (int i = 0; i < encoded.length; ++i) {
res[i + 1] = res[i] ^ encoded[i];
}
return res;
}
}
5652. 交换链表中的节点
双指针, 前者距离后者 k 格.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode swapNodes(ListNode head, int k) {
ListNode n2 = head;
for (int i = 1; i < k; ++i) n2 = n2.next;
ListNode swap1 = n2;
ListNode n1 = head;
while (n2.next != null) {
n2 = n2.next;
n1 = n1.next;
}
ListNode swap2 = n1;
int t = swap1.val;
swap1.val = swap2.val;
swap2.val = t;
return head;
}
}
5650. 执行交换操作后的最小汉明距离
可以任意交换, 也就是只要两个节点直接或间接有边, 就能交换.
并查集找出所有连通图, 连通图里的节点可以任意交换. 把连通图里所有节点打入一个集合, target 要啥我就从集合里拿啥, 不在集合里就 res - 1.
class Solution {
public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) {
int n = source.length;
HashMap[] a = new HashMap[n];
int[] f = new int[n];
for (int i = 0; i < n; ++i) f[i] = i;
for (int[] e : allowedSwaps) merge(f, e[0], e[1]);
for (int i = 0; i < n; ++i) find(f, i);
for (int i = 0; i < n; ++i) {
if (a[f[i]] == null) a[f[i]] = new HashMap();
if (f[i] != i) a[i] = a[f[i]];
int cnt = (int) a[i].getOrDefault(source[i], 0);
a[i].put(source[i], cnt + 1);
}
int res = n;
for (int i = 0; i < n; ++i) {
int cnt = (int) a[i].getOrDefault(target[i], 0);
if (cnt == 0) continue;
--res;
a[i].put(target[i],cnt - 1);
}
return res;
}
private int find(int[] f, int x) {
if(f[x] == x) return x;
return f[x] = find(f, f[x]);
}
private void merge(int[] f, int i, int j) {
int x = find(f, i), y = find(f, j);
if (x < y) {
int t = x;
x = y;
y = t;
}
f[x] = y;
}
}
5639. 完成所有工作的最短时间
比赛时没做出来, 赛后倒是想出来了一个方法, 虽然还是很暴力... 但至少过了.
用回溯法枚举所有任务分配给任意用户的情况.
然后发现很多回溯是重复的. 比如说如下两种分配, 其实是一种 (这里 arr[i] 表示任务 i 分配给打工人 arr[i]):
[1, 1, 1, 2, 2, 3]
[2, 2, 2, 3, 3, 1]
最简单的, 我们发现开局分配第一个工作时, 分配给谁都是一样的, 每种情况回溯下来都是重复的, 那我们不如让第一个工作只分配给第一个人. 同样, 第二个工作要么继续分配给第一个人, 要么分配给一个没工作的人, 而所有没工作的人情况都是重复的, 于是不如就指定分给第二个人.
也就是给定 n 个 job 和 k 个人. 在已经分配了 x 个 job 给前 y 个人的情况下, 第 x + 1 个 job 要么继续分配给前 y 个人的其中之一, 要么分配给一个任意的没工作的人. 于是本来这个 job 要回溯所有 k 个人, 现在剪成只要回溯 min(k, x + 1).
class Solution {
private int[] job;
private int[] man;
private int res;
public int minimumTimeRequired(int[] jobs, int k) {
if (jobs.length <= k) {
int x = 0;
for (int v : jobs) x = Math.max(x, v);
return x;
}
job = jobs;
man = new int[k];
res = 0x7fffffff;
f(0, 0, 0);
return res;
}
private void f(int i, int max, int used) {
if (i == job.length) {
res = Math.min(res, max);
return;
}
int type = Math.min(man.length, used + 1);
for (int j = 0; j < type; ++ j) {
man[j] += job[i];
f(i + 1, Math.max(max, man[j]), Math.max(used, j + 1));
man[j] -= job[i];
}
}
}
执行用时：345 ms, 内存消耗：35.9 MB
这方法不好, 看大佬的方法是二分 + 状态压缩DP 可以只用几毫秒.
- 本文作者： XieNaoban
- 本文链接： https://xienaoban.github.io/posts/45902.html
- 版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-ND 许可协议。转载请注明出处！
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK