阅读 572

前端工程师的 LeetCode 之旅 - 夜喵专场(22)




01
两个数组之间的距离值



题目描述【Easy】


给你两个整数数组 arr1 , arr2 和一个整数 d ,请你返回两个数组之间的 距离值 。
「距离值」 定义为符合此描述的元素数目:对于元素 arr1[i] ,不存在任何元素 arr2[j] 满足 |arr1[i]-arr2[j]| <= d 。
示例:
输入:arr1 = [4,5,8], arr2 = [10,9,1,8], d = 2
输出:2
解释:
对于 arr1[0]=4 我们有:
|4-10|=6 > d=2
|4-9|=5 > d=2
|4-1|=3 > d=2
|4-8|=4 > d=2
对于 arr1[1]=5 我们有:
|5-10|=5 > d=2
|5-9|=4 > d=2
|5-1|=4 > d=2
|5-8|=3 > d=2
对于 arr1[2]=8 我们有:
|8-10|=2 <= d=2
|8-9|=1 <= d=2
|8-1|=7 > d=2
|8-8|=0 <= d=2



本道题主要考察数组的基本循环遍历操作。




02
安排电影院座位



题目描述【Medium】


电影院的观影厅中有 n 行座位,行编号从 1 到 n ,且每一行内总共有 10 个座位,列编号从 1 到 10 。
给你数组 reservedSeats ,包含所有已经被预约了的座位。比如说,researvedSeats[i]=[3,8] ,它表示第 3 行第 8 个座位被预约了。
请你返回 最多能安排多少个 4 人家庭 。4 人家庭要占据 同一行内连续 的 4 个座位。隔着过道的座位(比方说 [3,3] 和 [3,4])不是连续的座位,但是如果你可以将 4 人家庭拆成过道两边各坐 2 人,这样子是允许的。
示例:
输入:n = 3, reservedSeats = [[1,2],[1,3],[1,8],[2,6],[3,1],[3,10]]
输出:4
解释:上图所示是最优的安排方案,总共可以安排 4 个家庭。蓝色的叉表示被预约的座位,橙色的连续座位表示一个 4 人家庭。



因为每一行的座位固定 10 个,所以每一行可以容纳的家庭数是可以枚举的。

采用哈希表记录每一行各位置的占用情况,即可得出每一行容纳家庭的数量。

本道题有一个卡时间的点:n 的取值比 reservedSeats 长度的取值要大得多,所以需要以被占用的行数为遍历范围,对于未占用的行数 k,它能够容纳的家庭数自然是 2 * k。




03
将整数按权重排序



题目描述【Medium】


我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数:
如果 x 是偶数,那么 x = x / 2
如果 x 是奇数,那么 x = 3 * x + 1
比方说,x=3 的权重为 7 。因为 3 需要 7 步变成 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)。
给你三个整数 lo, hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ,如果大于等于 2 个整数有 相同 的权重,那么按照数字自身的数值 升序排序 。
请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。
注意,题目保证对于任意整数 x (lo <= x <= hi) ,它变成 1 所需要的步数是一个 32 位有符号整数。
示例:
输入:lo = 12, hi = 15, k = 2
输出:13
解释:12 的权重为 9(12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
13 的权重为 9
14 的权重为 17
15 的权重为 17
区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ,答案是第二个整数也就是 13 。
注意,12 和 13 有相同的权重,所以我们按照它们本身升序排序。14 和 15 同理。



本道题相对比较简单,主要考察数组的多条件排序。

第一步:按照规则计算整数的权重。

第二步:遍历区间,计算出所有整数的权重,按照规则进行多条件排序。




04
5351.3n块披萨



题目描述【Hard】


给你一个披萨,它由 3n 块不同大小的部分组成,现在你和你的朋友们需要按照如下规则来分披萨:
你挑选 任意 一块披萨。
Alice 将会挑选你所选择的披萨逆时针方向的下一块披萨。
Bob 将会挑选你所选择的披萨顺时针方向的下一块披萨。
重复上述过程直到没有披萨剩下。
每一块披萨的大小按顺时针方向由循环数组 slices 表示。
请你返回你可以获得的披萨大小总和的最大值。
示例:
输入:slices = [1,2,3,4,5,6]
输出:10
解释:选择大小为 4 的披萨,Alice 和 Bob 分别挑选大小为 3 和 5 的披萨。然后你选择大小为 6 的披萨,Alice 和 Bob 分别挑选大小为 2 和 1 的披萨。你获得的披萨总大小为 4 + 6 = 10 。



本道题是「 不连续子数列最大和问题 」的升级版。

对于不连续子数列的最大和问题,可以采用动态规划处理。

定义状态 dp[i][j]:表示前 i 块披萨中拿走 j 块所获取的最大和值。

对于任意 dp[i][j] 应该从以下两种情况中获取最大值(状态转移方程):

  • dp[i - 1][j]

  • dp[i - 2][j - 1] + slices[i]

而本道题的难点在于:这是一个环形数列,首尾是不能同时取的。

所以需要在原有的 DP 处理过程中区别数组的首尾元素不能同时取,即可解题。




05
往期精彩回顾









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