Leetcode Weekly Contest 174

标签: 算法  leetcode

5328. The K Weakest Rows in a Matrix

1. 题意

给定一个二维矩阵mat,每一行由0,1组成, 1代表士兵,0代表平民,如果一行士兵更多,则称这一行的战斗力更强,求从弱到强的k行,返回下标。

2. 思路

简单的统计每一行中1的个数,然后进行排序即可
这里不仅要记录每一行中1的个数,还得记录每一行的下标!!!
这里不能使用元组来做,因为元组不支持赋值操作,也就是不能进行修改!

第一种方法:通过dict来存储, 浪费存储空间了!
这里得学会对dict进行排序,排序后返回了一个元组的数组
c = sorted(cc.items(), key = lambda d:d[1]) # 变成元组了啊!

第二种方法:通过二维数组来存储!
cc.sort(key = lambda c:c[1]) # 数组按照第二项进行从小往大排序

3. python实现

class Solution(object):
    def kWeakestRows(self, mat, k):
        """
        :type mat: List[List[int]]
        :type k: int
        :rtype: List[int]
        """
# ----------------刚刚比赛时写的并不好啊1------------------------------------
#         cc = collections.defaultdict(int)
#         for i in range(len(mat)):
#             for j in range(len(mat[0])):
#                 if mat[i][j] == 1:
#                     cc[i] += 1
#                 else:
#                     if j==0:
#                         cc[i] = 0
#                     break
        
#         c = sorted(cc.items(), key = lambda d:d[1]) # 变成元组了啊!
#         # print(c)
#         res = []
#         for nums in c:
#             if k > 0:
#                 res.append(nums[0])
#             k -= 1
#         return res
        
        m, n = len(mat), len(mat[0])  
        # 直接用元组来存,(i,j)表示第i行中有j个1
        cc = [[0,0] for i in range(m)] 
        
        for i in range(m):
            cc[i][0] = i
            for j in range(n):
                if mat[i][j] == 1:
                    cc[i][1] += 1
                else: # 一行中1是连续的啊
                    break  
        
        cc.sort(key = lambda c:c[1]) # 数组按照第二项进行从小往大排序
        
        res = []
        for i in range(k):
            res.append(cc[i][0])
        
        return res

5329. Reduce Array Size to The Half

1. 题意

给定一个一维数组arr,你可以选择一个整数集合,然后把数组中所有出现在集合中的数都去掉,最后让数组的长度减半!求最短的集合

比如arr = [3,3,3,3,5,5,5,2,2,7], set = {3,5} or {3,2} or {5,2} , 删除set中在arr中出现的数,都可以导致arr的长度减半!因此最短的集合的长度为2!

2.思路

统计arr中每一个数出现的次数,然后从大到小排序,当然是从出现最多的数开始删除!

3. Python实现

class Solution(object):
    def minSetSize(self, arr):
        """
        :type arr: List[int]
        :rtype: int
        """
        n = len(arr)
        cc = collections.Counter(arr)
        c = sorted(cc.items(), key = lambda d:-d[1])  # 按照出现次数排序
        res = 0
        count = 0
        # print(c)
        for tup in c:
            if count < n//2:
                count += tup[1]
                res += 1
            else:
                break
            
        return res

5330. Maximum Product of Splitted Binary Tree

1. 题意

给定一棵二叉树root, 然后每次删除其中一条边,把二叉树分裂成两棵二叉树,求两棵二叉树的和的乘积的最大值!
在这里插入图片描述

2. 思路

我看到这道题,立马就思考去掉边怎么操作?还有就是子树如何求和?
数据量最大有50000,并且数值在0-10000之间,可以看出节点有重复值,并且时间复杂度不能是O(N^2),否则就会超时!

所以最好就是在遍历的时候顺便求子树的和,并且顺便也求两个子树之间的乘积,这样时间复杂度就控制在O(N)了。

做这道题之前最好做一下另外一道题:
程序员面试算法宝典—解题总结: 第三章 二叉树 3.4 如何求一棵二叉树的最大子树和

会求二叉树的子树和就会做这道题了!

3. python实现

