关于facebook:上岸算法-I-LeetCode-Weekly-Contest-223解题报告

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;
    }
}