目录
一，3396. 使数组元素互不相同所需的最少操作次数
倒着遍历 nums，将 nums[i] 存入哈希表中，如果 nums[i] 重复出现，说明要将 [0，i] 区间所有的元素删除，返回（i+1)/3 向上取整，即 i / 3 + 1
代码如下：
class Solution {
public int minimumOperations(int[] nums) {
Set<Integer> set = new HashSet<>();
int n = nums.length;
for(int i=n-1; i>=0; i--){
if(set.contains(nums[i]))
return i/3+1;
set.add(nums[i]);
}
return 0;
}
}二，3397. 执行操作后不同元素的最大数量
本题就是一道贪心题，就跟排队一样，后一个人需要紧贴前一个人，这样才能空出更多的位置给后面的人。所以需要将 nums 数组排序，枚举 nums 数组，使用 L 记录前一个人的位置，此时当前人的位置要尽可能贴近 L（但是也要在 [nums[i] - k，nums[i]+k] 的范围内），所以当前人的位置应该是 x = min(max(nums[i] - k，L+1)，nums[i] - k），判断 x 是否大于 L，如果是，说明获得了一个不同的元素，ans++。最终返回 ans。
代码如下：
class Solution {
public int maxDistinctElements(int[] nums, int k) {
Arrays.sort(nums);
int ans = 0;
int l = Integer.MIN_VALUE;
for(int x : nums){
x = Math.min(Math.max(x-k, l+1), x+k);
if(x > l){
ans++;
l = x;
}
}
return ans;
}
}三，3398. 字符相同的最短子字符串 I
T3 和 T4 一样，这里一起讲了。本题有这样一个性质，假设执行所有操作后获得的长度为 m，m越小，它越不容易实现，m越大它越容易实现，具有单调性，所以可以使用二分来做。
二分长度 m，接下来就是判断二分的长度 m 是否可以在 numOps 次操作内得到，这里可以用贪心的思路来想，假设有一个字符串 s = "000000000"，m = 3，要想该字符串满足条件，需要在 m，2m 处执行操作（将 '0' 改成 ’1‘），此时字符串变成 "000100010"，也就是说需要 s.length / (m+1) 次操作。
但是有一种特殊情况，在 m = 1 时，如果 s = "0010" ，就不能使用上述结论来计算了，因为如果对 m 位置进行操作，s = "0110"，这会导致出现一个连续的 1，所以需要单独处理 m = 1 的情况，此时字符串 s 最终只能有两种形态 "0101010..."，"10101010..."，很好计算需要几次操作。
代码如下：
class Solution {
public int minLength(String str, int op) {
int n = str.length();
char[] s = str.toCharArray();
int l = 1, r = n;
while(l <= r){//[l,r]
int mid = (l + r) / 2;
if(check(mid, op, s)){
r = mid - 1;
}else{
l = mid + 1;
}
}
return r + 1;
}
boolean check(int m, int op, char[] s){
int n = s.length;
int cnt = 0;
if(m == 1){
for(int i=0; i<n; i++){
//如果 s[i] 与 i 的奇偶不同， cnt++
cnt += (s[i] ^ i) & 1;
}
cnt = Math.min(cnt, n - cnt);
}else{
int k = 0;
for(int i=0; i<n; i++){
k++;
if(i==n-1 || s[i] != s[i+1]){
cnt += k / (m + 1);
k = 0;
}
}
}
return cnt <= op;
}
}