欢迎大家加QQ群：623375442。还觉得这周挺难做的。后两题没啥提示根本想不出来。
100549. Calculate Score After Performing Instructions
给你两个数组：instructions 和 values，数组的长度均为 n。
你需要根据以下规则模拟一个过程：
- 从下标 i = 0 的第一个指令开始，初始得分为 0。
- 如果 instructions[i] 是 "add"：
- 将 values[i] 加到你的得分中。
- 移动到下一个指令 (i + 1)。
- 如果 instructions[i] 是 "jump"：
- 移动到下标为 (i + values[i]) 的指令，但不修改你的得分。
当以下任一情况发生时，过程会终止：
- 越界（即 i < 0 或 i >= n），或
- 尝试再次执行已经执行过的指令。被重复访问的指令不会再次执行。
返回过程结束时的得分。
测试样例：
输入：instructions = ["jump","add","add","jump","add","jump"], values = [2,1,3,1,-2,-3]
输出：1
解释：从下标 0 开始模拟过程：
- 下标 0：指令是 "jump"，移动到下标 0 + 2 = 2。
- 下标 2：指令是 "add"，将 values[2] = 3 加到得分中，移动到下标 3。得分变为 3。
- 下标 3：指令是 "jump"，移动到下标 3 + 1 = 4。
- 下标 4：指令是 "add"，将 values[4] = -2 加到得分中，移动到下标 5。得分变为 1。
- 下标 5：指令是 "jump"，移动到下标 5 + (-3) = 2。
- 下标 2：已经访问过。过程结束。
解答：本题等价于在一个指令数组上模拟执行“跳转”与“累加”操作。
- 用 pos 记录当前指令位置，用 res 累加加分；
- 用一个布尔数组 isVisit 防止重复执行同一条指令（可能出现死循环）；
- 遇到 "jump" 就修改 pos，遇到 "add" 就 res += value 并 pos++；
- 当 pos 越界或要执行的位置已经访问过时，停止模拟，返回 res。
时间 O(n)，空间 O(n)。
class Solution {
public long calculateScore(String[] instructions, int[] values) {
// res 用来累加“add”指令带来的分数
long res = 0;
// pos 表示当前要执行的指令下标，初始为 0
int pos = 0;
// isVisit[i] 标记下标 i 的指令是否已经执行过，防止死循环
boolean[] isVisit = new boolean[instructions.length];
// 只要 pos 在合法范围内且该指令未被执行过，就继续模拟
while (pos >= 0 && pos < instructions.length && !isVisit[pos]) {
// 标记当前指令已访问
isVisit[pos] = true;
// 如果是“jump”，跳转到 pos + values[pos]
if (instructions[pos].equals("jump")) {
pos += values[pos];
} else {
// 否则是“add”，累加分数，然后顺序执行下一条
res += values[pos];
pos += 1;
}
}
// 当越界或重复访问时，循环结束，返回累计得分
return res;
}
}
100554. Make Array Non-decreasing
给你一个整数数组 nums。在一次操作中，你可以选择一个子数组，并将其替换为一个等于该子数组 最大值 的单个元素。
返回经过零次或多次操作后，数组仍为 非递减 的情况下，数组 可能的最大长度。
子数组 是数组中一个连续、非空 的元素序列。
测试样例：
输入：nums = [4,2,5,3,5]
输出：3
解释: 实现最大长度的一种方法是：
- 将子数组 nums[1..2] = [2, 5] 替换为 5 → [4, 5, 3, 5]。
- 将子数组 nums[2..3] = [3, 5] 替换为 5 → [4, 5, 5]。
最终数组 [4, 5, 5] 是非递减的，长度为 3。
解答：每次操作可以将一段子数组替换成其中的最大值，以使数组非递减。
事实上，贪心地保留那些不小于此前所有元素的数，其他都可以合并成前面某个较大的数，不影响非递减性。
- 用 max 记录前缀最大值；
- 遍历 nums，遇到 nums[i] >= max 时就“留”住它，计数加 1；
- 否则这个位置可以合并到某个更大的数上，不计入最终长度。
时间 O(n)，空间 O(1)。
class Solution {
public int maximumPossibleSize(int[] nums) {
// max 记录到当前位置为止遇到的最大值
int max = -1;
// res 记录最终可以保留的元素个数
int res = 0;
for (int i = 0; i < nums.length; ++i) {
// 只有当当前元素 nums[i] >= max 时，才可以保留
if (nums[i] >= max) {
++res;
}
// 更新 max，为后面元素比较做准备
max = Math.max(max, nums[i]);
}
return res;
}
}
100634. Find X Value of Array I
给你一个由 正 整数组成的数组 nums，以及一个 正 整数 k。
你可以对 nums 执行 一次 操作，该操作中可以移除任意 不重叠 的前缀和后缀，使得 nums 仍然 非空 。
你需要找出 nums 的 x 值，即在执行操作后，剩余元素的 乘积 除以 k 后的 余数 为 x 的操作数量。
返回一个大小为 k 的数组 result，其中 result[x] 表示对于 0 <= x <= k - 1，nums 的 x 值。
数组的 前缀 指从数组起始位置开始到数组中任意位置的一段连续子数组。
数组的 后缀 是指从数组中任意位置开始到数组末尾的一段连续子数组。
子数组 是数组中一段连续的元素序列。
注意，在操作中选择的前缀和后缀可以是 空的 。
测试样例：
输入：nums = [1,2,3,4,5], k = 3
输出：3
解释:
- 对于 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]。
解答：本题要统计对原数组任意删除前缀／后缀后，剩余子数组乘积对 k 取余等于 x 的方案数。
- 先对整个 nums 建一棵线段树，每个节点存一个 Node：
- moduleResult 表示此区间所有元素乘积对 k 的余数；
- dp[a][b] 表示：如果入参乘积模为 a，经过该区间后变为 b 的删除后缀方案数。
- 区间合并时用“卷积”方式：左侧先从 pre → mid，右侧再从 mid → tar，二者累加。
- 最后枚举每个起点 i，当只保留后缀 [i..n-1] 时，查询线段树得到这一段的 Node，从初始模 1 到各模 x 的方案数即为 dp[1][x]。
- 循环累加得出长度为 k 的结果数组。
时间复杂度 O(n·k²·log n)，适合 k 较小的情况。
class Solution {
public long[] resultArray(int[] nums, int k) {
// 构建一个支持区间合并和查询的线段树
SegmentTree tree = new SegmentTree(nums, k);
long[] res = new long[k];
// 枚举每个可能的前缀起点 i，表示我们只保留 [i..n-1] 这一段
for (int i = 0; i < nums.length; ++i) {
// 查询从 i 到末尾这一段的 Node（包含 dp 信息）
Node node = tree.query(1, 0, nums.length - 1, i, nums.length - 1);
// 累加：从初始模 1（空乘积）到各个 x 的转移数
for (int x = 0; x < k; ++x) {
res[x] += node.dp[1 % k][x];
}
}
return res;
}
}
// 存储一个区间内的模运算统计信息
class Node {
// 该区间所有元素乘积对 k 的余数
int moduleResult;
// dp[a][b] = “在此区间内，从前缀乘积模 a 变到模 b 的方案数”
int[][] dp;
Node(int k) {
dp = new int[k][k];
}
}
class SegmentTree {
int k;
int[] arr;
Node[] segTree;
// 空区间对应的 Node：模结果 1，且无转移
Node empty;
public SegmentTree(int[] nums, int k) {
int n = nums.length;
this.arr = nums;
this.k = k;
empty = new Node(k);
empty.moduleResult = 1 % k;
// 先算出线段树数组大小，然后 build
segTree = new Node[4 * n];
build(1, 0, n - 1);
}
// 递归建树
private void build(int idx, int l, int r) {
if (l == r) {
// 叶节点：只有一个元素
Node node = new Node(k);
node.moduleResult = arr[l] % k;
// 统计 preMod -> curMod 的方案数
for (int pre = 0; pre < k; ++pre) {
int cur = (pre * node.moduleResult) % k;
node.dp[pre][cur] = 1;
}
segTree[idx] = node;
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
// 合并左右子区间
segTree[idx] = combine(segTree[idx << 1], segTree[idx << 1 | 1]);
}
// 区间合并：卷积思想
private Node combine(Node left, Node right) {
Node res = new Node(k);
// 合并后的整体乘积余数
res.moduleResult = (left.moduleResult * right.moduleResult) % k;
// 对所有可能的前缀模 pre 和目标模 tar
for (int pre = 0; pre < k; ++pre) {
for (int tar = 0; tar < k; ++tar) {
// 要么在左侧就完成从 pre->tar
int cnt = left.dp[pre][tar];
// 要么先到左侧结束时的某个 mid，再由右侧把 mid->tar
int midMod = (pre * left.moduleResult) % k;
cnt += right.dp[midMod][tar];
res.dp[pre][tar] = cnt;
}
}
return res;
}
// 区间查询
public Node query(int idx, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return empty;
if (ql <= l && r <= qr) return segTree[idx];
int mid = (l + r) >> 1;
Node left = query(idx << 1, l, mid, ql, qr);
Node right = query(idx << 1 | 1, mid + 1, r, ql, qr);
return combine(left, right);
}
}
100634. Find X Value of Array I
给你一个由 正整数 组成的数组 nums 和一个 正整数 k。同时给你一个二维数组 queries，其中 queries[i] = [indexi, valuei, starti, xi]。
你可以对 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 有不同的定义。
测试样例：
输入：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]。
解答：此题在 I 题的基础上增加了多次“点更新”与查询：
- 维护同样的线段树结构，支持 update（单点重建）与 query；
- 对每个查询，先把 nums[index] 更新为新值，再针对后缀 [start..n-1] 做一次和 I 题相同的 dp 查询，取 dp[1][x]；
- 汇总每次查询结果即可。
复杂度：每次更新与查询各 O(log n·k²)，总共 O(q·log n·k²)。适合 n, q ≤ 10⁵ 且 k 较小的场景。
class Solution {
class Node {
int moduleResult;
int[][] dp;
Node(int k) { dp = new int[k][k]; }
}
class SegmentTree {
int k, n;
int[] arr;
Node[] segTree;
Node empty;
public SegmentTree(int[] nums, int k) {
this.n = nums.length;
this.arr = nums;
this.k = k;
empty = new Node(k);
empty.moduleResult = 1 % k;
segTree = new Node[4 * n];
build(1, 0, n - 1);
}
private void build(int idx, int l, int r) {
if (l == r) {
Node node = new Node(k);
node.moduleResult = arr[l] % k;
for (int pre = 0; pre < k; ++pre) {
int cur = (pre * node.moduleResult) % k;
node.dp[pre][cur] = 1;
}
segTree[idx] = node;
return;
}
int mid = (l + r) >> 1;
build(idx << 1, l, mid);
build(idx << 1 | 1, mid + 1, r);
segTree[idx] = combine(segTree[idx << 1], segTree[idx << 1 | 1]);
}
private Node combine(Node left, Node right) {
Node res = new Node(k);
res.moduleResult = (left.moduleResult * right.moduleResult) % k;
for (int pre = 0; pre < k; ++pre) {
for (int tar = 0; tar < k; ++tar) {
int cnt = left.dp[pre][tar];
int midMod = (pre * left.moduleResult) % k;
cnt += right.dp[midMod][tar];
res.dp[pre][tar] = cnt;
}
}
return res;
}
// 点更新：将 arr[pos] 改为 val，然后自底向上重建节点
public void update(int idx, int l, int r, int pos, int val) {
if (l == r) {
arr[pos] = val;
Node node = new Node(k);
node.moduleResult = val % k;
for (int pre = 0; pre < k; ++pre) {
int cur = (pre * node.moduleResult) % k;
node.dp[pre][cur] = 1;
}
segTree[idx] = node;
return;
}
int mid = (l + r) >> 1;
if (pos <= mid) update(idx << 1, l, mid, pos, val);
else update(idx << 1 | 1, mid + 1, r, pos, val);
segTree[idx] = combine(segTree[idx << 1], segTree[idx << 1 | 1]);
}
// 区间查询，与 I 题相同
public Node query(int idx, int l, int r, int ql, int qr) {
if (ql > r || qr < l) return empty;
if (ql <= l && r <= qr) return segTree[idx];
int mid = (l + r) >> 1;
Node left = query(idx << 1, l, mid, ql, qr);
Node right = query(idx << 1 | 1, mid + 1, r, ql, qr);
return combine(left, right);
}
}
public int[] resultArray(int[] nums, int k, int[][] queries) {
int n = nums.length;
SegmentTree tree = new SegmentTree(nums, k);
int[] res = new int[queries.length];
// 逐条执行更新 + 查询
for (int i = 0; i < queries.length; i++) {
int idx = queries[i][0], val = queries[i][1];
int start = queries[i][2], x = queries[i][3];
// 先更新 nums[idx] = val
tree.update(1, 0, n - 1, idx, val);
// 再查询区间 [start..n-1]，统计从模 1 到模 x 的方案数
Node node = tree.query(1, 0, n - 1, start, n - 1);
res[i] = node.dp[1 % k][x];
}
return res;
}
}