HTML5教程

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

本文主要是介绍前端工程师的 LeetCode 之旅 -- 174周赛，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！



01
方阵中战斗力最弱的K行



题目描述【Easy】


给你一个大小为 m * n 的方阵 mat，方阵由若干军人和平民组成，分别用 0 和 1 表示。
请你返回方阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但是 i 小于 j ，那么我们认为第 i 行的战斗力比第 j 行弱。
军人总是排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
示例：
mat = [[1,0,0,0],[1,1,1,1],[1,0,0,0],[1,0,0,0]]
k = 2
输出：[0,2]
解释：每行中的军人数目如下
行 0 -> 1
行 1 -> 4
行 2 -> 1
行 3 -> 1
对最弱到最强对这些排序后得到：[0, 2, 3, 1]。



本道题主要考察两点：

  • JavaScript 数组的基本操作

  • sort 方法的多条件排序




02
1338.数组大小减半



题目描述【Medium】


给你一个整数数组 arr。你可以从中选出一个整数集合，并删除这些整数在数组中的每次出现。
返回至少能删除其中的一半整数的整数集合的最小大小。
示例：
arr = [3,3,3,3,5,5,5,2,2,7]
输出：2
解释：选择 {3, 7} 使得结果数组为 [5,5,5,2,2] ，长度为5（原数组的长度一半）。大小为2的可行集合有{3, 5}，{3, 2}，{5, 2}。选择 {2, 7} 是不行的，它的结果数组为 [3,3,3,3,5,5,5]，新数组的长度大于原数组长度的一半。



本题主要考察 JavaScript 中的 Map 数据结构的使用。

要想使得整数集合的大小越小，那么就需要优先删除出现次数最多的整数。

所以需要利用 Map 来记录数组中每个整数出现的次数再按照出现次数的优先级进行排序，最后得到最少删除整数的个数。




03
分裂二叉树的最大乘积



题目描述【Medium】


给你一颗 root 为根的二叉树和一个 head 为第一个节点的链表。
如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True，否则返回 False。
一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。
示例：
root = [1,2,3,4,5,6]
输出：110
解释：删除红色的边，得到两棵子树，和分别为11和10，它们的乘积为 110。



本道题目主要考察数据结构 -- 二叉树。

本题要求子树和的乘积，首先需要求解每棵子树的和。

二叉树一般都是采用递归方法求解，在递归求解子树和的过程中，需要采用 JavaScript 中的 Set 数据结构来存储子树和，这里不作过多赘述，代码清晰明了。

得到子树和之后，再通过减法进行减元操作（常用技巧），最终通过一次迭代比较乘积，即可得到结果。




04
1340.跳跃游戏V



题目描述【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 的代价修改一个格子中的数字，但每个格子中的数字只能修改一次。
请你返回让网格图至少有一条有效路径的最小代价。
示例：
arr = [6,4,14,6,8,13,9,7,10,6,12]
输出：4
解释：你可以从下标 10 开始出发，然后如上图依次经过 10 -> 8 --> 6 --> 7。



本题要求求解最多可以访问多少个下标，需要知道从任意下标出发可以访问的下标情况。

从任意下标 i 跳跃的过程中，都是根据一定的条件向左或者向右跳跃（相似子问题），那么就符合将大规模问题转化为相似子问题的递归思想。

本道题在递归跳跃的过程中存在重复跳跃的问题，需要采用记忆化递归来避免重复的递归次数。

这里可以采用 JavaScript 中的 Map 数据结构，不过本道题目中记忆的结果与下标有关，可以直接采用数组来记忆已经跳跃过的下标。




05
往期回顾









这篇关于前端工程师的 LeetCode 之旅 -- 174周赛的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航