No.1 解码异或后的数组
解题思路
a ^ b = c 则有 a ^ b ^ a = c ^ a 即 b = a ^ c
代码展现
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] ^ res[i+1] = encoded[i] res[i + 1] = encoded[i] ^ res[i]; } return res; }}No.2替换链表中的节点
解题思路
比拟奢侈的实现，封装了一个函数，遍历三次链表。
代码展现
class Solution { public ListNode swapNodes(ListNode head, int k) { int n = 0; for (ListNode cur = head; cur != null; cur = cur.next) { n++; } ListNode a = getKthNode(head, k); ListNode b = getKthNode(head, n - k + 1); int tmp = a.val; a.val = b.val; b.val = tmp; return head; } ListNode getKthNode(ListNode head, int k) { ListNode cur = head; for (int i = 0; cur != null; i++, cur = cur.next) { if (i == k - 1) { return cur; } } return null; }}No.3执行替换操作后的最小汉明间隔
解题思路
应用并查集保护汇合 —— 一个地位的数字与其余哪些地位的数字可替换。
而后贪婪法计数即可。
代码展现
class UnionFind { public UnionFind(int size) { f = new int[size]; Arrays.fill(f, -1); } public int find(int x) { if (f[x] < 0) return x; return f[x] = find(f[x]); } public boolean merge(int a, int b) { int fa = find(a); int fb = find(b); if (fa == fb) return false; f[fa] = fb; return true; } private int[] f;}class Solution { public int minimumHammingDistance(int[] source, int[] target, int[][] allowedSwaps) { UnionFind uf = new UnionFind(source.length); for (int[] a : allowedSwaps) { uf.merge(a[0], a[1]); } // map[i] 是一个 counter // map[i][j] > 0 示意 source[i] 能够通过替换变成 j // 应用 map<int,map> 而不是 map<int,set> 的起因是防止 source 有反复数字 Map<Integer, Map<Integer, Integer>> map = new HashMap<>(); for (int i = 0; i < source.length; i++) { int fi = uf.find(i); if (!map.containsKey(fi)) { map.put(fi, new HashMap<>()); } Map<Integer, Integer> cnt = map.get(fi); cnt.put(source[i], cnt.getOrDefault(source[i], 0) + 1); map.put(i, cnt); } int res = target.length; for (int i = 0; i < target.length; i++) { Map<Integer, Integer> cnt = map.get(i); if (cnt.getOrDefault(target[i], 0) > 0) { res--; cnt.put(target[i], cnt.get(target[i]) - 1); } } return res; }}No.4实现所有工作的最短时间
解题思路
二分 + 枚举
代码展现
class Solution { public int minimumTimeRequired(int[] jobs, int k) { // 应用 long 以防止 (l + r) 溢出 long l = Arrays.stream(jobs).min().getAsInt(); long r = Arrays.stream(jobs).sum(); while (l + 1 < r) { long mid = (l + r) / 2; if (check(jobs, k, mid)) { r = mid; } else { l = mid; } } return (int) (check(jobs, k, l) ? l : r); } boolean check(int[] jobs, int k, long limit) { // 判断 k 个工人是否在 limit 的时限下实现工作 return dfs(jobs, 0, new int[k], limit); } // 枚举每个任务分配给哪个工人 // sum[i] 示意以后 i 工人失去的工作的总工时 boolean dfs(int[] jobs, int curJob, int[] sum, long limit) { if (curJob == jobs.length) { return true; } for (int i = 0; i < sum.length; i++) { if (sum[i] + jobs[curJob] <= limit) { sum[i] += jobs[curJob]; if (dfs(jobs, curJob + 1, sum, limit)) { return true; } sum[i] -= jobs[curJob]; // 一个很重要的优化 // sum[i] = 0 示意 curJob 被分给一个新的工人 // 如果未能在上方 return true, 换一个新工人也不可能达标 if (sum[i] == 0) { break; } } } return false; }}