Leetcode - 周赛446

一、3522. 执行指令后的得分

题目链接

本题就是一道模拟题，代码如下：

class Solution {public long calculateScore(String[] in, int[] v) {long ans = 0;int i = 0;int n = in.length;boolean[] vis = new boolean[n];while(i >= 0 && i < n && !vis[i]){vis[i] = true;if(in[i].charAt(0) == 'a'){ans += v[i++];}else{i += v[i];}}return ans;}
}

二、3523. 非递减数组的最大长度

题目链接

本题是一道贪心题，由于题目允许将子数组替换成该子数组的最大元素，求最长非递减的长度，这就变相的说明了需要保留尽可能多的较大值，分类讨论：

• 对于第一个元素来说，它必须保留，因为如果执行操作，就必须向后找到一个大于等于它的元素，如果存在该元素，那么不如选择不操作，这样就能获得长度为 2 的非递减数组
• 对于其他元素，贪心的想，从前往后遍历，只要一遇到大于等于 mx 的数，立即更新 mx 和 长度。这样能给后续留下更多的元素，就更可能出现更长的非递减数组。

代码如下：

class Solution {public int maximumPossibleSize(int[] nums) {int ans = 0;int mx = 0;// 有点类似于求前缀最大值的更新次数（只不过==也算更新）for(int x : nums){if(x >= mx){ans++;mx = x;}}return ans;}
}

三、3524. 求出数组的 X 值 I

题目链接

本题题意就是问，对于 数组nums 的所有子数组来说，他们的乘积 %k = {0,1,...,k-1} 分别有多少种情况。定义 f[i+1][j]：右端点为 i，且它们的乘积 %k = j 的子数组个数，对于 x = nums[i] 来说：

• 须知：(a * b) % k = ((a % k) * (b % k)) % k
• 选择以 i-1 结尾的子数组，需要枚举f[i][j], j = %k = {0,1,...,k-1}，f[i+1][x*j%k] += f[i][j]
• 不选以 i-1 结尾的任意子数组，即只包含x，那么 f[i+1][x%k]++

代码如下：

class Solution {public long[] resultArray(int[] nums, int k) {long[] res = new long[k];int n = nums.length;long[][] f = new long[n+1][k];//f[i][j]: 以 i-1 为右端点时，%k=j 的子数组个数// x * ? % k = j, ？是难以计算的// ? = x * j % k, ？是可以直接计算的for(int i = 0; i < n; i++){int x = nums[i] % k;f[i+1][x] = 1;for(int j = 0; j < k; j++){f[i+1][j*x%k] += f[i][j];}for(int j = 0; j < k; j++){res[j] += f[i+1][j];}}return res;}
}

四、3525. 求出数组的 X 值 II

题目链接

本题与T3类似，区别在于本题有修改操作，且每次查询的子数组的左端点是确定的，问每次查询mod k = queries[i][3] 的子数组个数。单点修改，区间查询可以使用线段树做。需要维护两个东西，一个是[l,r] 的区间乘积，一个是以 l 为左端点的所有子数组乘积mod k的情况。

代码如下：

class SegmentTree{int[][] tree;int k;public SegmentTree(int[] nums, int k){this.k = k;int n = nums.length;tree = new int[n<<2][k+1];build(1, 0, n-1, nums);}void build(int i, int l, int r, int[] a){if(l == r){tree[i][k] = a[l] % k;tree[i][a[l]%k] = 1;return;}int mid = (l + r) >>> 1;build(i<<1, l, mid, a);build(i<<1|1, mid+1, r, a);tree[i] = merge(tree[i<<1], tree[i<<1|1]);}// 合并int[] merge(int[] a, int[] b){int[] ans = a.clone();ans[k] = a[k] * b[k] % k;// 区间乘积 mod kint x = a[k];// 更新以 l 为左端点的子数组 mod k 的情况for(int i = 0; i < k; i++){ans[x * i % k] += b[i];}return ans;}// 单点更新void update(int i, int l, int r, int j, int val){if(l == r){Arrays.fill(tree[i], 0);// 复原tree[i][k] = val % k;tree[i][val%k] = 1;return;}int mid = (l + r) >>> 1;if(j <= mid){update(i<<1, l, mid, j, val);}else{update(i<<1|1, mid+1, r, j, val);}tree[i] = merge(tree[i<<1], tree[i<<1|1]);}// 区间查询int[] query(int i, int l, int r, int jobL, int jobR){if(jobL <= l && r <= jobR){return tree[i];}int mid = (l + r) >>> 1;if(jobR <= mid){return query(i<<1, l, mid, jobL, jobR);}if(mid < jobL){return query(i<<1|1, mid+1, r, jobL, jobR);}return merge(query(i<<1, l, mid, jobL, jobR), query(i<<1|1, mid+1, r, jobL, jobR));}
}
class Solution {public int[] resultArray(int[] nums, int k, int[][] queries) {SegmentTree t = new SegmentTree(nums, k);int n = nums.length;int m = queries.length;int[] ans = new int[m];for(int i = 0; i < m; i++){int[] q = queries[i];t.update(1, 0, n-1, q[0], q[1]);int[] res = t.query(1, 0, n-1, q[2], n-1);ans[i] = res[q[3]];}return ans;}
}