力扣第 267 场周赛

比赛时间 2021-11-14。纪念下第一次 AK。本场周赛国服共 402 人 AK。

T1. 买票需要的时间（3 分）

解题思路

模拟。

时间复杂度：O(nT)，其中 T = tickets[k]。

参考代码

class Solution {
    public int timeRequiredToBuy(int[] tickets, int k) {
        int len = tickets.length;
        int cnt = 0;
        while (tickets[k] > 0) {
            for (int i = 0; i < len; i++) {
                if (tickets[i] > 0) {
                    tickets[i]--;
                    cnt++;
                    // 退出循环
                    if (tickets[k] == 0) {
                        return cnt;
                    }
                }
            }
        }
        return cnt;
    }
}

T2. 反转偶数长度组的节点（4 分）

解题思路

模拟。翻转链表细节较多容易出错，比赛时可以先转化为数组，在数组的基础上进行模拟，再转换成链表返回。

时间复杂度：O(n)。

参考代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseEvenLengthGroups(ListNode head) {
        // ListNode => int[]
        int[] nums = toArray(head);

        int len = nums.length;
        // group 长度
        int groupLen = 1;
        // 下标
        int left = 0;
        int right = 0;
        while (left <= right) {
            groupLen++;
            left = right + 1;
            right = Math.min(len - 1, left + groupLen - 1);
            // 反转 每个 偶数 长度组中的节点
            if ((right - left + 1) % 2 == 0) {
                swap(nums, left, right);
            }
        }

        // int[] => ListNode
        return toListNode(nums);
    }

    private void swap(int[] arr, int left, int right) {
        int len = right - left + 1;
        for (int i = 0; i < len / 2; i++) {
            int tmp = arr[left + i];
            arr[left + i] = arr[left + len - i - 1];
            arr[left + len - i - 1] = tmp;
        }
    }

    private int[] toArray(ListNode head) {
        List<Integer> list = new ArrayList<>();
        while (head != null) {
            list.add(head.val);
            head = head.next;
        }
        int[] res = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }

    private ListNode toListNode(int[] nums) {
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        for (int num : nums) {
            head.next = new ListNode(num);
            head = head.next;
        }
        return dummy.next;
    }
}

T3. 解码斜向换位密码（5 分）

解题思路

矩阵模拟。注意 originalText 不含尾随空格，需特殊处理（可用 String#replaceAll("\\s+$", "") 去掉尾随空格，jdk11 可使用 String#stripTrailing()）。

时间复杂度：O(n)。

参考代码

class Solution {
    public String decodeCiphertext(String encodedText, int rows) {
        int len = encodedText.length();
        int cols = len / rows;
        char[][] chars = new char[rows][cols];
        int idx = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                chars[i][j] = encodedText.charAt(idx++);
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < cols; i++) {
            for (int j = 0; j < rows; j++) {
                if (j + i < cols) {
                    stringBuilder.append(chars[j][j + i]);
                }
            }
        }
        return stringBuilder.toString().replaceAll("\\s+$","");
    }
}

T4. 处理含限制条件的好友请求（6 分）

解题思路

并查集。对每一次询问，在 α(n) 时间复杂度内判断是否违反限制条件，如果违反限制条件，并查集需进行回退。

时间复杂度：O(Q*R*α(n))，其中 Q 为查询数，R 为限制数，α 表示阿克曼函数的反函数，在宇宙可观测的 n 内（例如宇宙中包含的粒子总数），α(n) 不会超过 5。

参考代码

class Solution {
    public boolean[] friendRequests(int n, int[][] restrictions, int[][] requests) {
        UnionFind unionFind = new UnionFind(n);
        int len = requests.length;
        boolean[] res = new boolean[len];
        Arrays.fill(res, true);

        for (int i = 0; i < len; i++) {
            // 先并
            unionFind.union(requests[i][0], requests[i][1]);
            for (int[] restriction : restrictions) {
                if (unionFind.connected(restriction[0], restriction[1])) {
                    res[i] = false;
                    // 不行就复原
                    unionFind.reset();
                    break;
                }
            }
        }
        return res;
    }

    private static class UnionFind {
        // 记录每个节点的父节点
        int[] parent;
        // 记录每棵树的重量
        int[] rank;
        // (可选) 连通分量
        int count;
        // 记录上一个状态
        int[] preParent;

        public UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = i;
            }
            count = n;
        }

        // 返回节点 x 的根节点
        private int find(int x) {
            int ret = x;
            while (ret != parent[ret]) {
                // 路径压缩
                parent[ret] = parent[parent[ret]];
                ret = parent[ret];
            }
            return ret;
        }

        // 将 p 和 q 连通
        public void union(int p, int q) {
            preParent = parent.clone();
            int rootP = find(p);
            int rootQ = find(q);
            if (rootP != rootQ) {
                if (rank[rootP] > rank[rootQ]) {
                    parent[rootQ] = rootP;
                } else if (rank[rootP] < rank[rootQ]) {
                    parent[rootP] = rootQ;
                } else {
                    parent[rootQ] = rootP;
                    // 重量平衡
                    rank[rootP] += 1;
                }
                count--;
            }
        }

        // p 和 q 是否连通
        public boolean connected(int p, int q) {
            int rootP = find(p);
            int rootQ = find(q);
            return rootP == rootQ;
        }

        public void reset() {
            parent = preParent.clone();
        }
    }
}

（全文完）