class Solution(object):
    def maxProduct(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.allsum = 0
        self.product = float('-inf')
        
        def dfs(root): # 求树的所有节点之和
            if not root: return 
            self.allsum += root.val
            dfs(root.left)
            dfs(root.right)
        
        def post(root): # 返回以root为根的子树的和,后序遍历,自底向上来遍历
            if not root: return 0
            lsums = post(root.left)
            rsums = post(root.right)
            subsum = lsums + rsums + root.val 
            # print(subsum, (self.allsum-subsum), subsum* (self.allsum-subsum))
            self.product = max(self.product, subsum* (self.allsum-subsum))
            return subsum
            
        dfs(root)
        post(root)
        return self.product % 1000000007

5331. Jump Game V

版权声明:本文为weixin_44038165原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_44038165/article/details/104143253

智能推荐

Qt 之 Query Model Example 解析

总体概括 Query Model Example主要演示了怎么使用QSqlQueryModel这个数据库查询模型类。其中包括创建普通的数据库查询模型、可编辑的数据库查询模型和自定义的数据库查询模型。普通(默认)的数据库查询模型是只读的(不可再模型中编辑数据,模型只通过视图展示数据);可编辑的数据库查询模型重写了QSqlQueryModel的flags()方法和setData()方法;自定义的数据库...

Flutter:Scaffold.of() called with a context that does not contain a Scaffold.

Flutter:Scaffold.of() called with a context that does not contain a Scaffold. 当我第一次点击按钮想要弹出底部消息时出现了如下错误 当BuildContext在Scaffold之前时,调用Scaffold.of(context)会报错。这时可以通过Builder Widget来解决,代码如下:...

【机器学习基础】线性回归

                                                        &nbs...

08-Vue实现书籍购物车案例

书籍购物车案例 index.html main.js style.css 1.内容讲解 写一个table和thead,tbody中每一个tr都用来遍历data变量中的books列表。 结果如下: 在thead中加上购买数量和操作,并在对应的tbody中加入对应的按钮。结果如下: 为每个+和-按钮添加事件,将index作为参数传入,并判断当数量为1时,按钮-不可点击。 结果如下: 为每个移除按钮添加...

堆排序

堆排序就是利用堆进行排序的方法,基本思想是,将代排序列构造成一个大根堆,此时整个序列的最大值就是堆顶的根节点。将它与堆数组的末尾元素交换,此时末尾元素就是最大值,移除末尾元素,然后将剩余n-1个元素重新构造成一个大根堆,堆顶元素为次大元素,再次与末尾元素交换,再移除,如此反复进行,便得到一个有序序列。 (大根堆为每一个父节点都大于两个子节点的堆) 上面思想的实现还要解决两个问题: 1.如何由一个无...

猜你喜欢

基础知识(变量类型和计算)

一、值类型 常见的有:number、string、Boolean、undefined、Symbol 二、引用类型 常用的有:object、Array、null(指针指向为空)、function 两者的区别: 值类型暂用空间小,所以存放在栈中,赋值时互不干扰,所以b还是100 引用类型暂用空间大,所以存放在堆中,赋值的时候b是引用了和a一样的内存地址,所以a改变了b也跟着改变,b和a相等 如图: 值...

Codeforces 1342 C. Yet Another Counting Problem(找规律)

题意: [l,r][l,r][l,r] 范围内多少个数满足 (x%b)%a!=(x%a)%b(x \% b) \% a != (x \% a) \% b(x%b)%a!=(x%a)%b。 一般这种题没什么思路就打表找一下规律。 7 8 9 10 11 12 13 14 15 16 17 18 19 20 28 29 30 31 32 33 34 35 36 37 38 39 40 41 49 50...

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3)

[笔记]飞浆PaddlePaddle-百度架构师手把手带你零基础实践深度学习-21日学习打卡(Day 3) (Credit: https://gitee.com/paddlepaddle/Paddle/raw/develop/doc/imgs/logo.png) MNIST数据集 MNIST数据集可以认为是学习机器学习的“hello world”。最早出现在1998年LeC...

哈希数据结构和代码实现

主要结构体: 实现插入、删除、查找、扩容、冲突解决等接口,用于理解哈希这种数据结构 完整代码参见github: https://github.com/jinxiang1224/cpp/tree/master/DataStruct_Algorithm/hash...