Leetcode - 双周赛153

一、3498. 字符串的反转度

题目连接

本题直接模拟，代码如下：

class Solution {public int reverseDegree(String s) {int ans = 0;for(int i = 0; i < s.length(); i++){int c = 'z' - s.charAt(i) + 1;ans += (i + 1) * c;}return ans;}
}

二、3499. 操作后最大活跃区段数 I

题目连接

本题就是一道阅读理解题，大概意思：至多执行一次操作，在一次操作中，可以将 0011100 这种把连续的 1 包围的 0 （左右两边都要有0）转换成 1，问最终 1 出现的最大次数。实际上就是计算操作一次最多可以将多少个 0 翻转成 1，而这就是计算相邻两段连续的 0 出现的最大次数，然后再加上原本 1 的个数就是答案。

代码如下：

class Solution {public int maxActiveSectionsAfterTrade(String s) {int n = s.length();int i = 0, ans = 0, mx = 0, pre = 0;while(i < n){while(i < n && s.charAt(i) == '1'){ans++;// 统计 1 出现的次数i++;}int j = i;// 记录 0 出现的位置while(i < n && s.charAt(i) == '0'){i++;}// 0: [j, i)// i - j 表示连续的 0 的出现次数 if(pre > 0 && i - j > 0){mx = Math.max(pre + i - j, mx); }pre = i - j; // 更新相邻 0 出现次数}return ans + mx;}
}

三、3500. 将数组分割为子数组的最小代价

题目连接

本题如果直接使用 dp 做的话，需要分别枚举 (l,r,i)，也就是说时间复杂度是O(n^3)的，这明显会超时，所以需要进行优化。

将代价公式进行优化：

• $(nums[0]+nums[1]+...+nums[r]+k\ast i)\ast (cost[l]+...+cost[r])$
• 用前缀和化简一下，得到：$(preN[r+1]+k\ast i)\ast (preC[r+1]-preC[l])$
• 明确 (l,r) 是不可能优化的，所以实际上就是如何把 i 给优化掉，公因式分解，得到：$preN[r+1]\ast (preC[r+1]-preC[l])+k\ast i\ast (preC[r+1]-preC[l])$
• 前一段已经没有i了，主要看 $k\ast i\ast (preC[r+1]-pre[l])$
• 假设 $nums$ 数组分成 $m$ 段，从前到后每一段的和依次为 {A,B,C,...,M}，将 k 提出来，剩下的和就变成了A + 2B + 3C + .... + mM，这时可以将其重新划分(A+...+M)+(B+...+M)+(C+...+M)+...+(M)，这样一看 i 就已经被等价成计算后缀和了，即 (preC[n]-preC[l1])+(preC[n]-preC[l2])+...
• 最终代价公式可以等价为 preN[r+1] * (preC[r+1] - preC[l]) + k * (preC[n] - preC[l])

此时在使用 dp 去计算，定义 f[i]: 以 i-1 结尾得到的最小总代价，对于 i 来说：

• 它可以从 i 之前任意一个状态转移过来，假设它从 f[j] 转移过来，转移方程就是 f[i] = max(f[i], f[j] + preN[i+1] * (preC[i+1] - preC[j]) + k * (preC[n] - preC[j]))

代码如下：

class Solution {public long minimumCost(int[] nums, int[] cost, int k) {int n = nums.length;long[] preN = new long[n + 1];long[] preC = new long[n + 1];for(int i = 0; i < n; i++){preN[i + 1] = preN[i] + nums[i];preC[i + 1] = preC[i] + cost[i];}long[] f = new long[n+1];//以 i-1 结尾的最小总代价Arrays.fill(f, Long.MAX_VALUE);f[0] = 0;//preN[r] * (preC[r] - preC[l]) + k * (preC[n] - pre[l])for(int i = 0; i < n; i++){for(int j = 0; j <= i; j++){f[i+1] = Math.min(f[i+1], f[j] + preN[i+1] * (preC[i+1] - preC[j]) + k * (preC[n] - preC[j]));}}return f[n];}
}

四、3501. 操作后最大活跃区段数 II

题目链接

本题是T2的进阶，变化的点在于本题限定了操作的范围，问每次查询只能操作 [L,R] 区间时，所能得到的最多 1 的个数，与 T2 的思路一致，还是计算出 [L,R] 区间相邻两段连续的 0 出现的最大次数，唯一的问题在于如何快速计算出相邻两段连续的 0 出现的最大次数

可以预处理相邻两段连续的 0 出现的次数，会出现以下三种情况：

对于情况一的第二种情况，就是维护一个区间最大值，可以使用 ST表 或者 线段树 去维护，对于第一/三种情况，可以手动计算。此时还有一个问题，需要找到 [L,R] 区间中最前/最后的完整的连续 0 段落，这可以使用二分来查找。

代码如下：

class Solution {private record Pair(int l, int r) { // 左闭右开}private static class SparseTable {private final int[][] st;SparseTable(List<Pair> a) {int n = a.size() - 1;int sz = 32 - Integer.numberOfLeadingZeros(n);// st[i][j]: 区间 [i, i+2^j) 的最大值 st = new int[n][sz];for (int i = 0; i < n; i++) {st[i][0] = a.get(i).r - a.get(i).l + a.get(i + 1).r - a.get(i + 1).l;}for (int j = 1; j < sz; j++) {for (int i = 0; i + (1 << j) <= n; i++) {st[i][j] = Math.max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);}}}// 查询区间最大值，[l,r) 左闭右开int query(int l, int r) {if (l >= r) {return 0;}int k = 32 - Integer.numberOfLeadingZeros(r - l) - 1;return Math.max(st[l][k], st[r - (1 << k)][k]);}}public List<Integer> maxActiveSectionsAfterTrade(String S, int[][] queries) {char[] s = S.toCharArray();int n = s.length;int total1 = 0;List<Pair> a = new ArrayList<>();a.add(new Pair(-1, -1)); // 哨兵int start = 0;for (int i = 0; i < n; i++) {if (i == n - 1 || s[i] != s[i + 1]) {if (s[i] == '1') {total1 += i - start + 1;} else {a.add(new Pair(start, i + 1)); // 左闭右开}start = i + 1;}}a.add(new Pair(n + 1, n + 1)); // 哨兵SparseTable st = new SparseTable(a);List<Integer> ans = new ArrayList<>(queries.length);for (int[] query : queries) {int ql = query[0];int qr = query[1] + 1; // 左闭右开// a 中没有重复的区间左右端点，可以直接用库函数二分// 找第一个区间，左端点 >= qlint i = Collections.binarySearch(a, new Pair(ql, 0), (p, q) -> p.l - q.l);if (i < 0) i = ~i;// 找最后一个区间，右端点 <= qrint j = Collections.binarySearch(a, new Pair(0, qr + 1), (p, q) -> p.r - q.r);if (j < 0) j = ~j;j--;int mx = 0;if (i <= j) { // [ql,qr) 中有完整的区间int full = st.query(i, j); // 相邻完整区间的长度之和的最大值int sl = merge(a.get(i - 1).r - ql, a.get(i).r - a.get(i).l);int sr = merge(qr - a.get(j + 1).l, a.get(j).r - a.get(j).l);mx = Math.max(full, Math.max(sl, sr));} else if (i == j + 1) {mx = merge(a.get(i - 1).r - ql, qr - a.get(j + 1).l);}ans.add(total1 + mx);}return ans;}private int merge(int x, int y) {return x > 0 && y > 0 ? x + y : 0;}
}