2025-10-21 学习日记

发布于 2025-10-21 12:00 1296 字 7 min read 手写每个字都是我自己敲的。

今日学习记录

1. 3346. 执行操作后元素的最高频率 I

关键词：二分,枚举 问题分析：给你一个整数数组 nums 和两个整数 k 和 numOperations 。你必须对 nums 执行操作 numOperations 次。每次操作中，你可以：

选择一个下标 i ，它在之前的操作中没有被选择过。
将 nums[i] 增加范围 [-k, k] 中的一个整数。在执行完所有操作以后，请你返回 nums 中出现 频率最高 元素的出现次数。一个元素 x 的频率指的是它在数组中出现的次数。 核心思路:

枚举+二分搜索

看到这个题第一眼就是差分,但是这个题不同于常规的简单题,而是限制了操作次数,先暴力模拟,我们要想出最优的叠被子法找到被子层数最多的方案,很难,所以正难则反,不如从答案的角度往前看,我要找到答案所在的范围,就是要找[ans-k,ans+k]的范围,而我们不知道答案到底是什么,所以枚举,找上界和小界,先对数组排序,再使用二分法搜索,这里要注意,操作是可以对两个值同时进行操作的,如果两个数要尽可能有交点,要 a+k 和 b-k(a<b),要有交集,就是要把每个数的-k 和+k 状态放入搜索中,可以先进行去重,再进行遍历 tip:找到的这个范围内会有原来就是答案的值(不需要操作,但是占了操作数),所以需要一个哈希表来记录每个数的频次,最后ans= max(min(r-l+1-mp[num],oper)+mp[num],ans)

ranges::sort(nums);

        unordered_set<int> st;

        int n = nums.size(), res = 0;

        unordered_map<int, int> cnt;

        for(int i = 0; i < n; i ++) {

            st.insert(nums[i]);

            st.insert(nums[i] - k), st.insert(nums[i] + k);

        }

        for(int& x : nums) cnt[x] ++;

        for(int x : st) {

            int r = upper_bound(nums.begin(), nums.end(), x+k) - lower_bound(nums.begin(), nums.end(), x-k) - cnt[x];

            res = max(res, min(r, numOperations) + cnt[x]);

        }

        return res;

学到的点：

二分

2. 3347. 执行操作后元素的最高频率 II

关键词：差分 前缀和 滑动窗口 三指针 问题分析：难在数据范围,这次就不能光搜索了,要上技巧了

核心思路

差分+前缀和

一眼差分,就是差分,用差分最简单,每个数都能变成[num-k,num+k]范围中的数,所以干脆直接将该范围中的数的次数都加一,然后再前缀和进行统计最大的覆盖次数,这里其实还有一个贪心的最优选择,因为我们要找的是有限操作次数后能得到的最大频次,这里的想法是无论我怎么加,最大的数永远都是最大的,所以先在没有限制的条件下去找到最大的数,再根据实际限制的操作次数进行比较计算,这里还是要考虑,原数值不消耗操作次数的情况(依旧哈希表) tip:因为只要计数,所以使用 map 来记录该加该减的位置,要使用红黑树实现的 map(有顺序)

unordered_map<int,int> mp;

        map<int,int> diff;

        int n = nums.size();

        for(int &x:nums){

            mp[x]++;

            diff[x];

            diff[x-k]++;

            diff[x+k+1]--;

        }

        int ans = 0;

        int sum = 0;

        for(auto [a,b]:diff){

            sum += b;

            ans = max(ans,min(sum-mp[a],numOperations)+mp[a]);

        }

        return ans;

同向三指针+滑动窗口

这个题难就难在难想,实现起来真不难,之前做过类似的滑动窗口的题目,而这个三指针就是维护三个值 num-k,num+k,以及下一个 num-k,但是这个方法是两个方法分开计算,这点没想到

最终代码：

int maxFrequency(vector<int>& nums, int k, int numOperations) {

        ranges::sort(nums);

        int n = nums.size();

        int ans = 0, cnt = 0, left = 0, right = 0;

        for (int i = 0; i < n; i++) {

            int x = nums[i];

            cnt++;

            if (i < n - 1 && x == nums[i + 1]) continue;

            while (nums[left] < x - k) left++;

            while (right < n && nums[right] <= x + k) right++;

            ans = max(ans, min(right - left, cnt + numOperations));

            cnt = 0;

        }

  

        if (ans >= numOperations) return ans;

        left = 0;

        for (int right = 0; right < n; right++) {

            int x = nums[right];

            while (nums[left] < x - k * 2) left++;

            ans = max(ans, right - left + 1);

        }

        return min(ans, numOperations);

    }