LeetCode第223场周赛
注：题目来源LeetCode
1720. 解码异或后的数组
未知 整数数组 arr 由 n 个非负整数组成。
经编码后变为长度为 n - 1 的另一个整数数组 encoded ，其中 encoded[i] = arr[i] XOR arr[i + 1] 。例如，arr = [1,0,2,1] 经编码后得到 encoded = [1,2,3] 。
给你编码后的数组 encoded 和原数组 arr 的第一个元素 first（arr[0]）。
请解码返回原数组 arr 。可以证明答案存在并且是唯一的。
示例 1：
输入：encoded = [1,2,3], first = 1
输出：[1,0,2,1]
解释：若 arr = [1,0,2,1] ，那么 first = 1 且 encoded = [1 XOR 0, 0 XOR 2, 2 XOR 1] = [1,2,3]
示例 2：
输入：encoded = [6,2,7,3], first = 4
输出：[4,2,0,7,4]
思路：只要利用异或运算的性质，如果有a ^ b = c，则有b = c ^ a，a = c ^ b，时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( 1 ) O(1)O(1)
class Solution {
public:
vector<int> decode(vector<int>& encoded, int first) {
vector<int> res;
res.push_back(first);
int pre = first;
for (int i = 0; i < encoded.size(); i++) {
res.push_back(encoded[i] ^ first);
first = res[res.size() - 1];
}
return res;
}
};
1721. 交换链表中的节点
给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
示例 1：
输入：head = [1,2,3,4,5], k = 2
输出：[1,4,3,2,5]
示例 2：
输入：head = [7,9,6,6,7,8,3,0,9,5], k = 5
输出：[7,9,6,6,8,7,3,0,9,5]
示例 3：
输入：head = [1], k = 1
输出：[1]
示例 4：
输入：head = [1,2], k = 1
输出：[2,1]
示例 5：
输入：head = [1,2,3], k = 2
输出：[1,2,3]
思路：
方法一：直接遍历一遍链表，并且把对链表的遍历结果存储到哈希表中，然后直接交换整数第k个元素和倒数第k个元素的值。时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( n ) O(n)O(n)
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
vector<ListNode*> vec;
while (head) {
vec.push_back(head);
head = head->next;
}
int n = vec.size();
swap(vec[k - 1]->val, vec[n - k]->val);//交换正数第k个元素和倒数第k个元素
return vec[0];
}
};
方法二：利用快慢指针，首先，使用一个指针firstK从链表头移动k-1步指向第k个元素，然后快指针从firstK出发，慢指针从头出发，当快指针到达链表末尾时，慢指针指向倒数第k个元素。然后交换正数第k个元素和倒数第k个元素的值。时间复杂度O ( n ) O(n)O(n)，空间复杂度O ( 1 ) O(1)O(1)
class Solution {
public:
ListNode* swapNodes(ListNode* head, int k) {
auto firstK = head;
int cnt = k - 1;
while (cnt--) {//定位第k个元素
firstK = firstK->next;
}
auto fast = firstK, slow = head;//快指针从firstK出发，慢指针从头出发
while (fast->next) {//当快指针到达链表末尾时，慢指针指向倒数第k个元素
fast = fast->next;
slow = slow->next;
}
swap(firstK->val, slow->val);//交换正数第k个元素和倒数第k个元素
return head;
}
};
1722. 执行交换操作后的最小汉明距离
给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。
相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。
在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。
示例 1：
输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：
- 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
- 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。
示例 2：
输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。
示例 3：
输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0
思路：这题的关键是要得出这样一个性质，如果allowedSwaps中有[a, b]，[b, c]，那么source中通过任意次数交换后，可以得到元素source[a]，source[b]， source[c]的任意排列，也可以从图论的角度理解这个性质，allowedSwaps中有[a, b]，[b, c]，则在图中有a到b、b到c的无向边，下标a、b、c构成一个联通分量，通过交换任意次的性质可以得到该联通分量内任意元素的排列。
这个性质不只是适用于只有2对交换关系。更一般地，可以得出，假设有一个下标集合S，source中下标在S集合中的元素可以交换任意次，那么可以得到source中这n个元素的任意排列，可以使用并查集维护这样可以任意交换元素的集合。因为我们要计算最小的汉明距离，则我们就将source中这n个元素的顺序，转化为与target中这n个下标对应的元素的顺序相同。设source中下标集合S的所有元素构成集合S1，target中下标集合S的所有元素构成集合S2，如果S1中有一个元素在S2中没有对应元素，那么汉明距离增加1。
时间复杂度O ( n l o g n ) O(nlogn)O(nlogn)，空间复杂度O ( n ) O(n)O(n)
const int N = 1e5 + 10;
class Solution {
public:
int p[N];
int find(int x) {
if (x == p[x]) return x;
return p[x] = find(p[x]);
}
int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& swaps) {
int n = source.size();
for (int i = 1; i <= n; i++)
p[i] = i;
for (auto &s: swaps) {//加入并查集
int a = s[0], b = s[1];
if (find(a) != find(b))
p[find(a)] = find(b);
}
unordered_map<int, vector<int>> g;
int res = 0;
for (int i = 0; i < n; i++) {//从并查集中提取出相同集合内的下标
g[find(i)].push_back(i);
}
for (auto &[k, v]: g) {
vector<int> a, b, c;
for (int i = 0; i < v.size(); i++) {
a.push_back(source[v[i]]);
b.push_back(target[v[i]]);
}
//计算source和target在对应下标集合不同元素的个数
sort(a.begin(), a.end());
sort(b.begin(), b.end());
auto i = a.begin(), j = b.begin();
//双指针找交集
int cnt = 0;
while (i < a.end() && j < b.end()) {
if (*i == *j) {
i++;
j++;
cnt++;
} else if (*i > *j) j++;
else if (*i < *j) i++;
}
// std::set_intersection(a.begin(), a.end(), b.begin(), b.end(), std::back_inserter(c));
res += v.size() - cnt;
}
return res;
}
};
1723. 完成所有工作的最短时间
给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。
请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能 最小 的 最大工作时间 。
示例 1：
输入：jobs = [3,2,3], k = 3
输出：3
解释：给每位工人分配一项工作，最大工作时间是 3 。
示例 2：
输入：jobs = [1,2,4,7,8], k = 2
输出：11
解释：按下述方式分配工作：
1 号工人：1、2、8（工作时间 = 1 + 2 + 8 = 11）
2 号工人：4、7（工作时间 = 4 + 7 = 11）
最大工作时间是 11 。
提示：
1 <= k <= jobs.length <= 12
1 <= jobs[i] <= 1 0 7 10^7107
思路：根据数据范围可以有效的算法时间复杂度可能是指数级别，故有效算法可能是搜索或者状态压缩DP。
方法一：状态压缩DP
下面考虑如果使用状态压缩DP来该问题。因为最终求解的是工人的工作时间，即完成分配给他们的所有工作花费时间的总和，首先预处理出该值。假设一共有n个作业（n ≤ 12 n \leq 12n≤12），那么一个工人被分配到的所有可能的作业最多有2 n 2^n2n种情况（n的所有子集），可以使用一个整数 i 上的低 n 位表示被分配到的作业情况，如果整数i的第 j 位为1，表示被分配到第jobs[j]个工作，有了这样的状态表示，可以枚举 i ，即 jobs 的所有可能分配方案，对于每个 i ，枚举 i 的每一位，如果 i 的第 j 位为1，去掉第 j 位的任务集合为left，可以使用递推式sum[i] = sum[left] + jobs[j]，计算出当前完成所有当前工作集合所需的工作时间。
下面考虑如何定义动态规划的状态以及转移。动态规划的状态可以根据题意定义，题目怎样设问就怎样定义，故设f[i][j]表示前 i (0 ≤ i < k 0\leq i<k0≤i<k)个人完成工作 j (0 ≤ j < 2 n 0 \leq j < 2^n0≤j<2n)的 最小 的 最大工作时间 ，这里工作 j 是一个二进制的状态表示，j中为1的为表示当前的工作集合，故最终答案即为f[k - 1][(1 << n)- 1]。
状态的转移需要枚举j的所有子集s，考虑计算f[i][j]，可以将前i - 1个人完成任务j - s，第i个人完成任务s，记录每个人的最大工作时间，然后f[i][j]等于所有方案中去最小的最大工作时间。
时间复杂度O ( k ∗ 3 n ) O(k*3^n)O(k∗3n)，空间复杂度O ( k ∗ 2 n ) O(k*2^n)O(k∗2n)，n为jobs的长度，k为工人人数。
class Solution {
public:
int minimumTimeRequired(vector<int>& jobs, int k) {
int n = jobs.size();
vector<int> sum(1 << n, 0);//sum[i]表示完成工作集合i所需的工作时间
for (int i = 1; i < (1 << n); i++) {//预处理
for (int j = 0; j < n; j++) {
if (i & (1 << j)) {
int left = i - (1 << j);
sum[i] = sum[left] + jobs[j];
break;//sum[i]不需要重复计算
}
}
}
vector<vector<int>> f(k, vector<int>(1 << n, -1));//f[i][j]前i个人完成工作集合j的最小的最大工作时间
for (int i = 0; i < (1 << n); i++) f[0][i] = sum[i];//一个人完成所有任务所需的时间
for (int i = 1; i < k; i++) {
for (int j = 0; j < (1 << n); j++) {
int minTime = INT_MAX;
for (int s = j; s; s = (s - 1) & j) {
int left = j - s;
int curTime = max(f[i - 1][left], sum[s]);//前i - 1个人完成任务left，第i个人完成任务s
minTime = min(minTime, curTime);
}
f[i][j] = minTime;
}
}
return f[k - 1][(1 << n) - 1];
}
};
方法二：DFS，注意剪枝。
class Solution {
public:
int res = INT_MAX;
int minimumTimeRequired(vector<int>& jobs, int k) {
vector<int> sum(k, 0);
dfs(jobs, k, sum, 0);
return res;
}
void dfs(vector<int> &jobs, int k, vector<int> &sum, int x) {//将jobs的前x个工作分配给k个人，sum[i]表示第i个人的工作时间
if (x == jobs.size()) {
res = min(res, *max_element(sum.begin(), sum.end()));
return;
}
for (int i = 0; i < k; i++) {
if (sum[i] + jobs[x] >= res) continue;//剪枝
sum[i] += jobs[x];
dfs(jobs, k, sum, x + 1);
sum[i] -= jobs[x];
if (sum[i] == 0) break;//剪枝
}
}
};