1.解码异或后的数组
题目描述：已知数组encoded由数组arr得到，计算方式为encoded[i] = arr[i] ^ arr[i+1]。现给定encoded和arr的第一个元素，要求还原出arr。
思路：异或的计算性质：若a ^ b = c 则有a = b ^ c。因此，这个题由first和encoded做异或运算即可。
由于比较简单，代码略。
2.交换列表中的节点
题目描述：给定链表的头节点，要求交换链表的正数第k和节点和倒数第k个节点的值。题目会保证k有效。
思路：这个题的核心在于找到整数第k个节点和倒数第k个节点。正数第k个很简单，直接数就好了；而找倒数第k个的思路为：找到正数第k个后，继续往后走，同时另一个指针从头开始，当前者到链尾时，后者指向的即为倒数第k个节点。
也比较简单，代码略。
3.执行完交换操作后的最小汉明距离
题目描述：给定两个数组source和target，二者的汉明距离为对应位置值不相等的数量：sum([m == n for m, n in zip(source, target)] )。同时，给定允许的交换位置allowedSwaps，allowedSwaps[i] = [ai, bi]表示source数组中可以交换的下标位置。现可以以任意顺序、任意次数进行allowedSwaps中允许位置的交换，求能达到的最小汉明距离。
思路：就是交换使得两个数组对应位置的值尽可能多地相等。allowedSwaps中允许交换的下标可以进一步合并，类似于图中联通节点的合并。例如对于数组
[0,1,2,3,4]，允许交换的下标位置有[0,4]和[4,2]，表示0可以和4换，4可以和2换，那么0也可以和2换。那么首先可以找到数组中可以任意交换位置的下标组，利用并查集来做。之后，对于一组下标，由于其中数字的位置可以任意交换，因此统计比较两个数组中对应位置数字的大小和数量即可。由于题目说明了数字的范围，因此直接利用数组来做统计。
代码：
from collections import defaultdict
class Solution(object):
def minimumHammingDistance(self, source, target, allowedSwaps):
"""
:type source: List[int]
:type target: List[int]
:type allowedSwaps: List[List[int]]
:rtype: int
"""
res = 0
nums = [0] * ((10 ** 5) + 1)
d = defaultdict(set)
self.root = list(range(len(source)))
for p1, p2 in allowedSwaps:
#大小其实无所谓，这里只是想令小值做根
if p1 > p2:
t1, t2 = p2, p1
else:
t1, t2 = p1, p2
t1, t2 = self.find(t1), self.find(t2)
if t1 != t2:
self.root[max(t2, t1)] = min(t1, t2)
for i in range(len(source)):
d[self.find(i)].add(i)
# 已经把可以交换的放在了一起
for k, y in d.items():
s = set()
# nums[n]+1 表示source数组中n的数量加1，若target中也有该数字则减1。最后只统计正值或负值即可
for i in y:
nums[source[i]] += 1
nums[target[i]] -= 1
s.add(source[i])
s.add(target[i])
for n in s:
if nums[n] > 0:
res += nums[n]
if nums[n] != 0:
nums[n] = 0
return res
def find(self, i):
if i != self.root[i]:
self.root[i] = self.find(self.root[i])
return self.root[i]
4.完成所有工作的最短时间
题目描述：给定数组jobs表示每个工作的完成时间，以及整数k表示员工数量。现将工作分配给员工，每个工作只能安排给一位员工，要求合理安排工作使得所有工作完成花费的时间最少。题目给定的员工数量不大于工作数量。
思路：采用二分法来做：若员工数量等于工作数量，且每位员工都有工作安排，则所求为max(jobs)；若将所有工作都安排给一个人，则所求为sum(jobs)。因此所求值的范围在二者之间。
代码：
class Solution:
def minimumTimeRequired(self, jobs, k):
n = len(jobs)
jobs.sort(reverse=True)
def dfs(i):
if i == n:
return True
for j in range(k):
# 若第j位员工的预期工作时间大于第i项工作的话费时间，则将该工作分配给该员工
if cap[j] >= jobs[i]:
cap[j] -= jobs[i]
if dfs(i + 1):
return True
cap[j] += jobs[i]
# 程序运行至此说明没有执行上边的返回True，说明为该员工分配工作是不能得到结果的，这对于后面的员工也是适用的，因此可以直接退出循环
if cap[j] == x:
break
return False
left, right = max(jobs), sum(jobs)
while left < right:
x = (left + right) // 2
cap = [x] * k # 每位员工的预期工作时间
if dfs(0):
right = x
else:
left = x + 1
return left