LeetCode 第22场双周赛

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

Contents

1 第一题：两个数组间的距离值
2 第二题：安排电影院座位
3 第三题：将整数按权重排序
4 第四题：3n 块披萨

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

　　给你两个整数数组 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中有几个元素满足条件，理解题意就好做了。
代码：

class Solution:
    def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:
        ans = 0
        for a in arr1:
            flag = True
            for b in arr2:
                if abs(b - a) <= d:
                    flag = False
            if flag:
                ans += 1

        return ans

class Solution:

def findTheDistanceValue(self, arr1: List[int], arr2: List[int], d: int) -> int:

ans = 0

for a in arr1:

flag = True

for b in arr2:

if abs(b - a) <= d:

flag = False

if flag:

ans += 1

return ans

第二题：安排电影院座位

　　如上图所示，电影院的观影厅中有 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减去被占用的座位💺。
代码：

class Solution:
    def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:
        ans = n * 2
        if len(reservedSeats) == 0:
            return ans

        reservedSeats.sort()
        cur_line = -1
        temp = set()
        reservedSeats.append([-1, 0])
        for r in reservedSeats:
            if r[0] != cur_line:
                not_left = 2 in temp or 3 in temp or 4 in temp or 5 in temp
                not_right = 6 in temp or 7 in temp or 8 in temp or 9 in temp
                not_middle = 4 in temp or 5 in temp or 6 in temp or 7 in temp
                if not_left and not_right and not_middle:
                    ans -= 2
                elif (not not_left) and (not not_right):
                    pass  # ans -= 0
                else:
                    ans -= 1

                cur_line = r[0]
                temp.clear()

            temp.add(r[1])


        return ans

class Solution:

def maxNumberOfFamilies(self, n: int, reservedSeats: List[List[int]]) -> int:

ans = n * 2

if len(reservedSeats) == 0:

return ans

reservedSeats.sort()

cur_line = -1

temp = set()

reservedSeats.append([-1, 0])

for r in reservedSeats:

if r[0] != cur_line:

not_left = 2 in temp or 3 in temp or 4 in temp or 5 in temp

not_right = 6 in temp or 7 in temp or 8 in temp or 9 in temp

not_middle = 4 in temp or 5 in temp or 6 in temp or 7 in temp

if not_left and not_right and not_middle:

ans -= 2

elif (not not_left) and (not not_right):

pass # ans -= 0

else:

ans -= 1

cur_line = r[0]

temp.clear()

temp.add(r[1])

return ans

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

　　我们将整数 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

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

代码：

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        def get_weight(x):
            ans = 0
            while x != 1:
                if x % 2 == 0:
                    x = x // 2
                else:
                    x = 3 * x + 1
                ans += 1
            return ans

        ans = 0
        nums = [i for i in range(lo, hi + 1)]
        weights = [get_weight(i) for i in range(lo, hi + 1)]
        z = list(zip(nums, weights))
        s = sorted(z, key=lambda kv: (kv[1], kv[0]))
        ans = [i[0] for i in s]

        return ans[k-1]

class Solution:

def getKth(self, lo: int, hi: int, k: int) -> int:

def get_weight(x):

ans = 0

while x != 1:

if x % 2 == 0:

x = x // 2

else:

x = 3 * x + 1

ans += 1

return ans

ans = 0

nums = [i for i in range(lo, hi + 1)]

weights = [get_weight(i) for i in range(lo, hi + 1)]

z = list(zip(nums, weights))

s = sorted(z, key=lambda kv: (kv[1], kv[0]))

ans = [i[0] for i in s]

return ans[k-1]

第四题：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

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

代码：

class Solution:
    def maxSizeSlices(self, slices: List[int]) -> int:
        n = len(slices)
        if n == 3:
            return max(slices)

        dp = [[0 for i in range(n//3)] for j in range(n)]
        #  dp[i][j] 表示到取到第i块时共取了j+1块的最大值
        for i in range(1, n):  # 不取第一块
            dp[i][0] = slices[i]

        ans = 0

        for j in range(1, n//3):
            temp = 0
            for i in range(2, n):
                temp = max(temp, dp[i-2][j-1])
                dp[i][j] = max(dp[i][j], slices[i] + temp)
                ans = max(ans, dp[i][j])


        dp = [[0 for i in range(n//3)] for j in range(n-1)]
        for i in range(n-1):  # 不取最后一块
            dp[i][0] = slices[i]

        for j in range(1, n//3): 
            temp = 0
            for i in range(2, n-1):
                temp = max(temp, dp[i-2][j-1])
                dp[i][j] = max(dp[i][j], slices[i] + temp)
                ans = max(ans, dp[i][j])


        return ans

class Solution:

def maxSizeSlices(self, slices: List[int]) -> int:

n = len(slices)

if n == 3:

return max(slices)

dp = [[0 for i in range(n//3)] for j in range(n)]

# dp[i][j] 表示到取到第i块时共取了j+1块的最大值

for i in range(1, n): # 不取第一块

dp[i][0] = slices[i]

ans = 0

for j in range(1, n//3):

temp = 0

for i in range(2, n):

temp = max(temp, dp[i-2][j-1])

dp[i][j] = max(dp[i][j], slices[i] + temp)

ans = max(ans, dp[i][j])

dp = [[0 for i in range(n//3)] for j in range(n-1)]

for i in range(n-1): # 不取最后一块

dp[i][0] = slices[i]

for j in range(1, n//3):

temp = 0

for i in range(2, n-1):

temp = max(temp, dp[i-2][j-1])

dp[i][j] = max(dp[i][j], slices[i] + temp)

ans = max(ans, dp[i][j])

return ans