力扣 第 368 场周赛

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 i=1; i<n; i++) {pre[i] = Math.min(nums[i], pre[i-1]);}        for(int i=n-2; i>=0; i--) {suf[i] = Math.min(nums[i], suf[i+1]);}int ans = Integer.MAX_VALUE;for(int i=1; i<n-1; i++) {if(pre[i-1]<nums[i] && nums[i]>suf[i+1]) {ans = Math.min(ans, pre[i-1]+nums[i]+suf[i+1]);}}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{出现次数}，最小为1，K为出现次数的最小值。由大至小遍历上述的K值，c为当前组的值，q=c/k为当前组可以分的最少组，r=c%k为剩余的人数，显然q>=r时候，该次分组才是有效的。

class Solution {public int minGroupsForValidAssignment(int[] nums) {Map<Integer, Integer> map = new HashMap();for(int num:nums) {map.put(num, map.getOrDefault(num, 0)+1);}int minK = Integer.MAX_VALUE;for(Map.Entry<Integer, Integer> entry:map.entrySet()) {minK = Math.min(minK, entry.getValue());}int ans = 0;int res = Integer.MAX_VALUE;boolean f = true;for(int k=minK; k>=1; k--) {ans = 0;f = true;for(Map.Entry<Integer, Integer> entry:map.entrySet()) {int c = entry.getValue();int q = c/k;int r = c%k;if(q<r) {f = false;break;}ans = ans + (int)Math.ceil((double)c/(k+1));}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 List<Integer>[] divisors = new ArrayList[C];static{Arrays.setAll(divisors, e-> new ArrayList<>());for(int i=1; i<C; i++) {for(int j=i*2; j<C; 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 i=0; i<n; i++) {for(int j=i+1; j<n; j++) {modify[i][j] = getModify(s.substring(i, j+1));}}/**dp[i][j]: i表示剩余切割的次数，j表示要处理的字符串的最后一位dp[i][j] = dp[]*/int[][] memo = new int[k][n];for(int i=0; i<k; 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) {// 第一种i=0if(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; L<j; 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 i0=0; i0<d; i0++) {for(int i=i0, j=n-1-i0; i<j; i=i+i0, j=j-i0) {if(s.charAt(i)!=s.charAt(j)) {cnt ++;}}}ans = Math.min(ans, cnt);}return ans;}
}