力扣第 119 场双周赛

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

T1. 找到两个数组中的公共元素（3 分）

解题思路

集合 模拟。

时间复杂度：O(n+m)。

参考代码

class Solution {
    public int[] findIntersectionValues(int[] nums1, int[] nums2) {
        int[] ans = new int[2];
        BitSet set1 = new BitSet(101);
        BitSet set2 = new BitSet(101);
        for (int x : nums1) set1.set(x);
        for (int x : nums2) set2.set(x);
        for (int x : nums1) if (set2.get(x)) ans[0]++;
        for (int x : nums2) if (set1.get(x)) ans[1]++;
        return ans;
    }
}

T2. 消除相邻近似相等字符（4 分）

解题思路

分组循环。答案为每个分组的长度 / 2 的和。

时间复杂度：O(n)。

参考代码

class Solution {
    public int removeAlmostEqualCharacters(String word) {
        int n = word.length();
        char[] s = word.toCharArray();
        int ans = 0;
        int i = 0;
        while (i < n) {
            // 分组循环
            int st = i;
            for (i++; i < n && Math.abs(s[i] - s[i - 1]) <= 1; i++) {
            }
            ans += (i - st) / 2;
        }
        return ans;
    }
}

T3. 最多 K 个重复元素的最长子数组（5 分）

解题思路

滑动窗口。

时间复杂度：O(n)。

参考代码

class Solution {
    public int maxSubarrayLength(int[] nums, int k) {
        int n = nums.length;
        Map<Integer, Integer> cntMap = new HashMap<>();
        int l = 0, r = 0;
        int ans = 0;
        // 频次超过 k 的数目
        int gt_cnt = 0;
        while (r < n) {
            if (cntMap.getOrDefault(nums[r], 0) == k) gt_cnt++;
            cntMap.put(nums[r], cntMap.getOrDefault(nums[r], 0) + 1);

            while (gt_cnt > 0) {
                cntMap.put(nums[l], cntMap.get(nums[l]) - 1);
                if (cntMap.get(nums[l]) == k) gt_cnt--;
                l++;
            }
            ans = Math.max(ans, r - l + 1);

            r++;
        }
        return ans;
    }
}

T4. 关闭分部的可行集合数目（6 分）

解题思路

二进制枚举 + Floyd。

数据范围十分小，直接二进制枚举即可，哪怕跑 dijkstra 也不会 TLE。

时间复杂度：O(m + 2^n * n^3)。

参考代码

class Solution {
    private static final int INF = (int) 1e9;

    public int numberOfSets(int n, int maxDistance, int[][] roads) {
        int[][] g = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(g[i], INF);
            g[i][i] = 0;
        }
        for (int[] p : roads) {
            int u = p[0], v = p[1], wt = p[2];
            g[u][v] = Math.min(g[u][v], wt);
            g[v][u] = Math.min(g[v][u], wt);
        }

        int ans = 0;
        int[][] adj = new int[n][n];
        for (int mask = 0; mask < 1 << n; mask++) {
            // 重置 adj
            for (int i = 0; i < n; i++) {
                if ((mask >> i & 1) == 1) {
                    System.arraycopy(g[i], 0, adj[i], 0, n);
                }
            }

            // Floyd
            for (int k = 0; k < n; k++) {
                if ((mask >> k & 1) == 0) continue;
                for (int i = 0; i < n; i++) {
                    if ((mask >> i & 1) == 0) continue;
                    for (int j = 0; j < n; j++) {
                        adj[i][j] = Math.min(adj[i][j], adj[i][k] + adj[k][j]);
                    }
                }
            }

            int maxD = 0;
            for (int i = 0; i < n; i++) {
                if ((mask >> i & 1) == 0) continue;
                for (int j = 0; j < n; j++) {
                    if ((mask >> j & 1) == 0) continue;
                    maxD = Math.max(maxD, adj[i][j]);
                }
            }
            if (maxD <= maxDistance) {
                ans++;
            }
        }
        return ans;
    }
}

（全文完）