个人如何制作网站源码,asp网站设为首页代码,局域网的网站建设,私人app一键制作器软件目录
一#xff0c;3364. 最小正和子数组
二#xff0c; 3365. 重排子字符串以形成目标字符串
三#xff0c;3366. 最小数组和
四#xff0c;3367. 移除边之后的权重最大和 一#xff0c;3364. 最小正和子数组 本题可以直接暴力枚举#xff0c;代码如下#xff1a; …目录
一3364. 最小正和子数组
二 3365. 重排子字符串以形成目标字符串
三3366. 最小数组和
四3367. 移除边之后的权重最大和 一3364. 最小正和子数组 本题可以直接暴力枚举代码如下
class Solution {public int minimumSumSubarray(ListInteger nums, int l, int r) {int n nums.size();int ans Integer.MAX_VALUE;for(int kl; kr; k){int s 0;for(int i0, j0; jn; j){s nums.get(j);if(j-i1 k){s - nums.get(i);i;}if(j-i1 k s 0) ans Math.min(ans, s);}}return ansInteger.MAX_VALUE ? -1 : ans;}
}
如果它的数据范围更大一点上述做法会超时所以这里再介绍一个O(n*logn)的做法
这题求子数组和的最小正值子数组和可以直接使用前缀和来求题目要求子数组的长度在 [LR] 之间可以枚举左端点 / 右端点这里选择枚举右端点下标 i再根据上述条件直接推出左端点的下标 j 的范围 [i-Ri-L]假设前缀和数组为 s此时 si 是固定的要使得 si - sj 的值更大sj 必须是小于 si 的最大值题目要求为正数求 sj si 的最大值且 j 属于 [i-Ri-L]这可以使用有序集合二分来做
代码如下
class Solution {public int minimumSumSubarray(ListInteger nums, int l, int r) {int n nums.size();int ans Integer.MAX_VALUE;int[] pre new int[n1];for(int i0; in; i){pre[i1] pre[i] nums.get(i);}//枚举右端点[i-r, i-l] ~ i//s[i-r, i-l] si, 二分枚举最接近si的值 TreeMapInteger, Integer map new TreeMap();for(int il, j0; in; i){map.merge(pre[i-l], 1, Integer::sum);// 错误写法// 当lr时会出错没有计算当前子数组的大小// 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) {MapString, Integer map new HashMap();int n s.length();for(int in/k; in; in/k){map.merge(s.substring(i-n/k, i), 1, Integer::sum);}for(int in/k; in; in/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 个数来说
不执行任何操作剩下变成求 [i1n] 这些数进行 x 次操作1y 次操作2后的最小元素和执行操作1剩下变成求 [i1n] 这些数进行 x-1 次操作1y 次操作2后的最小元素和执行操作2剩下变成求 [i1n] 这些数进行 x 次操作1y-1 次操作2后的最小元素和执行操作1和操作2剩下变成求 [i1n] 这些数进行 x-1 次操作1y-1 次操作2后的最小元素和
定义 dfs(ixy)对 [in] 进行 x 次操作1y 次操作2后的最小元素和对于 nums[i] 进行分类讨论
不执行任何操作剩下变成求 [i1n] 这些数进行 x 次操作1y次操作2后的最小元素和即dfs(i1xy) nums[i]执行操作1剩下变成求 [i1n] 这些数进行 x-1 次操作1y次操作2后的最小元素和即dfs(i1x-1y) nums[i]1)/2执行操作2剩下变成求 [i1n] 这些数进行 x 次操作1y-1次操作2后的最小元素和即dfs(i1xy-1) nums[i] - k执行操作1和操作2剩下变成求 [i1n] 这些数进行 x-1 次操作1y-1次操作2后的最小元素和即 dfs(i1x-1y-1) (nums[i] - k 1)/2同时操作时先2后1更优(nums[i]1)/2 - k (nums[i]-k1)/2
代码如下
class Solution {public int minArraySum(int[] nums, int k, int op1, int op2) {int n nums.length;memo new int[n][op11][op21];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(i1, x, y, k, nums) nums[i];if(x 0)res Math.min(res, dfs(i1, x-1, y, k, nums) (nums[i]1)/2);if(y 0 nums[i] k){res Math.min(res, dfs(i1, 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]-k1)/2;res Math.min(res, dfs(i1, 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[n1][op11][op21];for(int in-1; i0; i--){for(int x0; xop1; x){for(int y0; yop2; y){f[i][x][y] f[i1][x][y] nums[i];if(x 0)f[i][x][y] Math.min(f[i][x][y], f[i1][x-1][y] (nums[i]1)/2);if(y 0 nums[i] k){f[i][x][y] Math.min(f[i][x][y], f[i1][x][y-1] nums[i] - k);if(x 0){int t (nums[i]1)/2 k ? (nums[i]1)/2 - k : (nums[i]-k1)/2;f[i][x][y] Math.min(f[i][x][y], f[i1][x-1][y-1] t);}}}}}return f[0][op1][op2];}
}
四3367. 移除边之后的权重最大和 代码如下
class Solution {public long maximizeSumOfWeights(int[][] edges, int k) {int n edges.length;Listint[][] g new ArrayList[n1];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, sfirst} f[1] f[0]}long[] dfs(int x, int fa, int k, Listint[][] g){PriorityQueueLong 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, sfirst};}
}
