链接:LeetCode
[Leetcode]2908. 元素和最小的山形三元组 I
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件,则认为它是一个 山形三元组 :
- i < j < k
- nums[i] < nums[j] 且 nums[k] < nums[j]
请你找出 nums 中 元素和最小 的山形三元组,并返回其 元素和 。如果不存在满足条件的三元组,返回 -1 。
遍历循环即可。
[Leetcode]2909. 元素和最小的山形三元组 II
给你一个下标从 0 开始的整数数组 nums 。
如果下标三元组 (i, j, k) 满足下述全部条件,则认为它是一个 山形三元组 :
- i < j < k
- nums[i] < nums[j] 且 nums[k] < nums[j]
请你找出 nums 中 元素和最小 的山形三元组,并返回其 元素和 。如果不存在满足条件的三元组,返回 -1 。
枚举 nums[j] + 前后缀分解。知道了 \(\textit{nums}[j]\),只需要知道 j 左边的最小值和右边的最小值,就知道了三元组的和的最小值。
class Solution {
public int minimumSum(int[] nums) {
int n = nums.length;
int[] left = new int[n];
int[] right = new int[n];
int leftMin = nums[0];
for(int i=1;i<n;++i) {
if(leftMin < nums[i]) {
left[i] = leftMin;
} else {
left[i] = Integer.MAX_VALUE;
leftMin = nums[i];
}
}
int rightMin = nums[n-1];
for(int i=n-2;i>=0;--i) {
if(rightMin < nums[i]) {
right[i] = rightMin;
} else {
right[i] = Integer.MAX_VALUE;
rightMin = nums[i];
}
}
int res = Integer.MAX_VALUE;
for(int i=1;i<n-1;++i) {
if(left[i] == Integer.MAX_VALUE || right[i] == Integer.MAX_VALUE) continue;
res = Math.min(res, left[i] + right[i] + nums[i]);
}
return res == Integer.MAX_VALUE ? -1 : res;
}
}
[Leetcode] 2910. 合法分组的最少组数
给你一个长度为 n 下标从 0 开始的整数数组 nums 。
我们想将下标进行分组,使得 [0, n - 1] 内所有下标 i 都 恰好 被分到其中一组。
如果以下条件成立,我们说这个分组方案是合法的:
- 对于每个组 g ,同一组内所有下标在 nums 中对应的数值都相等。
- 对于任意两个组 g1 和 g2 ,两个组中 下标数量 的 差值不超过 1 。
请你返回一个整数,表示得到一个合法分组方案的 最少 组数。
统计每个数字的出现次数,记在哈希表中。假设可以分成大小为 \(k\) 和 \(k+1\) 的组,现在需要算出每个 \(\textit{cnt}[x]\) 最少可以分成多少组。
由于两个组中下标数量的差值不超过 1, \(k\)最大可以取\(\textit{cnt}[x]\)中的最小值,我们可以把问题分解为两个部分:
1.\(\textit{cnt}[x]\)中的数量是否可以分成大小为 \(k\) 和 \(k+1\) 的组。
2.如果能,输出最小的分组数即可,如果不能,减小\(k\)的值再判断,直到\(k\)为零,输出\(-1\)。
针对第一个问题,我们可以先假设能进行对应的分组,则必定有\(a\)个\(k\)数量的组与\(b\)个\(k+1\)数量的组,那么针对\(\textit{cnt}[x]\)中的元素y必定有:
则
且\(a\),\(b\)为零或者正整数,要满足这个式子,必定有\(a+b>b\),也就是\(y/k > y\%k\)。反之,如果满足\(y/k > y\%k\),我们也必定能找到\(a*k+b*(k+1) = y\)的解。
针对第二个问题,如果需要分组的数目最小,我们必定需要尽量多分\(k+1\)的组,那么,求\(y/(k+1)\)的上界即可。
class Solution {
public int minGroupsForValidAssignment(int[] nums) {
Map<Integer, Integer> counter = new HashMap<>();
for(int num:nums) {
counter.put(num, counter.getOrDefault(num, 0) + 1);
}
List<Integer> set = new ArrayList<>();
int minAssignment = Integer.MAX_VALUE;
for(int count:counter.values()) {
set.add(count);
minAssignment = Math.min(minAssignment, count);
}
while(minAssignment > 0) {
if(minGroups(set, minAssignment))return getMinGroups(set, minAssignment);
else minAssignment --;
}
return -1;
}
private boolean minGroups(List<Integer> nums, int minAssignment) {
for(int num:nums) {
int a = num / minAssignment;
int b = num % minAssignment;
if(a<b) return false;
}
return true;
}
private int getMinGroups(List<Integer> nums, int minAssignment) {
System.out.println(minAssignment);
int res = 0;
for(int num:nums) {
res += Math.ceil(num*1.0/(minAssignment+1));
}
return res;
}
}
[Leetcode] 2911. 得到 K 个半回文串的最少修改次数
给你一个字符串 s 和一个整数 k ,请你将 s 分成 k 个 子字符串 ,使得每个 子字符串 变成 半回文串 需要修改的字符数目最少。
请你返回一个整数,表示需要修改的 最少 字符数目。
注意:
- 如果一个字符串从左往右和从右往左读是一样的,那么它是一个 回文串 。
- 如果长度为 len 的字符串存在一个满足 1 <= d < len 的正整数 d ,len % d == 0 成立且所有对 d 做除法余数相同的下标对应的字符连起来得到的字符串都是 回文串 ,那么我们说这个字符串是 半回文串 。比方说 "aa" ,"aba" ,"adbgad" 和 "abab" 都是 半回文串 ,而 "a" ,"ab" 和 "abca" 不是。
- 子字符串 指的是一个字符串中一段连续的字符序列。
factors = [[] for _ in range(201)]
for i in range(1, 201):
for j in range(i * 2, 201, i):
factors[j].append(i)
class Solution:
def minimumChanges(self, s: str, steps: int) -> int:
def f(i, j):
l = j - i + 1
ans = inf
for x in factors[l]:
res = 0
for k in range(x):
substr = s[i + k:j + 1:x]
for idx in range(len(substr) // 2):
if substr[idx] != substr[-idx-1]:
res += 1
ans = min(ans, res)
return ans
n = len(s)
calc = [[inf] * n for _ in range(n)]
for i in range(n):
for j in range(i + 1, n):
calc[i][j] = f(i, j)
# dp[i][j] 表示 s[0] 到 s[i-1] 分为 j 个字符串需要修改的字母数量
dp = [[inf] * (steps + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(n):
for j in range(steps):
if dp[i][j] < inf:
# 枚举新的字符串 s[i] 到 s[k],注意,所有长度为 1 的字符串不满足条件
for k in range(i + 1, n):
dp[k+1][j+1] = min(dp[k+1][j+1], dp[i][j] + calc[i][k])
return dp[-1][-1]
参考:LeetCode
- Leetcode Contest Weekly 368leetcode contest weekly 368 leetcode contest weekly 361 leetcode contest weekly 355 leetcode contest weekly 365 leetcode contest weekly 367 leetcode contest weekly 350 leetcode contest weekly 351 leetcode contest weekly 339 leetcode contest weekly 364 leetcode contest weekly 359