阅读 1031

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




01
有多少小于当前数字的数字



题目描述【Easy】


给你一个数组 nums,对于其中一个元素 nums[i],请你统计数组中比它小的所有数字的数目。
换而言之m,对于每一个 nums[i] 你必须计算出有效的 j 的数量,其中 j 满足 j != i 且 nums[j] < nums[i]。
以数组的形式返回答案。



本题数据规模比较小,暴力两重循环即可得解。




02
通过投票对团队排名



题目描述【Medium】


现在有一个特殊的排名系统,依据参赛团队在投票人心中的次序进行排序,每一个投票者都需要按从高到低的顺序对参与排名的所有团队进行排位。
排名规则如下:
参赛团队的排名次序依照其所获「排位第一」的票的多少决定。如果存在多个团队并列的情况,将继续考虑其「排名第二」的票的数量。以此类推,直到不存在并列的情况。
如果在考虑完所有投票情况后仍然出现并列的情况,则根据团队字母的顺序进行排名。
给你一个字符串数组 votes 代表全体投票者给出的排位情况,请你根据上述排位规则对所有的参赛团队进行排名。
请你返回能表示按排名系统排序后所有参赛团队的排名的字符串。



本题主要考察以下三点:

  • JavaScript 中的 Map 数据结构

  • JavaScript 数组的基本操作

  • JavaScript sort 方法的多条件排序

首先需要遍历整个 votes 数组,统计所有参赛团队获得排位的情况。

因为最多有 26 支参赛队伍,所以需要在排序时优先根据 26 种排名数量来排序参赛队伍,如果获得 26 种排名的情况一致,那么需要再比较一下参赛队伍的字母顺序。

最后,通过 JavaScript 中的 join 方法返回参赛队伍的排名字符串。




03
5346.二叉树中的列表



题目描述【Medium】


给你一颗 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中,存在一条一直向下的路径,且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值,那么请你返回 True,否则返回 False。
一直向下的路径的意思是:从树中某个节点开始,一直连续向下的路径。



本道题主要涉及两大数据结构:

  • 链表

  • 二叉树

题目要求验证二叉树中是否存在一条一直向下的路径,那么我们可以从二叉树中任意子树的根节点开始尝试,所以需要先记录二叉树所有子树的根节点,实际上就是遍历二叉树操作,一般采用递归思想处理。

获取到子树根节点之后,遍历链表即可验证是否存在一直向下的路径,遍历链表采用迭代 next 指针完成。




04
一条有效路径的最小代价



题目描述【Hard】


给你一个 m * n 的网格图 grid。grid 中每个格子都有一个数字,对应着从该格子出发下一步走的方向。grid[i][j] 中的数字可能有以下几种情况:
1、下一步往右走,也就是你会从 grid[i][j] 走到 grid[i][j + 1]。
2、下一步往左走,也就是你会从 grid[i][j] 走到 grid[i][j - 1]。
3、下一步往下走,也就是你会从 grid[i][j] 走到 grid[i + 1][j]。
4、下一步往上走,也就是你会从 grid[i][j] 走到 grid[i - 1][j]。
注意网格图中可能会有无效数字,因为它们可能指向 grid 之外的区域。
一开始,你会从最最左上角的格子 (0,0) 出发。我们定义一条有效路径为从格子(0,0)出发,每一步都顺着数字对应方向走,最终在右下角的格子(m - 1, n - 1)结束的路径。有效路径不需要是最短路径。
你可以花费 cost = 1 的代价修改一个格子中的数字,但每个格子中的数字只能修改一次。
请你返回让网格图至少有一条有效路径的最小代价。



这是一道图论相关的题型。

由题目中的描述可知:如果按照箭头的方向走,那么单向边的权重为0,否则单向边的权重为1。

因为不存在负权重的问题,所以本道题目可以通过 Dijkstra 求解。

不过官网给出的最优解法是:BFS 和 双端队列(0-1BFS)。

详细的过程建议直接看官方题解,下面给出 JavaScript 的实现代码。

由于 JavaScript 没有双端队列的数据结构,所以可以采用数组来模拟双端队列的特性。

但是 JavaScript 数组的 unshift 和 shift 操作的成本是非常高的(具体可以查看 V8 数组实现源码),这里可以基于单链表模拟双端队列的特性,降低队首操作的时间复杂度。




05
往期精彩回顾









关注下面的标签,发现更多相似文章
评论