来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/decode-xored-array
第一题：解码异或后的数组（3分）
未知 整数数组 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]
思路：任何一个数连续两次与另一个数异或（XOR）能得到本身，这个性质我也是在解题时推出来的。因为题目已经异或过一次了，所以我们在执行一次异或操作即可得到答案。
1 class Solution: 2 def decode(self, encoded: List[int], first: int) -> List[int]: 3 a =[] 4 a.append(first) 5 for i in range(len(encoded)): 6 c = encoded[i]^a[i] 7 a.append(c) 8 return a
第二题：交换链表中的节点（4分）
给你链表的头节点 head 和一个整数 k 。
交换 链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。
输入：head = [1,2,3,4,5], k = 2 输出：[1,4,3,2,5]
思路：正数第k个，倒数第k个交换，倒数第k个也就是正数第len(链表)-k+1个交换。
这道题我参考之前做过树的处理，使用queue=[]，queue.append(head)想着这样处理这个链表，写了这样的伪代码：
1 tmp = head[k-1].next.next 2 head[k-1].next = head[len(head)-k+1] 3 head[len(head)-k+1-1].next = head[k] 4 head[k].next = head[len(head)-k+1].next 5 head[len(head)-k+1].next = tmp
此思路的正确代码：
1 class Solution: 2 3 def swapNodes(self, head: ListNode, k: int) -> ListNode: 4 5 p, n, former, latter = head, 0, head, head 6 7 while p != None: # get the number of the nodes of list: n 8 n += 1 9 p = p.next 10 11 for _ in range(1, k): # find the former node 12 former = former.next 13 14 for _ in range(1, n - k + 1): # find the latter node 15 latter = latter.next 16 17 former.val, latter.val = latter.val, former.val 18 19 return head 20 21 作者：whybfq 22 链接：https://leetcode-cn.com/problems/swapping-nodes-in-a-linked-list/solution/python3-by-whybfq-932z/ 23 来源：力扣（LeetCode）
第三题：执行交换操作后的最小汉明距离（5分）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations
给你两个整数数组 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 。
本题我在题意上没理解清楚，以为交换过一次就OK，忽略了allowedSwaps中交换元素的下标可以任意、多次的重复使用，我们返回的是情况当中汉明距离最小的值。
我的代码只是按顺序执行交换操作，遍历了allowedSwaps中所有成对下标一次：
1 class Solution: 2 def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int: 3 cnt = 0 4 for i in range(len(allowedSwaps)): 5 a = allowedSwaps[i][0] 6 b = allowedSwaps[i][1] 7 tmp = source[a] 8 source[a] = source[b] 9 source[b] = tmp 10 for i in range(len(target)): 11 if source[i] != target[i]: 12 cnt +=1 13 return cnt
附上其他人解题思路：
参数定义
parent：并查集数组，每个节点指向根节点
dic：哈希表，k,v分别为并查集中每个簇的根节点和簇中所有元素的索引
res：返回值
思路
示例：如果allowedSwaps为[[0,1],[1,2]]，说明索引0/1和1/2处的元素可以交换，根据连通性，0/2处的元素同样可以交换，此时0/1/2构成的连通块之间相互可以交换，所以可以利用并查集计算出每一个连通块。
首先确定每个元素对应的根节点，利用哈希表dic存储根节点对应的所有元素的索引。
遍历dic，k,v分别为根节点和簇元素索引集合，找到索引集合v在source和target中对应的元素a,b，利用a在b中查找差集，所以b可以为哈希表，记录了每个元素的个数，便于O(1)时间复杂度查找。如果在b中没有找到a中的元素，res+=1。求两个数组的交集也可以用哈希表的&运算，见代码二。
复杂度分析
时间复杂度：O(N+M)，N为source和target的长度，M为allowedSwaps长度，路径压缩时间α(N)很小可忽略
空间复杂度：O(N)
作者：yim-6
链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/solution/python3-bing-cha-ji-ha-xi-biao-by-yim-6-4a03/
1 class Solution: 2 def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int: 3 n=len(source) 4 parent={i:i for i in range(n)} 5 # 并查集 6 def find(x): 7 if x!=parent[x]: 8 parent[x]=find(parent[x]) 9 return parent[x] 10 # 搜索根节点 11 for l,r in allowedSwaps: 12 a,b=find(l),find(r) 13 if a!=b: 14 parent[b]=a 15 # 获取根节点对应的连通块 16 dic=collections.defaultdict(list) 17 for i in range(n): 18 a=find(i) 19 dic[a].append(i) 20 res=0 21 # 计算每个连通块对应的source元素与target的差集 22 for k,v in dic.items(): 23 a=[source[i] for i in v] 24 b=Counter([target[i] for i in v]) 25 for c in a: 26 if b[c]>0: 27 b[c]-=1 28 else: 29 res+=1 30 return res 31 32 作者：yim-6 33 链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/solution/python3-bing-cha-ji-ha-xi-biao-by-yim-6-4a03/ 34 来源：力扣（LeetCode）
输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
parent ={0:0,1:1,2:2,3:3}
1)a,b = find(0),find(1) = 0,1 因为a!=b 所以parent[1] = 0 parent: {0: 0, 1: 0, 2: 2, 3: 3}
2)a,b = find(2),find(3) = 2,3 因为a!=b 所以parent[3] = 2 parent: {0: 0, 1: 0, 2: 2, 3: 2}
进入for循环i取值0~3，0的根节点是0加入... dic = defaultdict(<class 'list'>, {0: [0, 1], 2: [2, 3]})
代码二：
1 class Solution: 2 def minimumHammingDistance(self, source: List[int], target: List[int], allowedSwaps: List[List[int]]) -> int: 3 n=len(source) 4 parent={i:i for i in range(n)} 5 # 并查集 6 def find(x): 7 if x!=parent[x]: 8 parent[x]=find(parent[x]) 9 return parent[x] 10 # 搜索根节点 11 for l,r in allowedSwaps: 12 a,b=find(l),find(r) 13 if a!=b: 14 parent[b]=a 15 # 获取根节点对应的连通块 16 dic=collections.defaultdict(list) 17 for i in range(n): 18 a=find(i) 19 dic[a].append(i) 20 # 计算每个连通块对应的source元素与target的差集 21 count=0 22 for k,v in dic.items(): 23 a=Counter([source[i] for i in v]) 24 b=Counter([target[i] for i in v]) 25 count+=len(list((a&b).elements())) 26 return n-count 27 28 作者：yim-6 29 链接：https://leetcode-cn.com/problems/minimize-hamming-distance-after-swap-operations/solution/python3-bing-cha-ji-ha-xi-biao-by-yim-6-4a03/ 30 来源：力扣（LeetCode）
题目四：完成工作的最短时间（6分）
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs
给你一个整数数组 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 。
作者：xiao-man-tou-2s
链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/python-jian-zhi-sou-suo-by-xiao-man-tou-14kjt/
基本算法：DFS。 裸 DFS 会超时，所以需要剪枝：
1.第 j 个工作只能分配给前 j 个工人。
原理：工作 123 分别分配给工人 abc 或者分配给 acb ，这两种方案最后结果是一致的，只是交换了 b 和 c 的工作。所以令第 j 个工作只能分配给前 j 个工 人，避免出现 acb 的分配情况。
2.贪心求一个次优解，作为 DFS 算法的初始边界
当搜索过程中，某工人工作量大于已知最优解时，剪枝
1 class Solution: 2 def minimumTimeRequired(self, jobs: List[int], k: int) -> int: 3 #贪心求一个次优解 4 from heapq import heapify,heappush,heappop 5 heap = [0]*k 6 heapify(heap) 7 jobs = sorted(jobs)[::-1] 8 for i in jobs: 9 heappush(heap, heappop(heap)+i) 10 m = max(heap) 11 12 a = [0]*k # k 个工人，每个工人的工作量，初始为 0 13 def job(j): 14 nonlocal m 15 if j == len(jobs): 16 m = min(m,max(a)) #记录已知最优解 17 return 18 for i in range(min(k,j+1)): #剪枝，第 j 个工作只能分配给前 j 个工人 19 if a[i]+jobs[j]>m: #如果工作 j 分配给工人 i 后，工人 i 工作量大于已知最优解 m ，跳过 20 continue 21 a[i] += jobs[j] 22 job(j+1) 23 a[i] -= jobs[j] 24 job(0) 25 return m 26 27 作者：xiao-man-tou-2s 28 链接：https://leetcode-cn.com/problems/find-minimum-time-to-finish-all-jobs/solution/python-jian-zhi-sou-suo-by-xiao-man-tou-14kjt/ 29 来源：力扣（LeetCode）
PS：有的做法中，将 jobs 大到小排序，将前 k 个工作分配个每个工人作为初始化，然后直接从第 k+1 个工作开始搜索（不做第 1 种剪枝），虽然也能过，但是这么做是不对的。例如：[8,7,5,5,5] k=2。只能说测试数据集有点水。