上岸算法LeetCode Weekly Contest 267解题报告

买票需要的时间

签到题,使用一个 LinkedList 模拟即可。

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i : tickets) {
            queue.add(i);
        }
        int result = 0;
        while (!queue.isEmpty()) {
            result++;
            int t = queue.pollFirst() - 1;
            if (t == 0 && k == 0) {
                break;
            }
            if (t > 0) {
                queue.addLast(t);
            }
            k = (k - 1 + queue.size()) % queue.size();
        }
        return result;
    }
}

反转偶数长度组的节点

数组更有利于反转操作,可以先将链表转换成数组,操作完后再转换成链表。

class Solution {
    public ListNode reverseEvenLengthGroups(ListNode head) {
        List<Integer> list = new ArrayList<>();
        for (ListNode i = head; i != null; i = i.next) {
            list.add(i.val);
        }
        for (int start = 1, len = 2; start < list.size(); ) {
            int end = Math.min(list.size(), start + len);
            if ((end - start) % 2 == 0) {
                // reverse [start, end)
                for (int l = start, r = end - 1; l < r; ) {
                    int t = list.get(l);
                    list.set(l, list.get(r));
                    list.set(r, t);
                    l++;
                    r--;
                }
            }
            start += len;
            len++;
        }
        ListNode h = new ListNode(list.get(0));
        ListNode cur = h;
        for (int i = 1; i < list.size(); i++) {
            cur.next = new ListNode(list.get(i));
            cur = cur.next;
        }
        return h;
    }
}

解码斜向换位密码

还原出矩阵即可,最后注意将后缀空格删去。

class Solution {
    public String decodeCiphertext(String encodedText, int rows) {
        int cols = encodedText.length() / rows;
        char[][] mtx = new char[rows][cols];
        for (int i = 0; i < encodedText.length(); i++) {
            int x = i / cols;
            int y = i % cols;
            mtx[x][y] = encodedText.charAt(i);
        }
        StringBuilder sb = new StringBuilder();
        for (int startY = 0; startY < cols; startY++) {
            for (int x = 0, y = startY; x < rows && y < cols; x++, y++) {
                sb.append(mtx[x][y]);
            }
        }
        while (sb.length() > 0 && sb.charAt(sb.length() - 1) == ' ') {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }
}

处理含限制条件的好友请求

并查集,详见代码注释。

class Solution {
    public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
        boolean[] result = new boolean[requests.length];
        // R[i] 表示不能与 i 做朋友的人
        List<Set<Integer>> R = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            R.add(new HashSet<>());
        }
        for (var r : restrictions) {
            R.get(r[0]).add(r[1]);
            R.get(r[1]).add(r[0]);
        }
        // uf 维护间接朋友关系
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < requests.length; i++) {
            var r = requests[i];
            int f0 = uf.find(r[0]);
            int f1 = uf.find(r[1]);
            if (f0 == f1) { // 说明 r[0] 和 r[1] 已经是直接或间接朋友了
                result[i] = true;
                continue;
            }
            // 由于我们总是将限制关系合并到根,所以只需判断根节点即可
            result[i] = !R.get(f0).contains(f1) && !R.get(f1).contains(f0);
            if (result[i]) {
                uf.merge(f0, f1); // merge 后 f1 将成为 根
                // 原本不能与 f0 做朋友的人也不能与 f1 做朋友了
                R.get(f1).addAll(R.get(f0));
                for (int j : R.get(f1)) {
                    R.get(j).add(f1);
                }
            }
        }
        return result;
    }
}

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

    public Map<Integer, List<Integer>> sets() {
        Map<Integer, List<Integer>> res = new HashMap<>();
        for (int i = 0; i < f.length; i++) {
            int fi = find(i);
            if (!res.containsKey(fi)) {
                res.put(fi, new ArrayList<>());
            }
            res.get(fi).add(i);
        }
        return res;
    }

    private int[] f;
}