Leetcode - 周赛425
目录
一，3364. 最小正和子数组
二， 3365. 重排子字符串以形成目标字符串
三，3366. 最小数组和
四，3367. 移除边之后的权重最大和
一，3364. 最小正和子数组
本题可以直接暴力枚举，代码如下：
class Solution {
public int minimumSumSubarray(List<Integer> nums, int l, int r) {
int n = nums.size();
int ans = Integer.MAX_VALUE;
for(int k=l; k<=r; k++){
int s = 0;
for(int i=0, j=0; j<n; j++){
s += nums.get(j);
if(j-i+1 > k){
s -= nums.get(i);
i++;
}
if(j-i+1 == k && s > 0) ans = Math.min(ans, s);
}
}
return ans==Integer.MAX_VALUE ? -1 : ans;
}
}如果它的数据范围更大一点，上述做法会超时，所以这里再介绍一个O(n*logn)的做法：
- 这题求子数组和的最小正值，子数组和可以直接使用前缀和来求
- 题目要求子数组的长度在 [L，R] 之间，可以枚举左端点 / 右端点，这里选择枚举右端点下标 i，再根据上述条件直接推出左端点的下标 j 的范围 [i-R，i-L]
- 假设前缀和数组为 s，此时 si 是固定的，要使得 si - sj 的值更大，sj 必须是小于 si 的最大值（题目要求为正数），求 sj < si 的最大值且 j 属于 [i-R，i-L]，这可以使用有序集合+二分来做
代码如下：
class Solution {
public int minimumSumSubarray(List<Integer> nums, int l, int r) {
int n = nums.size();
int ans = Integer.MAX_VALUE;
int[] pre = new int[n+1];
for(int i=0; i<n; i++){
pre[i+1] = pre[i] + nums.get(i);
}
//枚举右端点：[i-r, i-l] ~ i
//s[i-r, i-l] < si, 二分枚举最接近si的值
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int i=l, j=0; i<=n; i++){
map.merge(pre[i-l], 1, Integer::sum);
// 错误写法：
// 当l==r时，会出错（没有计算当前子数组的大小）
// if(i-r > 0){
// map.merge(pre[i-r], -1, Integer::sum);
// if(map.get(pre[i-r])==0) map.remove(pre[i-r]);
// }
Integer res = map.lowerKey(pre[i]);
if(res != null)
ans = Math.min(ans, pre[i]-res);
if(i-r >= 0){
map.merge(pre[i-r], -1, Integer::sum);
if(map.get(pre[i-r])==0) map.remove(pre[i-r]);
}
}
return ans == Integer.MAX_VALUE ? -1 : ans;
}
}二， 3365. 重排子字符串以形成目标字符串
本题直接暴力哈希，使用哈希表统计字符串 s 中分割成 k 个等长的子字符串，再看 t 中分割出的 k 个等长子字符串是否与字符串 s 完全相同。
代码如下：
class Solution {
public boolean isPossibleToRearrange(String s, String t, int k) {
Map<String, Integer> map = new HashMap<>();
int n = s.length();
for(int i=n/k; i<=n; i+=n/k){
map.merge(s.substring(i-n/k, i), 1, Integer::sum);
}
for(int i=n/k; i<=n; i+=n/k){
String x = t.substring(i-n/k, i);
map.merge(x, -1, Integer::sum);
if(map.get(x) == 0) map.remove(x);
if(map.getOrDefault(x, 0) < 0) return false;
}
return map.size() == 0;
}
}三，3366. 最小数组和
本题数据范围较小，直接使用dp暴力求解，先找与原问题相同的子问题，从前往后遍历，对于第 i 个数来说：
- 不执行任何操作，剩下变成求 [i+1，n] 这些数进行 x 次操作1，y 次操作2后的最小元素和
- 执行操作1，剩下变成求 [i+1，n] 这些数进行 x-1 次操作1，y 次操作2后的最小元素和
- 执行操作2，剩下变成求 [i+1，n] 这些数进行 x 次操作1，y-1 次操作2后的最小元素和
- 执行操作1和操作2，剩下变成求 [i+1，n] 这些数进行 x-1 次操作1，y-1 次操作2后的最小元素和
定义 dfs(i，x，y)：对 [i，n] 进行 x 次操作1，y 次操作2后的最小元素和，对于 nums[i] 进行分类讨论：
- 不执行任何操作，剩下变成求 [i+1，n] 这些数进行 x 次操作1，y次操作2后的最小元素和，即dfs(i+1，x，y) + nums[i]
- 执行操作1，剩下变成求 [i+1，n] 这些数进行 x-1 次操作1，y次操作2后的最小元素和，即dfs(i+1，x-1，y) + （nums[i]+1)/2
- 执行操作2，剩下变成求 [i+1，n] 这些数进行 x 次操作1，y-1次操作2后的最小元素和，即dfs(i+1，x，y-1) + nums[i] - k
- 执行操作1和操作2，剩下变成求 [i+1，n] 这些数进行 x-1 次操作1，y-1次操作2后的最小元素和，即 dfs(i+1，x-1，y-1) + (nums[i] - k + 1)/2，同时操作时先2后1更优，(nums[i]+1)/2 - k >= (nums[i]-k+1)/2
代码如下：
class Solution {
public int minArraySum(int[] nums, int k, int op1, int op2) {
int n = nums.length;
memo = new int[n][op1+1][op2+1];
for (int[][] mat : memo) {
for (int[] row : mat) {
Arrays.fill(row, -1); // -1 表示没有计算过
}
}
return dfs(0, op1, op2, k, nums);
}
int[][][] memo;
int dfs(int i, int x, int y, int k, int[] nums){
if(i == nums.length) return 0;
if(memo[i][x][y] != -1) return memo[i][x][y];
int res = dfs(i+1, x, y, k, nums) + nums[i];
if(x > 0)
res = Math.min(res, dfs(i+1, x-1, y, k, nums) + (nums[i]+1)/2);
if(y > 0 && nums[i] >= k){
res = Math.min(res, dfs(i+1, x, y-1, k, nums) + nums[i] - k);
if(x > 0){
int t = (nums[i]+1)/2 >= k ? (nums[i]+1)/2 - k : (nums[i]-k+1)/2;
res = Math.min(res, dfs(i+1, x-1, y-1, k, nums) + t);
}
}
return memo[i][x][y] = res;
}
}递推代码：
class Solution {
public int minArraySum(int[] nums, int k, int op1, int op2) {
int n = nums.length;
int[][][] f = new int[n+1][op1+1][op2+1];
for(int i=n-1; i>=0; i--){
for(int x=0; x<=op1; x++){
for(int y=0; y<=op2; y++){
f[i][x][y] = f[i+1][x][y] + nums[i];
if(x > 0)
f[i][x][y] = Math.min(f[i][x][y], f[i+1][x-1][y] + (nums[i]+1)/2);
if(y > 0 && nums[i] >= k){
f[i][x][y] = Math.min(f[i][x][y], f[i+1][x][y-1] + nums[i] - k);
if(x > 0){
int t = (nums[i]+1)/2 >= k ? (nums[i]+1)/2 - k : (nums[i]-k+1)/2;
f[i][x][y] = Math.min(f[i][x][y], f[i+1][x-1][y-1] + t);
}
}
}
}
}
return f[0][op1][op2];
}
}四，3367. 移除边之后的权重最大和
代码如下：
class Solution {
public long maximizeSumOfWeights(int[][] edges, int k) {
int n = edges.length;
List<int[]>[] g = new ArrayList[n+1];
Arrays.setAll(g, e -> new ArrayList<>());
for(int[] e : edges){
int x = e[0], y = e[1], val = e[2];
g[x].add(new int[]{y, val});
g[y].add(new int[]{x, val});
}
long[] f = dfs(0, -1, k, g);
return f[1];//{s, s+first} f[1] >= f[0]
}
long[] dfs(int x, int fa, int k, List<int[]>[] g){
PriorityQueue<Long> que = new PriorityQueue<>();//默认最小堆
long s = 0;
for(int[] y : g[x]){
if(y[0] == fa) continue;
long[] f = dfs(y[0], x, k, g);//选/不选 x-y 这条边 f[0]+y[1]/f[1]
//选/不选 怎么在至多 选K个边 的情况下，使其最大？
//先把不选的值全部求和，在求出如果选相较于不选提升了多少，
//对其进行排序，选择k个提升最大的
if(que.size() == k && que.peek() < f[0] + y[1] - f[1]){
que.poll();
}
if(que.size() < k && f[0] + y[1] - f[1] > 0){
que.offer(f[0] + y[1] - f[1]);
}
s += f[1];
}
long first = que.size() == k ? que.poll() : 0;
while(!que.isEmpty()){
s += que.poll();
}
return new long[]{s, s+first};
}
}