阅读 962

前端工程师的 LeetCode 之旅 -- 180周赛




01
矩阵中的幸运数字



题目描述【Easy】


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



本题主要考察数组的基本操作,两重循环暴力求解。




02
设计一个支持增量的栈



题目描述【Medium】


请你设计一个支持下述操作的栈。
实现自定义栈类 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 。



本题主要考察数据结构 -- 栈。

在 JavaScript 中通常采用数组的 pop 和 push 来模拟栈的行为。




03
将二叉搜索树变平衡



题目描述【Medium】


给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。
如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 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] 也是一个可行的构造方案。



本题主要考察二叉树中具有特殊性质的 BST(二叉搜索树)和 BBT(平衡二叉树)。

题目描述中已经介绍了 BBT 的性质,而 BST 的性质这里再巩固一下:

  • 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;

  • 若任意节点的右子树不空,则右子树上所有节点的值均大于或等于它的根节点的值;

  • 任意节点的左、右子树也分别为二叉搜索树;

在构建具有平衡性质的 BST 之前,需要先遍历出用于重新构建 BST 的节点,这里采用中序遍历(BST 中序遍历的结果是一个单调递增的数组)。

要想构建具有平衡性质的二叉树,必须保证左右子树具有的节点相差程度最小,所以要对得到的节点进行均分。

由于其本身是一个单调递增的数组,所以很容易保证构建出来二叉树为二叉搜索树。




04
5359.最大团队表现值



题目描述【Hard】


公司有编号为 1 到 n 的 n 个工程师,给你两个数组 speed 和 efficiency ,其中 speed[i] 和 efficiency[i] 分别代表第 i 位工程师的速度和效率。请你返回由最多 k 个工程师组成的 最大团队表现值 ,由于答案可能很大,请你返回结果对 10^9 + 7 取余后的结果。
团队表现值 的定义为:一个团队中「所有工程师速度的和」乘以他们「效率值中的最小值」。
示例:
输入: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 。



团队表现值主要由两个维度决定:

  • 工程师的速度之和

  • 工程师的最小效率

要使得团队表现值最大,那么这两个维度应该尽可能的最大,所以需要使用贪心策略。

  • 优先选择效率高的工程师,可以将效率数组降序处理,因为速度数组和效率数组是一一对应的关系,所以需要将它们组成一个复合数组。

  • 保持工程师的速度之和最大,则需要利用优先队列来维护当前工程师的速度集合,有新工程师加入时,吐出当前队列中最小的速度,从而维护一个最大速度和。

JavaScript 中是没有数据结构 heap(堆)的,所以需要手动实现一个小根堆来实现优先队列。(下一篇会详细讲解 heap 以及 JavaScript 相关的实现)

本道题还有一个比较坑的地方就是部分测试用例超出了 JavaScript 中 Number 的范围,所以需要用到 BigInt 内置对象来解决这样的问题。




05
往期精彩回顾