力扣第 371 场周赛

比赛时间 2023-11-12。本场周赛国服共 383 人 AK。

T1. 找出强数对的最大异或值 I（3 分）

解题思路

暴力。

时间复杂度：O(n^2)。

参考代码

class Solution {
    public int maximumStrongPairXor(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(nums[i] - nums[j]) <= Math.min(nums[i], nums[j])) {
                    ans = Math.max(ans, nums[i] ^ nums[j]);
                }
            }
        }
        return ans;
    }
}

T2. 高访问员工（4 分）

解题思路

贪心。由于 0 要替换为正整数，因此最小也要替换为 1，求出最小上界，然后判断是否是合法解即可。

时间复杂度：O(n)。

参考代码

哈希表 + 排序。哈希表分组后，每组独立排序，如果满足，即加入答案。

时间复杂度：O(nlogn)。

class Solution {
    public List<String> findHighAccessEmployees(List<List<String>> access_times) {
        Map<String, List<Integer>> empTimes = new HashMap<>();
        for (List<String> accessTime : access_times) {
            String emp = accessTime.get(0);
            String hh = accessTime.get(1).substring(0, 2);
            String mm = accessTime.get(1).substring(2, 4);
            int time = Integer.parseInt(hh) * 60 + Integer.parseInt(mm);
            empTimes.computeIfAbsent(emp, e -> new ArrayList<>()).add(time);
        }
        List<String> ans = new ArrayList<>();
        for (Map.Entry<String, List<Integer>> entry : empTimes.entrySet()) {
            String emp = entry.getKey();
            List<Integer> time = entry.getValue();
            time.sort(null);
            int sz = time.size();
            for (int i = 2; i < sz; i++) {
                if (time.get(i) - time.get(i - 2) < 60) {
                    ans.add(emp);
                    break;
                }
            }
        }
        return ans;
    }
}

T3. 最大化数组末位元素的最少操作次数（4 分）

解题思路

分类讨论。

• 情况一：不交换 nums1[n-1]、nums2[n-1]，设答案为 ans1；
• 情况二：交换 nums1[n-1]、nums2[n-1]，设答案为 ans2；
• 答案即为 min(ans1, ans2 + 1)。

时间复杂度：O(n)。

参考代码

class Solution {
    public int minOperations(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int ans1 = getAns(nums1, nums2);
        int tmp = nums1[n - 1];
        nums1[n - 1] = nums2[n - 1];
        nums2[n - 1] = tmp;
        int ans2 = getAns(nums1, nums2) + 1;
        return Math.min(ans1, ans2);
    }

    private int getAns(int[] nums1, int[] nums2) {
        int n = nums1.length;
        int cnt = 0;
        for (int i = 0; i < n - 1; i++) {
            if (nums1[i] <= nums1[n - 1] && nums2[i] <= nums2[n - 1]) continue;
            if (Math.max(nums1[i], nums2[i]) > Math.max(nums1[n - 1], nums2[n - 1])) return -1;
            if (Math.min(nums1[i], nums2[i]) > Math.min(nums1[n - 1], nums2[n - 1])) return -1;
            if (nums1[i] > nums1[n - 1] || nums2[i] > nums2[n - 1]) cnt++;
        }
        return cnt;
    }
}

T4. 找出强数对的最大异或值 II（8 分）

解题思路

带删除的 0-1 Trie。

不等式变形，设 x 为最小值：

|x - y| <= min(x, y)
x - y <= x 和 y - x <= x
得 0 <= y <= 2x

排序后类似滑动窗口，枚举最小值为 x 时，把 y <= 2x 的数加到 Trie 中，枚举完后，删除掉 x 即可。

时间复杂度：O(nlogn + nlogU)。其中 logU 最大为 20。

参考代码

class Solution {
    public int maximumStrongPairXor(int[] nums) {
        int n = nums.length;
        Arrays.sort(nums);

        Trie trie = new Trie(n, 20);
        int j = 0;
        int ans = 0;
        for (int x : nums) {
            while (j < n && nums[j] <= x + x) {
                trie.insert(nums[j], 1);
                j++;
            }
            ans = Math.max(ans, trie.query(x));
            trie.insert(x, -1);
        }
        return ans;
    }

    // 0-1 Trie
    private static class Trie {
        int[][] dict;
        int[] cnt;
        int nextIdx, m;

        // n:长度 m:2^m
        public Trie(int n, int m) {
            this.dict = new int[2][n * m + 2];
            this.cnt = new int[n * m + 2];
            this.nextIdx = 1;
            this.m = m;
        }

        // op:1 插入 op:-1 删除
        void insert(int x, int op) {
            int idx = 0;
            for (int k = m - 1; k >= 0; k--) {
                int pos = x >> k & 1;
                if (dict[pos][idx] == 0) {
                    dict[pos][idx] = nextIdx++;
                }
                idx = dict[pos][idx];
                cnt[idx] += op;
            }
        }

        int query(int x) {
            int res = 0;
            int idx = 0;
            for (int k = m - 1; k >= 0; k--) {
                int pos = x >> k & 1;
                if (cnt[dict[1 - pos][idx]] != 0) {
                    res |= 1 << k;
                    idx = dict[1 - pos][idx];
                } else {
                    idx = dict[pos][idx];
                }
            }
            return res;
        }
    }
}

（全文完）