100106. Minimum Sum of Mountain Triplets I
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件，则认为它是一个 山形三元组 ：
- i < j < k
- nums[i] < nums[j] 且 nums[k] < nums[j]
请你找出 nums 中 元素和最小 的山形三元组，并返回其 元素和 。如果不存在满足条件的三元组，返回 -1 。
测试样例：
输入：nums = [8,6,1,5,3]
输出：9
解释：
三元组 (2, 3, 4) 是一个元素和等于 9 的山形三元组，因为：
- 2 < 3 < 4
- nums[2] < nums[3] 且 nums[4] < nums[3]
这个三元组的元素和等于 nums[2] + nums[3] + nums[4] = 9 。可以证明不存在元素和小于 9 的山形三元组。
解答：第一题和第二题一样，我也就只写一题题解了。因为需要寻找三元组，有需要最小山形三元组，所以我们可以想到利用TreeMap来记录数字左右两边的最小值情况。我的习惯是从右到左遍历，这样，当前数字右边可以用一个数字记录最小，右边利用TreeMap动态更新数组排序情况。
class Solution {
public int minimumSum(int[] nums) {
TreeMap<Integer, Integer> left = new TreeMap<>();
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; ++i) {
left.put(nums[i], left.getOrDefault(nums[i], 0) + 1);
}
int res = Integer.MAX_VALUE;
for (int i = nums.length - 1; i >= 1; --i) {
min = Math.min(min, nums[i]);
int count = left.get(nums[i]);
if (count == 1) {
left.remove(nums[i]);
} else {
left.put(nums[i], count - 1);
}
int leftMin = left.firstKey();
if (nums[i] > leftMin && nums[i] > min) {
res = Math.min(res, nums[i] + leftMin + min);
}
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}100097. Minimum Number of Groups to Create a Valid Assignment
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组，使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立，我们说这个分组方案是合法的：
- 对于每个组 g ，同一组内所有下标在 nums 中对应的数值都相等。
- 对于任意两个组 g1 和 g2 ，两个组中 下标数量 的 差值不超过 1 。
请你返回一个整数，表示得到一个合法分组方案的 最少 组数。
测试样例：
输入：nums = [3,2,3,2,3]
输出：2
解释：
一个得到 2 个分组的方案如下，中括号内的数字都是下标：
- 组 1 -> [0,2,4]
- 组 2 -> [1,3]
所有下标都只属于一个组。
- 组 1 中，nums[0] == nums[2] == nums[4] ，所有下标对应的数值都相等。
- 组 2 中，nums[1] == nums[3] ，所有下标对应的数值都相等。
- 组 1 中下标数目为 3 ，组 2 中下标数目为 2 。
两者之差不超过 1 。无法得到一个小于 2 组的答案，因为如果只有 1 组，组内所有下标对应的数值都要相等。所以答案为 2 。
解答：这道题目有一个小的暗含条件，1 <= nums.length <= 10^5，那么最多分组就是447个。利用HashMap聚合之后，是可以利用暴力计算的。组的最大规模就是最小频数的出现频次 + 1。然后判断一下每个数是否可以被完成计算即可(isValid函数)。
class Solution {
public int minGroupsForValidAssignment(int[] nums) {
HashMap<Integer, Integer> group = new HashMap<>();
for (int n : nums) {
group.put(n, group.getOrDefault(n, 0 ) + 1);
}
int max = Integer.MAX_VALUE;
for (Map.Entry<Integer, Integer> kv : group.entrySet()) {
max = Math.min(max, kv.getValue());
}
for (int i = max + 1; i > 1; --i) {
if (isValid(max, i) != -1) {
boolean isValid = true;
int groupNum = 0;
for (Map.Entry<Integer, Integer> kv : group.entrySet()) {
int tmp = isValid(kv.getValue(), i);
if (tmp == -1) {
isValid = false;
break;
} else {
groupNum += tmp;
}
}
if (isValid) {
return groupNum;
}
}
}
return nums.length;
}
private int isValid(int num, int max) {
int y = num % max;
if (y == 0) {
return num / max;
} else {
y = max - y;
if ((max - 1) * y > num) {
return -1;
} else {
return y + (num - (max - 1) * y) / max;
}
}
}
}6920. Minimum Changes to Make K Semi-palindromes
给你一个字符串 s 和一个整数 k ，请你将 s 分成 k 个 子字符串 ，使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数，表示需要修改的 最少 字符数目。
注意：
- 如果一个字符串从左往右和从右往左读是一样的，那么它是一个 回文串 。
- 如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ，len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ，那么我们说这个字符串是 半回文串 。比方说 "aa" ，"aba" ，"adbgad" 和 "abab" 都是 半回文串 ，而 "a" ，"ab" 和 "abca" 不是。
- 子字符串 指的是一个字符串中一段连续的字符序列。
测试样例
输入：s = "abcac", k = 2
输出：1
解释：
我们可以将 s 分成子字符串 "ab" 和 "cac" 。子字符串 "cac" 已经是半回文串。如果我们将 "ab" 变成 "aa" ，它也会变成一个 d = 1 的半回文串。该方案是将 s 分成 2 个子字符串的前提下，得到 2 个半回文子字符串需要的最少修改次数。所以答案为 1 。
解答：这道题目看着唬人，其实难度不大，基本每一步都能暴力。首先我们先记录一个二维数组，作用时计算i->j位，变成半回文串所需要的最小操作数（有len % d == 0这个条件，所以实际会进行计算的分支不多，可以暴力）。然后利用动态规划（我用了记忆搜索的写法）计算当前数组变成k个字串的最小操作数。
class Solution {
private String s;
private int[][] mem;
private Integer[][] dp;
public int minimumChanges(String s, int k) {
int len = s.length();
this.s = s;
mem = new int[len][len];
for (int i = 0; i < s.length(); ++i) {
for (int j = i; j < s.length(); ++j) {
mem[i][j] = minChange(i, j);
}
}
dp = new Integer[len][k];
return helper(0, k - 1);
}
private int minChange(int st, int ed) {
if (st == ed) return -1;
int len = ed - st + 1;
int res = Integer.MAX_VALUE;
for (int i = 1; i < len; ++i) {
if (len % i == 0) {
List<Character>[] lists = new List[i];
for (int j = 0; j < i; ++j) {
lists[j] = new ArrayList<>();
}
for (int j = st; j <= ed; ++j) {
lists[(j - st) % i].add(s.charAt(j));
}
int cur = 0;
for (List<Character> list : lists) {
cur += minChangeOneList(list);
}
res = Math.min(cur, res);
}
}
return res;
}
private int minChangeOneList(List<Character> list) {
int st = 0, ed = list.size() - 1;
int res = 0;
while (st < ed) {
if (list.get(st) != list.get(ed)) {
++res;
}
++st;
--ed;
}
return res;
}
private int helper(int pos, int k) {
if (k == 0) {
if ((s.length() - pos) < 2 * (k + 1)) return -1;
return mem[pos][s.length() - 1];
} else if ((s.length() - pos) < 2 * (k + 1)) {
return -1;
} else if (dp[pos][k] == null) {
dp[pos][k] = Integer.MAX_VALUE;
for (int i = pos + 1; i < s.length(); ++i) {
int tmp = helper(i + 1, k - 1);
if (tmp != -1) {
dp[pos][k] = Math.min(dp[pos][k], tmp + mem[pos][i]);
}
}
if (dp[pos][k] == Integer.MAX_VALUE) {
dp[pos][k] = -1;
}
}
return dp[pos][k];
}
}