Solutions CS101

Appearance

第 446 场周赛-20250420 ​

https://leetcode.cn/contest/weekly-contest-446/

中国时间：2025-04-20 10:30, 1 小时 30 分

M3522.执行指令后的得分 ​

implementation, https://leetcode.cn/problems/calculate-score-after-performing-instructions/

M3523.非递减数组的最大长度 ​

greedy, monotonic stack, https://leetcode.cn/problems/make-array-non-decreasing/

M3524.求出数组X值I ​

dp, https://leetcode.cn/problems/find-x-value-of-array-i/

给你一个由 正 整数组成的数组 nums，以及一个 正 整数 k。

你可以对 nums 执行 一次 操作，该操作中可以移除任意 不重叠 的前缀和后缀，使得 nums 仍然 非空 。

你需要找出 nums 的 x 值，即在执行操作后，剩余元素的 乘积 除以 k 后的 余数 为 x 的操作数量。

返回一个大小为 k 的数组 result，其中 result[x] 表示对于 0 <= x <= k - 1，nums 的 x 值。

数组的 前缀 指从数组起始位置开始到数组中任意位置的一段连续子数组。

数组的 后缀 是指从数组中任意位置开始到数组末尾的一段连续子数组。

子数组 是数组中一段连续的元素序列。

注意，在操作中选择的前缀和后缀可以是 空的 。

示例 1：

输入： nums = [1,2,3,4,5], k = 3

输出： [9,2,4]

解释：

  • 对于 x = 0，可行的操作包括所有不会移除 nums[2] == 3 的前后缀移除方式。
  • 对于x = 1，可行操作包括：
    • 移除空前缀和后缀 [2, 3, 4, 5]，nums 变为 [1]。
    • 移除前缀 [1, 2, 3] 和后缀 [5]，nums 变为 [4]。
  • 对于x = 2，可行操作包括：
    • 移除空前缀和后缀 [3, 4, 5]，nums 变为 [1, 2]。
    • 移除前缀 [1] 和后缀 [3, 4, 5]，nums 变为 [2]。
    • 移除前缀 [1, 2, 3] 和空后缀，nums 变为 [4, 5]。
    • 移除前缀 [1, 2, 3, 4] 和空后缀，nums 变为 [5]。

示例 2：

输入： nums = [1,2,4,8,16,32], k = 4

输出： [18,1,2,0]

解释：

  • 对于x = 0，唯一 不 得到x = 0的操作有：
    • 移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
    • 移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
    • 移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
  • 对于x = 1，唯一的操作是：
    • 移除空前缀和后缀 [2, 4, 8, 16, 32]，nums 变为 [1]。
  • 对于x = 2，可行操作包括：
    • 移除空前缀和后缀 [4, 8, 16, 32]，nums 变为 [1, 2]。
    • 移除前缀 [1] 和后缀 [4, 8, 16, 32]，nums 变为 [2]。
  • 对于 x = 3，没有可行的操作。

示例 3：

输入： nums = [1,1,2,1,1], k = 2

输出： [9,6]

提示：

  • 1 <= nums[i] <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= k <= 5

Python code请嵌在这个代码中

python
class Solution:
    def resultArray(self, nums: List[int], k: int) -> List[int]:

T3525.出数组X值II ​

https://leetcode.cn/problems/find-x-value-of-array-ii/

给你一个由 正整数 组成的数组 nums 和一个 正整数 k。同时给你一个二维数组 queries，其中 queries[i] = [indexi, valuei, starti, xi]。

你可以对 nums 执行 一次 操作，移除 nums 的任意 后缀 ，使得 nums 仍然非空。

给定一个 x，nums 的 x值 定义为执行以上操作后剩余元素的 乘积 除以 k 的 余数 为 x 的方案数。

对于 queries 中的每个查询，你需要执行以下操作，然后确定 xi 对应的 nums 的 x值：

  • 将 nums[indexi] 更新为 valuei。仅这个更改在接下来的所有查询中保留。
  • 移除 前缀 nums[0..(starti - 1)]（nums[0..(-1)] 表示 空前缀 ）。

返回一个长度为 queries.length 的数组 result，其中 result[i] 是第 i 个查询的答案。

数组的一个 前缀 是从数组开始位置到任意位置的子数组。

数组的一个 后缀 是从数组中任意位置开始直到结束的子数组。

子数组 是数组中一段连续的元素序列。

注意：操作中所选的前缀或后缀可以是 空的 。

注意：x值在本题中与问题 I 有不同的定义。

示例 1：

输入： nums = [1,2,3,4,5], k = 3, queries = [[2,2,0,2],[3,3,3,0],[0,1,0,1]]

输出： [2,2,2]

解释：

  • 对于查询 0，nums变为[1, 2, 2, 4, 5]。移除空前缀后，可选操作包括：
    • 移除后缀 [2, 4, 5] ，nums 变为 [1, 2]。
    • 不移除任何后缀。nums 保持为 [1, 2, 2, 4, 5]，乘积为 80，对 3 取余为 2。
  • 对于查询 1，nums变为[1, 2, 2, 3, 5] 。移除前缀[1, 2, 2]后，可选操作包括：
    • 不移除任何后缀，nums 为 [3, 5]。
    • 移除后缀 [5] ，nums 为 [3]。
  • 对于查询 2，nums保持为[1, 2, 2, 3, 5]。移除空前缀后。可选操作包括：
    • 移除后缀 [2, 2, 3, 5]。nums 为 [1]。
    • 移除后缀 [3, 5]。nums 为 [1, 2, 2]。

示例 2：

输入： nums = [1,2,4,8,16,32], k = 4, queries = [[0,2,0,2],[0,2,0,1]]

输出： [1,0]

解释：

  • 对于查询 0，nums变为[2, 2, 4, 8, 16, 32]。唯一可行的操作是：
    • 移除后缀 [2, 4, 8, 16, 32]。
  • 对于查询 1，nums 仍为 [2, 2, 4, 8, 16, 32]。没有任何操作能使余数为 1。

示例 3：

输入： nums = [1,1,2,1,1], k = 2, queries = [[2,1,0,1]]

输出： [5]

提示：

  • 1 <= nums[i] <= 10^9
  • 1 <= nums.length <= 10^5
  • 1 <= k <= 5
  • 1 <= queries.length <= 2 * 10^4
  • queries[i] == [indexi, valuei, starti, xi]
  • 0 <= indexi <= nums.length - 1
  • 1 <= valuei <= 10^9
  • 0 <= starti <= nums.length - 1
  • 0 <= xi <= k - 1
python
class Solution:
    def resultArray(self, nums: List[int], k: int, queries: List[List[int]]) -> List[int]:©leetcode