LeetCode 第22场双周赛

分披萨🍕目瞪口呆👀了半小时。。。

第一题:两个数组间的距离值

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

思路:
  就是求arr1中有几个元素满足条件,理解题意就好做了。
代码:

第二题:安排电影院座位

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

  提示:   1 <= n <= 10^9
  1 <= reservedSeats.length <= min(10*n, 10^4)
  reservedSeats[i].length == 2
  1 <= reservedSeats[i][0] <= n
  1 <= reservedSeats[i][1] <= 10
  所有 reservedSeats[i] 都是互不相同的。

思路:
  题目本身不难,但是要注意到有一个9次方的数据量。因此使用n×4减去被占用的座位💺。
代码:

第三题:将整数按权重排序

  我们将整数 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 位有符号整数。
  
  
  示例 1:
  输入: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 同理。
  
  示例 2:
  输入:lo = 1, hi = 1, k = 1
  输出:1
  
  示例 3:
  输入:lo = 7, hi = 11, k = 4
  输出:7
  解释:区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
  按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
  排序后数组中第 4 个数字为 7 。
  
  示例 4:
  输入:lo = 10, hi = 20, k = 5
  输出:13
  
  示例 5:
  输入:lo = 1, hi = 1000, k = 777
  输出:570

思路:
  题目数据量不大,全部计算出权重后按主次关键词排序。

代码:

第四题:3n 块披萨

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

思路:
  实际上不管AliceBob如何选,只要你不选相邻的比萨,所有的组合你都能选到。
  动态规划。令dp[i][j]表示到取到第i块时共取了j块的最大值。则dp[i][j]= max(dp[0:i-2][j-1])。
  由于整块披萨是环形的,取了第一块就不能取最后一块。因此把不取第一块不取最后一块分别拿出来讨论。

代码:

发表评论

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