第429场周赛

使数组元素互不相同所需的最少操作次数

做题过程

第一次没有罚时过了。

算法概述

本题要求为每次操作为移除数组中的前三个元素，求为了使数组内元素互不相同需要多少次操作（空数组也算）。直接模拟就完了。

时间复杂度为O(n)
空间复杂度为O(n)

JAVA

class Solution {
    public int minimumOperations(int[] nums) {
        Set<Integer> set=new HashSet<>();
        // 逆序遍历
        for(int i=nums.length-1;i>=0;--i){
            // 加不进集合就说明有重复的，不用看了，都要删
            if(!set.add(nums[i])) return i/3+1;
        }
        return 0;
    }
}

总结

最顺利的一次🤣。

执行操作后不同元素的最大数量

做题过程

一开始以为直接加减一下就行，后面发现不对，可以整个数组通通跟着动让答案变的更多，想了想还得排序+dp，最后也没推出来，现在看来思路至少对了一点，但是数学思维还是不行。

算法概述

本题要求为可以对数组中的元素进行一次操作，即加减给定值（包括小于等于给定值的值），求最多可以通过处理得到多少个不同元素。参考灵神，用贪心而不是动态规划都可以🥲。

时间复杂度为O(nlogn)：排序
空间复杂度为O(1)

JAVA

class Solution {
    public int maxDistinctElements(int[] nums, int k) {
        // 排序，我也想到了
        Arrays.sort(nums);
        int ans = 0;
        // 记录前一个元素可以变为的值（初始时前面没有元素）
        int pre = Integer.MIN_VALUE; 
        for (int x : nums) {
            // 尽量使当前元素变小，但同时要比前一个元素大维持升序，同时还要避免k过小的情况（加不到pre+1）
            x = Math.min(Math.max(x - k, pre + 1), x + k);
            // 如果比前一个元素大，那么就有一个新的不同元素
            if (x > pre) {
                ans++;
                // 移动指针
                pre = x;
            }
        }
        return ans;
    }
}

总结

也就是把问题转化为了 维护一个升序数组 ，同时又需要用贪心尽量使当前的不同元素最大，这也就等同于：

尽量使排列在前的元素变小
每一对元素中的右侧元素比左侧元素大1

同时还要注意k可能为0的情况，也就是用Math.min(, x + k);进行修正。

字符相同的最短子字符串 I

算法概述

本题要求为给出一个二进制字符串以及可操作的次数，每次操作可将字符串中的一位翻转，并通过这样最小化最长的相同子字符串的长度（连续且所有字符相同）。参考灵神，使用 二分查找 逐渐缩小答案范围，持续逼近直至找到答案，根据“最短”提供思路。

时间复杂度为O(nlogn)：每次二分都要遍历一次字符串
空间复杂度为O(1)

JAVA

class Solution {
    public int minLength(String S, int numOps) {
        char[] s = S.toCharArray();
        // 标准二分
        int left = 0;
        int right = s.length;
        while (left + 1 < right) {
            // 尝试缩小答案范围
            int mid = (left + right) >>> 1;
            // 开区间写二分
            // 成功了就把答案上限变小
            if (check(mid, s, numOps)) {
                right = mid;
                // 失败了说明在中间到上限的半区内
            } else {
                left = mid;
            }
        }
        // 标准二分
        return right;
    }

    private boolean check(int m, char[] s, int numOps) {
        int n = s.length;
        // 记录当前用到的操作数
        int cnt = 0;
        // 已经逼近到1（极限）了
        if (m == 1) {
            // 要么1010要么0101
            for (int i = 0; i < n; i++) {
                // 如果 s[i] 和 i 的奇偶性不同，则自增
                cnt += (s[i] ^ i) & 1;
            }
            // n-cnt 表示改成 0101...
            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]) {
                    // 要改这么多次（已经节省了），就能确保最长相同子字符串不超过m
                    cnt += k / (m + 1);
                    k = 0;
                }
            }
        }
        // 逆向思维
        return cnt <= numOps;
    }
}

总结

这里的二分的核心还是和 二分查找 一样是逼近，其实本质上没什么不同，利用到的题目的核心特点就是最长子字符串越长，m一定越小，就是这么简单的一个道理。

🤔其他方法：

使用最大堆动态记录所有相同子字符串，用三元组存原始长度、划分、当前长度，然后每次从堆顶取出来分割，再放回去
用分桶优化上面的最大堆，就是所有桶是一个数组，用下标表示每个桶表示的相同子字符串的长度，然后把所有相同子字符串填充入相应桶中（以原长度+分割次数的形式），从最后一个桶开始减，先把桶里的元素删光（每次消耗操作数），没了一个桶就可以向下递减答案（答案设置为目标字符串原长）。

还要记得处理m=1的情况，必须单拎出来处理 。