做暧暧国外网站,wordpress简体中文版本,网站开发的背景知识和技术,南宁网站搜索引擎优化2908. 元素和最小的山形三元组 I
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件#xff0c;则认为它是一个 山形三元组 #xff1a;
i j k nums[i] nums[j] 且 nums[k] nums[j] 请你找出 nums 中 元素和最小 的…2908. 元素和最小的山形三元组 I
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件则认为它是一个 山形三元组
i j k nums[i] nums[j] 且 nums[k] nums[j] 请你找出 nums 中 元素和最小 的山形三元组并返回其 元素和 。如果不存在满足条件的三元组返回 -1 。 复杂度O(N) 思路前后缀分解。一个数组记录前缀最小值一个数组记录后缀最小值。
class Solution {public int minimumSum(int[] nums) {int n nums.length; // 这两个都取最小值int[] pre new int[n];pre[0] nums[0]; int[] suf new int[n];suf[n-1] nums[n-1]; for(int i1; in; i) {pre[i] Math.min(nums[i], pre[i-1]);} for(int in-2; i0; i--) {suf[i] Math.min(nums[i], suf[i1]);}int ans Integer.MAX_VALUE;for(int i1; in-1; i) {if(pre[i-1]nums[i] nums[i]suf[i1]) {ans Math.min(ans, pre[i-1]nums[i]suf[i1]);}}if(ans Integer.MAX_VALUE) {return -1;} return ans; }
}2910. 合法分组的最少组数
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立我们说这个分组方案是合法的
对于每个组 g 同一组内所有下标在 nums 中对应的数值都相等。 对于任意两个组 g1 和 g2 两个组中 下标数量 的 差值不超过 1 。 请你返回一个整数表示得到一个合法分组方案的最少组数。 复杂度O(N) 思路使用HashMap统计每个数字出现的次数map数字出现次数。由于分组后两个组的成员数相差不能大于1。所以每个组的成员数最大为min{出现次数}最小为1K为出现次数的最小值。由大至小遍历上述的K值c为当前组的值qc/k为当前组可以分的最少组rc%k为剩余的人数显然qr时候该次分组才是有效的。
class Solution {public int minGroupsForValidAssignment(int[] nums) {MapInteger, Integer map new HashMap();for(int num:nums) {map.put(num, map.getOrDefault(num, 0)1);}int minK Integer.MAX_VALUE;for(Map.EntryInteger, Integer entry:map.entrySet()) {minK Math.min(minK, entry.getValue());}int ans 0;int res Integer.MAX_VALUE;boolean f true;for(int kminK; k1; k--) {ans 0;f true;for(Map.EntryInteger, Integer entry:map.entrySet()) {int c entry.getValue();int q c/k;int r c%k;if(qr) {f false;break;}ans ans (int)Math.ceil((double)c/(k1));}if(f true) {res Math.min(res, ans);}}return res;}
}2911. 得到 K 个半回文串的最少修改次数
给你一个字符串 s 和一个整数 k 请你将 s 分成 k 个 子字符串 使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数表示需要修改的 最少 字符数目。
注意
如果一个字符串从左往右和从右往左读是一样的那么它是一个 回文串 。 如果长度为 len 的字符串存在一个满足 1 d len 的正整数 d len % d 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 那么我们说这个字符串是 半回文串 。比方说 “aa” “aba” “adbgad” 和 “abab” 都是 半回文串 而 “a” “ab” 和 “abca” 不是。 子字符串 指的是一个字符串中一段连续的字符序列。 class Solution {private static Integer C 202;private static ListInteger[] divisors new ArrayList[C];static{Arrays.setAll(divisors, e- new ArrayList());for(int i1; iC; i) {for(int ji*2; jC; j) {divisors[j].add(i);}}}private int[][] modify;public int minimumChanges(String s, int k) {int n s.length();// 表示从i到j需要的变换次数modify new int[n][n];for(int i0; in; i) {for(int ji1; jn; j) {modify[i][j] getModify(s.substring(i, j1));}}/**dp[i][j]: i表示剩余切割的次数j表示要处理的字符串的最后一位dp[i][j] dp[]*/int[][] memo new int[k][n];for(int i0; ik; i) {Arrays.setAll(memo[i],e- -1);}return dfs(k-1, n-1, modify, memo);}public Integer dfs(int i, int j, int[][] modify, int[][] memo) {// 第一种i0if(i 0) {return modify[0][j];}if(memo[i][j] ! -1) {return memo[i][j];}int min Integer.MAX_VALUE;for(int L i*2; Lj; L) {min Math.min(min, dfs(i-1, L-1, modify, memo)modify[L][j]);}return memo[i][j] min;}private Integer getModify(String s) {int n s.length();int ans Integer.MAX_VALUE;for(int d:divisors[n]) {int cnt 0;for(int i00; i0d; i0) {for(int ii0, jn-1-i0; ij; iii0, jj-i0) {if(s.charAt(i)!s.charAt(j)) {cnt ;}}}ans Math.min(ans, cnt);}return ans;}
}
