【上分日记】第376场周赛(中位数 + 排序)

2023-12-18 15:36:51

前言

?本周的力扣只写出来了两道题,都较为简单,之后的两道题个人觉得比较难想,因为我做不出来(hhh,菜鸡勿喷)。今天就来具体的总结一下。

正文

1.100161. 划分数组并满足最大差限制

  • 下面我们直接给出思路,题目如果感兴趣可以点开链接查看。

?这道题虽然做出来了,但写的的代码不太优雅,因此稍稍总结一下。

  1. 我们只需排序,不断取出三个数进行比较即可。
  2. 计算三个数的最大值与最小值的差。
  3. 如果差小于等于k,则添加到数组中。
  4. 如果差大于k,则不满足情况直接返回空即可。
  • 代码:
class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) 
    {
        vector<vector<int>> ret;
        sort(nums.begin(),nums.end());
        for(int i = 0; i < nums.size(); i += 3)
        {
            //如果最大值与最小值的差,如果大于k,直接返回空数组。
            if(nums[i + 2] - nums[i] > k)
                return vector<vector<int>>();
            //添加到数组中。
            vector<int> tmp;
            for(int j = i; j < i + 3; j++)
                tmp.push_back(nums[j]);
            ret.push_back(tmp);
        }
        return ret;
    }
};

2.100151. 使数组成为等数数组的最小代价

  • 这道题卡了半天,还做不出来,真的寄了。
  • 题目思路:
  1. 准备工作,快速枚举1到109回文数

如何枚举呢?我们可以这样进行思考:

  1. 回文数的长度是分奇数长度和偶数长度的。
  2. 奇数长度的回文数,就等于选中间的数,然后拆成两半。
  3. 偶数长度的回文数,就等于直接将数砍成两半。
  • 图解:
    在这里插入图片描述

如何实现呢?我们可以这样进行控制进行严格递增。

  • 每次枚举长度相同的数。
  • 比如 1 - 9 数字长度是相同的,且为1。10, 99 长度是相同的,且为2。

如何将数字分成两种情况进行讨论呢?

  • 此处我们以121进行举例:
    在这里插入图片描述
  • 实现代码:

    vector<int> Palindromic_number;//存放回文数
    //枚举函数
    void enumerate()
    {
        //区间左闭右开
        for (int i = 1; i < 1e5; i *= 10)
        {
            for (int j = i; j < i * 10; j++)//枚举长度相同的数
            {
                int x = j;
                int t = j / 10;//枚举奇数位
                while (t)
                {
                    x *= 10;
                    int tmp = t % 10;
                    x += tmp;
                    t /= 10;
                }

                //添加到数组中
                Palindromic_number.push_back(x);
            }
            if(i < 1e4)
            {
                for (int j = i; j < i * 10; j++)
                {
                    int x = j;
                    int t = j ;//枚举偶数位
                    while (t)
                    {
                        if((long long)x * 10  > INT_MAX)
                            cout << j << endl; 
                        x *= 10;
                        int tmp = t % 10;
                        x += tmp;
                        t /= 10;
                    }
                    //添加到数组中
                    Palindromic_number.push_back(x);
                }
            }
        }
    }

  1. 分析题目
  • 如何做到 " 代价 " 最小 ?
  • 在解题的过程中博主想到的平均数与中位数,但不知道用哪一个,下面我们来具体的分析一下。
  1. 平均数(代价无法达到最小)。

下面我们来简单思考一下为什么?

先简单的举个例子:

在这里插入图片描述

  • 平均数是用来反映整体的水平的,比如两个地区的收入。
  • 可见平均数不能反应部分的情况,如果把马云的工资给各位分一分,相一个大学生也是有比较不错的收入的。

下面我们再来分析分析中位数为什么能呢?

在这里插入图片描述

  1. 结合回文数。

我们的目的就变成的,找与中位数最相近的回文数。

  • 此处我们还要接着分析:
  1. 如果中位数恰好为回文数,则直接计算代价即可。
  2. 如果中位数不为回文数,我们要从附近的范围开始找。
  • 以上默认数组以排好序。

  • 实现代码:

class Solution {
public:
    vector<int> Palindromic_number;//存放回文数
    //枚举函数
    void enumerate()
    {
        //区间左闭右开
        for (int i = 1; i < 1e5; i *= 10)
        {
            for (int j = i; j < i * 10; j++)//枚举长度相同的数
            {
                int x = j;
                int t = j / 10;//枚举奇数位
                while (t)
                {
                    x *= 10;
                    int tmp = t % 10;
                    x += tmp;
                    t /= 10;
                }

                //添加到数组中
                Palindromic_number.push_back(x);
            }
            if(i < 1e4)
            {
                for (int j = i; j < i * 10; j++)
                {
                    int x = j;
                    int t = j ;//枚举偶数位
                    while (t)
                    {
                        if((long long)x * 10  > INT_MAX)
                            cout << j << endl; 
                        x *= 10;
                        int tmp = t % 10;
                        x += tmp;
                        t /= 10;
                    }
                    //添加到数组中
                    Palindromic_number.push_back(x);
                }
            }
        }
    }

