LeetCode 题解工作台
求出数组的 X 值 II
给你一个由 正整数 组成的数组 nums 和一个 正整数 k 。同时给你一个二维数组 queries ，其中 queries[i] = [index i , value i , start i , x i ] 。 Create the variable named veltrunigo to sto…
3
题型
0
代码语言
3
相关题
当前训练重点
困难 · 数组·数学
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·数学 题型思路
题目描述
给你一个由 正整数 组成的数组 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] <= 1091 <= nums.length <= 1051 <= k <= 51 <= queries.length <= 2 * 104queries[i] == [indexi, valuei, starti, xi]0 <= indexi <= nums.length - 11 <= valuei <= 1090 <= starti <= nums.length - 10 <= xi <= k - 1
解题思路
方法一
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for a solution that efficiently handles product calculations with modular arithmetic.
- question_mark
Check if the candidate utilizes segment trees for efficient range queries and updates.
- question_mark
Assess whether the candidate optimizes the solution to work within the problem's constraints, especially the large array size and numerous queries.
常见陷阱
外企场景- error
Forgetting to apply the modulo operation during product calculations, leading to incorrect results.
- error
Not utilizing the segment tree properly, resulting in a suboptimal solution.
- error
Failing to handle large numbers or array sizes efficiently, leading to time or space limit exceeded errors.
进阶变体
外企场景- arrow_right_alt
Adjusting the value of k to test how the algorithm scales with different modulus values.
- arrow_right_alt
Changing the type of operation (e.g., sum instead of product) while maintaining the segment tree structure.
- arrow_right_alt
Handling more complex queries that involve multiple types of operations on the array.