LeetCode 第180场周赛

半个小时做完前三题 然后就开始摸鱼🐟

第一题:矩阵中的幸运数

  给你一个 m * n 的矩阵,矩阵中的数字 各不相同 。请你按 任意 顺序返回矩阵中的所有幸运数。
  
  幸运数是指矩阵中满足同时下列两个条件的元素:
  
  在同一行的所有元素中最小
  在同一列的所有元素中最大
   
  
  示例 1:
  输入:matrix = [[3,7,8],[9,11,13],[15,16,17]]
  输出:[15]
  解释:15 是唯一的幸运数,因为它是其所在行中的最小值,也是所在列中的最大值。
  
  示例 2:
  输入:matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
  输出:[12]
  解释:12 是唯一的幸运数,因为它是其所在行中的最小值,也是所在列中的最大值。
  
  示例 3:
  输入:matrix = [[7,8],[1,2]]
  输出:[7]

思路:
  先获取每行的最小值的集合,再获取每列的最大值的集合。因为所有元素都是不相同的。两个集合的交集即为结果。

代码:

第二题:设计一个支持增量操作的栈

  请你设计一个支持下述操作的栈。
  
  实现自定义栈类 CustomStack :
  
  CustomStack(int maxSize):用 maxSize 初始化对象,maxSize 是栈中最多能容纳的元素数量,栈在增长到 maxSize 之后则不支持 push 操作。
  void push(int x):如果栈还未增长到 maxSize ,就将 x 添加到栈顶。
  int pop():返回栈顶的值,或栈为空时返回 -1 。
  void inc(int k, int val):栈底的 k 个元素的值都增加 val 。如果栈中元素总数小于 k ,则栈中的所有元素都增加 val 。
   
  示例:
  输入:
  [“CustomStack”,”push”,”push”,”pop”,”push”,”push”,”push”,”increment”,”increment”,”pop”,”pop”,”pop”,”pop”]
  [[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
  输出:
  [null,null,null,2,null,null,null,null,null,103,202,201,-1]
  解释:
  CustomStack customStack = new CustomStack(3); // 栈是空的 []
  customStack.push(1); // 栈变为 [1]
  customStack.push(2); // 栈变为 [1, 2]
  customStack.pop(); // 返回 2 –> 返回栈顶值 2,栈变为 [1]
  customStack.push(2); // 栈变为 [1, 2]
  customStack.push(3); // 栈变为 [1, 2, 3]
  customStack.push(4); // 栈仍然是 [1, 2, 3],不能添加其他元素使栈大小变为 4
  customStack.increment(5, 100); // 栈变为 [101, 102, 103]
  customStack.increment(2, 100); // 栈变为 [201, 202, 103]
  customStack.pop(); // 返回 103 –> 返回栈顶值 103,栈变为 [201, 202]
  customStack.pop(); // 返回 202 –> 返回栈顶值 202,栈变为 [201]
  customStack.pop(); // 返回 201 –> 返回栈顶值 201,栈变为 []
  customStack.pop(); // 返回 -1 –> 栈为空,返回 -1

思路:
  按要求写就行了,见代码。

代码:

第三题:将二叉搜索树变平衡

  给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。
  
  如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。
  
  如果有多种构造方法,请你返回任意一种。
  
  
  示例:
  
  输入:root = [1,null,2,null,3,null,4,null,null]
  输出:[2,1,3,null,null,null,4]
  解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。

思路:
  常见做法:旋转换根。
  非常见做法:用有序数组重构树🌲。先中序遍历二叉搜索树得到有序数组。再通过有序数组构建平衡二叉树。

代码:
  这里给出的是非常见做法

第四题:最大的团队表现值

  公司有编号为 1 到 n 的 n 个工程师,给你两个数组 speed 和 efficiency ,其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的 ​​​​​​最大团队表现值 ,由于答案可能很大,请你返回结果对 10^9 + 7 取余后的结果。
  
  团队表现值 的定义为:一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
  
  
  示例 1:
  输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
  输出:60
  解释:
  我们选择工程师 2(speed=10 且 efficiency=4)和工程师 5(speed=5 且 efficiency=7)。他们的团队表现值为 performance = (10 + 5) * min(4, 7) = 60 。
  
  示例 2:
  输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
  输出:68
  解释:
  
  此示例与第一个示例相同,除了 k = 3 。我们可以选择工程师 1 ,工程师 2 和工程师 5 得到最大的团队表现值。表现值为 performance = (2 + 10 + 5) * min(5, 4, 7) = 68 。
  
  输入:n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
  输出:72

思路:

  先按效率降序排序,然后用一个最多含有k个元素的堆维护当前最大的k个速度。
  分析:根据题目给出的数据量,复杂度应该控制在O(nlogn)之内。由于遍历效率复杂度已经为O(n),所以要在O(logn)的时间复杂度找到当前最大的k个速度。如果使用有序的数组来维护当前最大的k个速度,查找新速度位置的复杂度为O(logn)(二分查找),但是插入的复杂度为O(n),因此只能使用堆。
  用一个变量speeds_sum记录当前堆中元素的和。因为重新计算堆的和需要的时间复杂度是O(n)

代码:

发表评论

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