LeetCode2020第176场周赛
5340. 统计有序矩阵中的负数
题目描述
给你一个 m * n
的矩阵 grid
,矩阵中的元素无论是按行还是按列,都以非递增顺序排列。 请你统计并返回 grid
中 负数 的数目。 示例 1:
输入:grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
输出:8
解释:矩阵中共有 8 个负数。
示例 2:
输入:grid = [[3,2],[1,0]]
输出:0
示例 3:
输入:grid = [[1,-1],[-1,-1]]
输出:3
示例 4:
输入:grid = [[-1]]
输出:1
题解
遍历二维数组,统计负数的个数即可。 时间复杂度为:$O(n^2)$ 空间复杂度为:$O(1)$
代码
1 | class Solution { |
5341. 最后 K 个数的乘积
题目描述
请你实现一个「数字乘积类」ProductOfNumbers
,要求支持下述两种方法: 1. add(int num)
- 将数字
num
添加到当前数字列表的最后面。
getProduct(int k)
- 返回当前数字列表中,最后
k
个数字的乘积。 - 你可以假设当前列表中始终 至少 包含
k
个数字。
题目数据保证:任何时候,任一连续数字序列的乘积都在 32-bit 整数范围内,不会溢出。 示例:
输入:
[“ProductOfNumbers”,”add”,”add”,”add”,”add”,”add”,”getProduct”,”getProduct”,”getProduct”,”add”,”getProduct”]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
输出:
[null,null,null,null,null,null,20,40,0,null,32]
解释:
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3); // [3]
productOfNumbers.add(0); // [3,0]
productOfNumbers.add(2); // [3,0,2]
productOfNumbers.add(5); // [3,0,2,5]
productOfNumbers.add(4); // [3,0,2,5,4]
productOfNumbers.getProduct(2); // 返回 20 。最后 2 个数字的乘积是 5 * 4 = 20
productOfNumbers.getProduct(3); // 返回 40 。最后 3 个数字的乘积是 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // 返回 0 。最后 4 个数字的乘积是 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8); // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32 。最后 2 个数字的乘积是 4 * 8 = 32
题解1
周赛的时候没有多想,上来直接用vector来存储所有的数,add
函数用push_back
来实现。最后k个元素乘积直接从vector的最后一个元素开始,将k个元素乘起来即可。 时间复杂度为:O(n) 空间复杂度为:O(n)
代码1
1 | class ProductOfNumbers { |
题解2
参照LeetCode - 圈子,对于第二题给出了许多优化的算法。题目中给出的限制条件需要注意。
题目数据保证:任何时候,任一连续数字序列的乘积都在 32-bit 整数范围内,不会溢出。 0 <= num <= 100
对于任一连续序列的乘积都小于32位整数范围,表示序列中最多只有31个数大于1($2^{31} - 1$),其它数字都是0和1。所以可以用前缀和来统计0-100这101个数字在序列中出现的个数,这里空间开销是101 * n(n是序列的总长度)。计算最后K个数的乘积,只需要先找出每个数字num出现的次数cnt,$cnt_{num} = vec[n][num] - vec[n - k][num]$,出现0,最后乘积就为0,出现1,则跳过1不算。然后再求其它数字乘积即可。 这里我介绍前缀积的思路。数组存储连续数字的乘积,遇到0,清除数组,重新统计。当最后数组长度不足K时,表示乘积为0,否则就用总乘积除以前面元素的乘积。 时间复杂度为:O(1) 空间复杂度为:O(n)
代码2
1 | class ProductOfNumbers { |
1353. 最多可以参加的会议数目
题目描述
给你一个数组 events
,其中 events[i] = [startDayi, endDayi]
,表示会议 i
开始于 startDayi
,结束于 endDayi
。 你可以在满足 startDayi <= d <= endDayi
中的任意一天 d
参加会议 i
。注意,一天只能参加一个会议。 请你返回你可以参加的 最大 会议数目。 示例 1:
输入:events = [[1,2],[2,3],[3,4]]
输出:3
解释:你可以参加所有的三个会议。
安排会议的一种方案如上图。
第 1 天参加第一个会议。
第 2 天参加第二个会议。
第 3 天参加第三个会议。
示例 2:
输入:events= [[1,2],[2,3],[3,4],[1,2]]
输出:4
示例 3:
输入:events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
输出:4
示例 4:
输入:events = [[1,100000]]
输出:1
示例 5:
输入:events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
输出:7
题解
贪心+优先队列 首先将区间按开始时间进行排序,然后结束时间早的先安排。还需要鼗安排冲突,不合理的去掉。 时间复杂度为:O(nlogn) 空间复杂度为:O(n)
代码
1 | class Solution { |
5343. 多次求和构造目标数组
题目描述
给你一个整数数组 target
。一开始,你有一个数组 A
,它的所有元素均为 1 ,你可以执行以下操作:
- 令
x
为你数组里所有元素的和 - 选择满足
0 <= i < target.size
的任意下标i
,并让A
数组里下标为i
处的值为x
。 - 你可以重复该过程任意次
如果能从 A
开始构造出目标数组 target
,请你返回 True ,否则返回 False 。 示例 1:
输入:target = [9,3,5]
输出:true
解释:从 [1, 1, 1] 开始
[1, 1, 1], 和为 3 ,选择下标 1
[1, 3, 1], 和为 5, 选择下标 2
[1, 3, 5], 和为 9, 选择下标 0
[9, 3, 5] 完成
示例 2:
输入:target = [1,1,1,2]
输出:false
解释:不可能从 [1,1,1,1] 出发构造目标数组。
示例 3:
输入:target = [8,5]
输出:true
题解
正向思考,不知道用所有的数字之和去替换哪一个数字,尝试的话可能性太多,实现难度太大。反向思考的话,数组中最大的数字显然是上一个数组中所有数字之和,而它所替换的数字等于最大的数字减去其它数字之和。如此替换下去,如果最后所有的数字都为1,表示可以构造目标数组,一旦出现数字0或负数,表示不能构造。
代码
1 | class Solution { |