讨论/题目交流/🏆 第 174 场力扣周赛/
🏆 第 174 场力扣周赛

欢迎小伙伴们在这里交流分享你的参赛心得以及体验。【前往竞赛

image.png

3 分 - 方阵中战斗力最弱的 K 行
4 分 - 数组大小减半
5 分 - 分裂二叉树的最大乘积
6 分 - 跳跃游戏 V

展开讨论

5328. 方阵中战斗力最弱的 K 行

记录每一行0的个数和对应是第几行,排个序取前k个对应的行数

class Solution:
    def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
        res = []
        for i, v in enumerate(mat):
            num = 0
            for j in v:
                if j==1:
                    num+=1
            res.append((num, i))
        res.sort()
        return [i[1] for i in res][:k]

5329. 数组大小减半

算一下每个数字出现的次数,再把次数按降序排序,从最大开始累加,当累积超过总数一半时,所对应的累加次数就是结果

class Solution:
    def minSetSize(self, arr: List[int]) -> int:
        le = len(arr)
        ct = dict(collections.Counter(arr))
        it = list(ct.values())
        it.sort(reverse=True)
        res = 0
        sm = 0
        for i in it:
            sm+=i
            res+=1
            if sm>=le/2: break
        return res

5330. 分裂二叉树的最大乘积

一开始看错题了,上了个厕所回来恍然大悟,赶时间怎么想就怎么写了,过程可以更简洁一下

dfs

开两个数组, 一个记录每个非根节点对应子树的和,一个记录所有节点

计算所有节点和 Si

遍历每个非根节点对应子树的和 Sj,计算 Sj*(Si-Sj), 记录最大值即可

class Solution:
    def maxProduct(self, root: TreeNode) -> int:
        mod = 1000000007
        lis = []
        l2 = []
        ans = 0

        def dfs(node):
            nonlocal lis, ans, sm
            if not node:
                return 0
            
            lis.append(node.val)
            res = node.val
            res+=dfs(node.left)
            res+=dfs(node.right)
            
            if node!=root:
                l2.append(res)
            
            return res
        
        dfs(root)
        sm = sum(lis)
        for i in l2:
            ans = max(ans, (sm-i)*i)
        
        return ans%mod

5331. 跳跃游戏 V

最小堆+DP

因为只能从大的柱子往小的跳,所以要先知道小的柱子最多可以访问几个下标

DP[i]表示第i个柱子最多可以访问几个下标

把所有柱子大小和下标压入最小堆

遍历柱子i可以跳到的柱子j,DP[i] = min(DP[j]+1, DP[i])

遍历的时候遇到比自己大的柱子直接跳出

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        from heapq import heappush, heappop
        lis = []
        
        for i, v in enumerate(arr):
            heappush(lis, (v, i))
        
        le = len(arr)
        dp = [-1]*le
        
        
        while lis:
            # print(i)
            v, i = heappop(lis)
            dis = 0
            dp[i] = 1
            for j in range(i+1, min(i+d+1, le)):
              
                if arr[j]>=arr[i]: break
                if dp[j]!=-1:
                    dp[i] = max(dp[j]+1, dp[i])
            for j in range(i-1, max(i-d, 0)-1, -1):
                if arr[j]>=arr[i]: break
                dp[i] = max(dp[j]+1, dp[i])
                
                
        # print(dp)
        return max(dp)

3
展开全部 18 讨论