LeetCode 周赛 442

667
Algorithm
LeetCodeContest
本文最后更新于 2 分钟前，文中所描述的信息可能已发生改变。

Q1. 船上可以装载的最大集装箱数量 ​

解题思路 ​

比较简单，直接返回容器和载重最小值即可

示例代码 ​

python
class Solution:
    def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
        return min(n * n, maxWeight // w)
java
class Solution {
    public int maxContainers(int n, int w, int maxWeight) {
        return Math.min(n * n, maxWeight / w);
    }
}

Q2. 属性图 ​

解题思路 ​

用set判断交集，再用unionfind计算联通块个数（用dfs也可以）

示例代码 ​

python
class Solution:
    def numberOfComponents(self, ps: List[List[int]], k: int) -> int:
        n = len(ps)
        parent = list(range(n))

        def find(x):
            if parent[x] == x:
                return x
            parent[x] = find(parent[x])
            return parent[x]

        def union(x, y):
            parent[find(y)] = find(x)

        s = [set(ps[i]) for i in range(n)]
        for i in range(n):
            for j in range(i + 1, n):
                if len(s[i] & s[j]) >= k:
                    union(i, j)
        return sum(i == find(i) for i in range(n))

Q3. 酿造药水需要的最少总时间 ​

解题思路 ​

枚举，用上一个药水的完成最后时间更新当前巫师可能的最晚开始时间

示例代码 ​

python
class Solution:
    def minTime(self, skill: list[int], mana: list[int]) -> int:
        n, m = len(skill), len(mana)
        ans = [0] * n
        pre = list(accumulate(skill, initial=0))
        fmax = lambda x, y: x if x > y else y
        for i in range(m):
            for j in range(n):
                if i > 0:
                    ans[j] = fmax(ans[n - 1] - mana[i - 1] * (pre[n] - pre[j + 1]), ans[fmax(0, j - 1)]) + mana[i] * skill[j]
                else:
                    ans[j] = ans[j - 1] + mana[i] * skill[j]
        return ans[n - 1]
java
class Solution {
    public long minTime(int[] skill, int[] mana) {
        int n = skill.length;
        int m = mana.length;
        long[] ans = new long[n];
        int[] pre = new int[n + 1];
        for (int i = 0; i < n; i ++) {
            pre[i + 1] = pre[i] + skill[i];
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (i > 0) {
                    ans[j] = Math.max(ans[n - 1] - (long) mana[i - 1] * (pre[n] - pre[j + 1]), ans[Math.max(0, j - 1)]) + (long) mana[i] * skill[j];
                } else {
                    ans[j] = ans[Math.max(0, j - 1)] + (long) mana[i] * skill[j];
                }
            }
        }
        return ans[n - 1];
    }
}

Q4. 使数组元素都变为零的最少操作次数 ​

解题思路 ​

找规律，枚举4的倍数，即操作次数，判断相应区间内数的个数，乘以操作次数，累加即可

[4 ^ (k - 1), 4 ^ k) 区间内的数个数为 4 ^ k - 4 ^ (k - 1) , 操作次数为 k

示例代码 ​

python
class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        ans = 0
        for l, r in queries:
            res = 0
            base = 1
            cnt = 1
            while base * 4 <= r:
                base *= 4
                if base > l:
                    res += (base - l) * cnt
                    l = base
                cnt += 1
            if r >= l:
                res += (r - l + 1) * cnt
            ans += (res + 1) // 2
        return ans
LeetCode Weekly Contest 443
Trading API Module