LeetCode第176场周赛

有一道贪心不太熟 排名 167 / 2409

第一题:统计有序矩阵中的负数

  给你一个 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

  思路: 统计即可

第二题:最后 K 个数的乘积

  请你实现一个「数字乘积类」ProductOfNumbers,要求支持下述两种方法:
  
  1. add(int num)
  
  将数字 num 添加到当前数字列表的最后面。
  2. 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

  思路:这题其实测试用例很简单,不过考虑了时间复杂度用一个数组product[]记录累乘的值,然后用product[-1]product[-k-1]作除法来求最后k个元素的乘积。

第三题:最多可以参加的会议数目

 

  给你一个数组 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

  思路:注意题目中一个会议只需挑一天参加即算参加了
  使用贪心算法,开始时令day=1,第day天如果没有参加会议,分为以下两种情况:
  (1) 第day天能够参加会议,则参加结束时间最早的会议,然后继续考虑第day+1天。
  (2) 第day天不能参加会议,则等待n天后重试,也就是在剩下的会议中选择开始时间最早的作为新的day值来继续循环。

流程图如下:

  具体实现时为了节省时间,先将会议排序,假设所有的会议events = [[27,29],[28,32],[3,3],[24,25],[7,7],[22,25],[14,15],[13,17],[1,2],[7,7],[10,12],[9,13],[21,25],[20,21],[20,22],[19,20],[27,28],[9,9],[21,24],[18,21],[6,10],[29,30],[22,24]],我们先把它按照开始时间为主键,结束时间为次键排序,结果如下:

循环过程为:

代码:

第四题:多次求和构造目标数组 

  给你一个整数数组 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

  思路:每次都用target中最大的元素减去其他元素的和。如果最后的结果全是1,则返回True,如果中间出现了小于1的结果,则返回False

  示例1, target = [9,3,5]

  示例2, target = [1,1,1,2]

  示例3, target = [8,5]

代码:

发表评论

电子邮件地址不会被公开。 必填项已用*标注