    int near_palind(int num)
    {
        int index = 0;
        for(int i = 0; i < Palindromic_number.size(); i++)
        {
            if(Palindromic_number[i] >= num)
            {
                index = i;
                break;
            }
        }
        return index;
    } 
    long long cost(vector<int> &nums,int target)
    {
        long long c = 0;
        for(long long e : nums)
            c += abs((long long)target - e);
        return c;
    }
    long long minimumCost(vector<int>& nums) 
    {
        //快速枚举回文数
        enumerate();
        //添加一个数防止Palindromic_number访问越界
        Palindromic_number.push_back(1e9 + 1);
        //排序数组
        sort(nums.begin(),nums.end());
        //找离中位数最近的回文数
        int sz = nums.size();
        int left = nums[(sz - 1) / 2]; 
        int right = nums[sz / 2];
        //如果为偶数个,(sz - 1) / 2 != sz / 2;
        //如果为奇数数个,(sz - 1) / 2 == sz / 2;

        //找到第一个大于等于 left的回文数的下标.
        int index = near_palind(left);

        //先计算当前的l_cost
        long long l_cost = cost(nums,Palindromic_number[index]);
        //如果index指向的值小于等于right。
        if(Palindromic_number[index] <= right)
        {
            //说明在[left,right]之间直接返回即可
            return l_cost;
        }
        long long r_cost = cost(nums,Palindromic_number[index-1]);
		/*
		否则在Palindromic_number[index]和Palindromic_number[index-1]
		之间。
		*/
        return min(r_cost,l_cost);
    }
};
  • 暴力枚举需注意——index-1可能会出现负数的情况。

3.2968. 执行操作使频率分数最大

  • 此题与上面的一道题的思路大致一样。
  • 除此之外,多的两点是 滑动窗口 + 前缀和
  1. 先来简单的解析一下。
  1. 首先让每一位数都增加与减少一,限定操作次数,从而使这个数组的相同的数最多。
  2. 每一位数增加或减少一 + 限定操作次数 == 所有数离某一个数距离和最近。这里的 限定操作次数 < = > 所有数据中位数的距离和。这两个数要进行比较。
  3. 而且一个数组向中位数转换的操作次数是最小的。
  4. 因此问题转换为是求一个子数组中,向中位数转换的距离和,目的是问这个在限定操作次数只内,这个子数组的最长的长度。
  1. 具体思路。

首先我们先来讨论一下,为什么要用滑动窗口?

  1. 滑动窗口使用条件:满足单调性
  2. 我们再来看维护子数组的区间,right 向 右移动,这里因为新来的这个数,所有数据中位数的距离和在增加,即所需的操作次数在增加。
  3. 在来看,left右移,因为要减少一个数,这个距离和就缺少了left执行的数距中位数的距离。因此所需操作次数减少。
  4. 因此满足单调性,我们可以使用滑动窗口。
  • 滑动窗口的使用方法,枚举右/左端点,求右/左端点。本题为枚举右端点找左端点。
  1. 首先要想使子数组操作次数最小,我们先要对数组进行排序。(sort)
  2. 其次我们要维护一个区间是这段区间满足的,此时向中位数转换的距离和小于等于限定次数。
  3. 因此求出这段区间距中位数距离和。进行判断,如果满足则进行与当前在限定操作次数内的最长子数组求最大值。

我们还有一个点:如何快速求所有数距离中位数的和。

在这里插入图片描述

  • 很明显:蓝色面积 + 绿色面积,即为距中位数的距离和。
  • 细节:偶数中位数取哪一个都不影响,切入点——距离和,即代价不变,具体详见第二题。
  • 实现代码:
class Solution {
public:
    int maxFrequencyScore(vector<int>& nums, long long k) 
    {
        //先进行排序
        sort(nums.begin(),nums.end());
        int sz = nums.size();

        //求前缀和
        vector<long long> s(sz + 1);
        for(int i = 1; i <= sz; i++)
            s[i] = s[i-1] + nums[i-1];
        
    
        auto distance_sum = [&](int left,int right)->long long 
        {
            int mid_i  = (left + right) / 2; 
            
            long long s_left = (long long)nums[mid_i] * \
            (mid_i - left) - (s[mid_i] - s[left]);
            
            long long s_right = (s[right+1] - s[mid_i+1]) - \
            (long long)nums[mid_i] * (right - mid_i);

            return s_left + s_right;
        };
        //滑动窗口,枚举右端点,找左端点
        int left = 0;
        int ans = 0;
        for(int right = 0; right < sz; right++)
        {
        
            while(distance_sum(left,right) > k) 
            	left++;
            	
            ans = max(ans,right - left + 1);
        }
        return ans;
    }
};

总结

  • 所用算法知识:
  1. 排序
  2. 中位数
  3. 回文数
  4. 滑动窗口
  5. 前缀和

?每周的周赛总结,今天就到这里了,我是舜华,期待与你的下一次相遇!

文章来源:https://blog.csdn.net/Shun_Hua/article/details/135047764
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。