第 151 场双周赛-20250301
https://leetcode.cn/contest/biweekly-contest-151/
中国时间：2025-03-01 22:30, 1 小时 30 分
3467. 将数组按照奇偶性转化
https://leetcode.cn/problems/transform-array-by-parity/description/
给你一个整数数组 nums。请你按照以下顺序 依次 执行操作，转换 nums：
- 将每个偶数替换为 0。
- 将每个奇数替换为 1。
- 按 非递减 顺序排序修改后的数组。
执行完这些操作后，返回结果数组。
示例 1:
输入：nums = [4,3,2,1]
输出：[0,0,1,1]
解释：
- 将偶数（4 和 2）替换为 0，将奇数（3 和 1）替换为 1。现在，
nums = [0, 1, 0, 1]。 - 按非递减顺序排序
nums，得到nums = [0, 0, 1, 1]。
示例 2:
输入：nums = [1,5,1,4,2]
输出：[0,0,1,1,1]
解释：
- 将偶数（4 和 2）替换为 0，将奇数（1, 5 和 1）替换为 1。现在，
nums = [1, 1, 1, 0, 0]。 - 按非递减顺序排序
nums，得到nums = [0, 0, 1, 1, 1]。
提示：
1 <= nums.length <= 1001 <= nums[i] <= 1000
from typing import List
class Solution:
def transformArray(self, nums: List[int]) -> List[int]:
for i in range(len(nums)):
if nums[i] & 1:
nums[i] = 1
else:
nums[i] = 0
nums.sort()
return nums
if __name__ == "__main__":
sol = Solution()
nums = [0,1,2,3,4,5,6,7,8,9]
print(sol.transformArray(nums))
print(sol.transformArray([1,5,1,4,2]))Q2. 可行数组的数目
https://leetcode.cn/contest/biweekly-contest-151/problems/find-the-number-of-copy-arrays/
给你一个长度为 n 的数组 original 和一个长度为 n x 2 的二维数组 bounds，其中 bounds[i] = [ui, vi]。
你需要找到长度为 n 且满足以下条件的 可能的 数组 copy 的数量：
- 对于
1 <= i <= n - 1，都有(copy[i] - copy[i - 1]) == (original[i] - original[i - 1])。 - 对于
0 <= i <= n - 1，都有ui <= copy[i] <= vi。
返回满足这些条件的数组数目。
示例 1
输入：original = [1,2,3,4], bounds = [[1,2],[2,3],[3,4],[4,5]]
输出：2
解释：
可能的数组为：
[1, 2, 3, 4][2, 3, 4, 5]
示例 2
输入：original = [1,2,3,4], bounds = [[1,10],[2,9],[3,8],[4,7]]
输出：4
解释：
可能的数组为：
[1, 2, 3, 4][2, 3, 4, 5][3, 4, 5, 6][4, 5, 6, 7]
示例 3
输入：original = [1,2,1,2], bounds = [[1,1],[2,3],[3,3],[2,3]]
输出：0
解释：
没有可行的数组。
提示：
2 <= n == original.length <= 10^51 <= original[i] <= 10^9bounds.length == nbounds[i].length == 21 <= bounds[i][0] <= bounds[i][1] <= 10^9
from typing import List
class Solution:
def countArrays(self, original: List[int], bounds: List[List[int]]) -> int:
n = len(original)
# Difference between consecutive elements in the original array
diffs = [original[i] - original[i - 1] for i in range(1, n)]
# Initialize valid range for copy[0]
min_val, max_val = bounds[0]
for i in range(1, n):
diff = diffs[i - 1]
# Update bounds for next element in copy based on the previous bounds and the diff
min_val = max(min_val + diff, bounds[i][0])
max_val = min(max_val + diff, bounds[i][1])
# If bounds become invalid, no valid array is possible
if min_val > max_val:
return 0
# Number of possible arrays is the size of the final valid range
# 如果所有元素的取值范围都是有效的（即没有出现min_val > max_val的情况），
# 则满足条件的数组数量等于最后一个元素的取值范围大小，
return max_val - min_val + 1
if __name__ == "__main__":
sol = Solution()
original = [1, 2, 3, 4]
bounds = [[1, 2], [2, 3], [3, 4], [4, 5]]
print(sol.countArrays(original, bounds)) # Output: 2
original = [1, 2, 3, 4]
bounds = [[1, 10], [2, 9], [3, 8], [4, 7]]
print(sol.countArrays(original, bounds)) # Output: 4
original = [1, 2, 1, 2]
bounds = [[1, 1], [2, 3], [3, 3], [2, 3]]
print(sol.countArrays(original, bounds)) # Output: 0Q3.移除所有数组的最小代价
给你一个整数数组 nums。你的任务是在每一步中执行以下操作之一，直到 nums 为空，从而移除 所有元素 ：
- 从
nums的前三个元素中选择任意两个元素并移除它们。此操作的成本为移除的两个元素中的 最大值 。 - 如果
nums中剩下的元素少于三个，则一次性移除所有剩余元素。此操作的成本为剩余元素中的 最大值 。
返回移除所有元素所需的最小成本。
示例 1
输入：nums = [6,2,8,4]
输出：12
解释：
初始时，nums = [6, 2, 8, 4]。
- 在第一次操作中，移除
nums[0] = 6和nums[2] = 8，操作成本为max(6, 8) = 8。现在，nums = [2, 4]。 - 在第二次操作中，移除剩余元素，操作成本为
max(2, 4) = 4。
移除所有元素的成本为 8 + 4 = 12。这是移除 nums 中所有元素的最小成本。所以输出 12。
示例 2
输入：nums = [2,1,3,3]
输出：5
解释：
初始时，nums = [2, 1, 3, 3]。
- 在第一次操作中，移除
nums[0] = 2和nums[1] = 1，操作成本为max(2, 1) = 2。现在，nums = [3, 3]。 - 在第二次操作中，移除剩余元素，操作成本为
max(3, 3) = 3。
移除所有元素的成本为 2 + 3 = 5。这是移除 nums 中所有元素的最小成本。因此，输出是 5。
提示：
1 <= nums.length <= 10001 <= nums[i] <= 10^6
思路是：
定义状态为
dp(i, carry)，其中i表示原数组中还未使用的起始位置，carry是一个元组，代表前一步操作留下的“剩余”元素（最多 1 个在非终止状态，但终止状态下可能为 2 个）。每次从当前状态构造出 “可选组” 即
available = list(carry) + nums[i:i+needed]，保证其长度恰好为 3。当可用元素不足 3 时（即状态终止），直接返回这些元素的最大值（代表一次性移除它们的成本）。当有 3 个元素时，我们可以有 3 种选择：
- 移除前 2 个，成本为
max(a, b)，新状态为剩下的第三个元素加上后续未处理的部分。 - 移除第 1 个和第 3 个，成本为
max(a, c)，新状态为[b]加上后续。 - 移除第 2 个和第 3 个，成本为
max(b, c)，新状态为[a]加上后续。
- 移除前 2 个，成本为
最终返回所有操作的最小累计成本。
from typing import List
from functools import lru_cache
class Solution:
def minCost(self, nums: List[int]) -> int:
n = len(nums)
@lru_cache(maxsize=None)
def dp(i, carry):
"""
i: 当前在 nums 中还未使用的起始索引
carry: 元组，表示上一步留下的剩余元素（顺序不能改变）
"""
# 构造当前可用序列（carry 后跟 nums[i:]中的前几个元素）
available = list(carry)
needed = 3 - len(available) # 补满 3 个元素需要从 nums 中取多少个
# 如果不足 3 个，则进行一次性移除，成本为可用元素的最大值
if i + needed > n:
if available or i < n:
return max(available + nums[i:]) # 若非空，返回最大值
else:
return 0
# 否则，补全 3 个元素
available.extend(nums[i:i + needed])
a, b, c = available[0], available[1], available[2]
ans = float('inf')
# 情况1：移除 a 和 b，成本为 max(a, b)，剩余元素为 c
ans = min(ans, max(a, b) + dp(i + needed, (c,)))
# 情况2：移除 a 和 c，成本为 max(a, c)，剩余元素为 b
ans = min(ans, max(a, c) + dp(i + needed, (b,)))
# 情况3：移除 b 和 c，成本为 max(b, c)，剩余元素为 a
ans = min(ans, max(b, c) + dp(i + needed, (a,)))
return ans
return dp(0, ())
if __name__ == "__main__":
sol = Solution()
print(sol.minCost([6, 2, 8, 4])) # Output: 4
print(sol.minCost([2, 1, 3, 3])) # Output: 5
print(sol.minCost([9, 1, 5])) #Q4.排列IV
https://leetcode.cn/contest/biweekly-contest-151/problems/permutations-iv/
给你两个整数 n 和 k，一个 交替排列 是前 n 个正整数的排列，且任意相邻 两个 元素不都为奇数或都为偶数。
返回第 k 个 交替排列 ，并按 字典序 排序。如果有效的 交替排列 少于 k 个，则返回一个空列表。
示例 1
输入：n = 4, k = 6
输出：[3,4,1,2]
解释：
[1, 2, 3, 4] 的交替排列按字典序排序后为：
[1, 2, 3, 4][1, 4, 3, 2][2, 1, 4, 3][2, 3, 4, 1][3, 2, 1, 4][3, 4, 1, 2]← 第 6 个排列[4, 1, 2, 3][4, 3, 2, 1]
由于 k = 6，我们返回 [3, 4, 1, 2]。
示例 2
输入：n = 3, k = 2
输出：[3,2,1]
解释：
[1, 2, 3] 的交替排列按字典序排序后为：
[1, 2, 3][3, 2, 1]← 第 2 个排列
由于 k = 2，我们返回 [3, 2, 1]。
示例 3
输入：n = 2, k = 3
输出：[]
解释：
[1, 2] 的交替排列按字典序排序后为：
[1, 2][2, 1]
只有 2 个交替排列，但 k = 3 超出了范围。因此，我们返回一个空列表 []。
提示：
1 <= n <= 1001 <= k <= 10^15