力扣第 442 场周赛

比赛时间 2025-03-23。本场周赛国服共 308 人 AK。

东西冲（东西涌）-天文台栈道穿越。

T1. 船上可以装载的最大集装箱数量（3 分）

解题思路

数学。

时间复杂度：O(1)。

参考代码

class Solution {
    public int maxContainers(int n, int w, int maxWeight) {
        return Math.min(maxWeight / w, n * n);
    }
}

T2. 属性图（4 分）

解题思路

并查集。

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

参考代码

class Solution {
    public int numberOfComponents(int[][] properties, int k) {
        int n = properties.length;
        DSU dsu = new DSU(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (intersectGeK(properties[i], properties[j], k)) {
                    dsu.union(i, j);
                }
            }
        }
        return dsu.sz;
    }

    // intersect >= k
    private boolean intersectGeK(int[] property1, int[] property2, int k) {
        Set<Integer> set = new HashSet<>();
        for (int v : property1) set.add(v);
        Set<Integer> set2 = new HashSet<>();
        for (int v : property2) set2.add(v);
        set.retainAll(set2);
        return set.size() >= k;
    }

    static class DSU {
        int[] fa;
        int sz;

        public DSU(int n) {
            fa = new int[n];
            for (int i = 0; i < n; i++) fa[i] = i;
            sz = n;
        }

        int find(int x) { // 查找
            return x == fa[x] ? fa[x] : (fa[x] = find(fa[x]));
        }

        void union(int p, int q) { // 合并
            p = find(p);
            q = find(q);
            if (p == q) return;
            fa[q] = p;
            sz--;
        }
    }
}

T3. 酿造药水需要的最少总时间（5 分）

解题思路

正向贪心 + 反向校准。

时间复杂度：O(mn)。

参考代码

class Solution {
    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        int m = mana.length;

        // f[i][j] 表示 药水 i 被巫师 j 处理完的时间，答案为 f[m][n]
        long[][] f = new long[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                f[i][j] = Math.max(f[i][j - 1], f[i - 1][j]) + (long) skill[j - 1] * mana[i - 1];
            }
            // 校准
            for (int j = n - 1; j >= 1; j--) {
                f[i][j] = f[i][j + 1] - (long) skill[j + 1 - 1] * mana[i - 1];
            }
        }
        return f[m][n];
    }
}

T4. 使数组元素都变为零的最少操作次数（6 分）

解题思路

数学。

时间复杂度：O(qlogR)。

参考代码

class Solution {
    public long minOperations(int[][] queries) {
        long ans = 0;
        for (int[] q : queries) {
            int l = q[0], r = q[1];
            long sum_level = 0;
            int k = 1;
            int prev = 1;
            int curr = 4;
            while (prev <= r) {
                int start_k = prev;
                int end_k = curr - 1;
                int overlap_start = Math.max(l, start_k);
                int overlap_end = Math.min(r, end_k);
                if (overlap_start <= overlap_end) {
                    long count = overlap_end - overlap_start + 1;
                    sum_level += count * k;
                }
                prev = curr;
                curr *= 4;
                k++;
            }
            ans += (sum_level + 1) / 2;
        }
        return ans;
    }
}

（全文完）