力扣 之 第442场周赛

• 今天稍微总结一下力扣的442场周赛

比赛地址

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

• 直接暴力求解即可：

class Solution:
    def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
        # 直接暴力
        ans = 0
        i = 0
        while ans + w <= maxWeight and i+1 <= n*n:
            ans += w
            i += 1
        return i

• 上述的代码是直接通过模拟进行求解的，其实可以通过数学的方法进行求解

class Solution:
    def maxContainers(self, n: int, w: int, maxWeight: int) -> int:
        return min(n*n,maxWeight//w)

3493.属性图

• 本质是求解这个连通分量，求解连通分量的问题，可以使用BFS、DFS、并查集三种方法，在这里，我们介绍这个DFS的代码思路

class Solution:
    def numberOfComponents(self, properties: List[List[int]], k: int) -> int:
        # 先定义这个 intersect函数,出入两个数组
        def intersect(a,b):
            # 学会使用集合的交集运算快速求解
            return len(set(a)&set(b))
            
        # 你得判断是否有边
        def check(i,j):
            if intersect(properties[i],properties[j]) >= k:
                return True
            else:
                return False
        res= 0 

        # 使用dfs搜索
        n = len(properties)
        visited = [False]*n
        def dfs(i):
            for j in range(n):
                if not visited[j] and check(i,j):
                    visited[j] = True
                    dfs(j)
        for i in range(n):
            # 枚举开始的位置
            if not visited[i]:
                visited[i] = True
                dfs(i)
                # 调用多少次这个dfs，就说明有多少个连通分类
                res += 1
        return res

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

• 分析题目，发现必须制造过程中一个巫师接着一个巫师生产同一个药水的生产过程，在求解的过程中，十分容易陷入知道是什么思路，但是实际的代码确表达不出来的地步，总的来说，就是题目的模拟的过程并没有想清楚而导致的
• 这个题目的关注点，我们都知道是上一轮的制药的每一个巫师的完成的时间，关注点应该是通过这个上一轮的完成时间，正向遍历，然后再逆推得到本轮每一个巫师完成制药的时间，正向遍历，可以得出全部人满足的情况下，完成制药的最终时间

class Solution:
    def minTime(self, skill: List[int], mana: List[int]) -> int:
        # 应该怎么思考？
        n,m = len(skill),len(mana)
        # 首先得记录在每一次制造的时候结束时间
        finishtime = [0]*n 
        for i in range(m):
            t_sum = 0
            # 得出本轮的最终的完成制药的时间
            for x,last in  zip(skill,finishtime):
                t_sum = max(t_sum,last) + x * mana[i]
            finishtime[-1] = t_sum
            # 倒推这个结束时间
            for j in range(n-2,-1,-1):
                finishtime[j] = finishtime[j+1] - skill[j+1]*mana[i]
        return finishtime[-1]

3495.使数组元素都变为0的最少操作次数

• 首先得学会转化问题，将问题转化为首先将每一个数，转化为所需的操作次数，然后就变为每次选择两个数减去1，求解最少的操作次数

def f(n: int) -> int:
    m = n.bit_length()
    res = sum((i + 1) // 2 << (i - 1) for i in range(1, m))
    return res + (m + 1) // 2 * (n + 1 - (1 << m >> 1))

class Solution:
    def minOperations(self, queries: List[List[int]]) -> int:
        return sum((f(r) - f(l - 1) + 1) // 2 for l, r in queries)

灵神题解