您现在的位置是：首页 >技术杂谈 >【力扣周赛】第342场周赛网站首页技术杂谈

【力扣周赛】第342场周赛

雾里看花花里看雾 2023-06-08 04:00:04
简介【力扣周赛】第342场周赛

【力扣周赛】第342场周赛

6387：计算列车到站时间

题目描述

描述：给你一个正整数 arrivalTime 表示列车正点到站的时间（单位：小时），另给你一个正整数 delayedTime 表示列车延误的小时数。

返回列车实际到站的时间。

注意，该问题中的时间采用 24 小时制。

输入： arrivalTime = 15, delayedTime = 5 
输入： 20 
解释：列车正确点到站时间是15:00，延错5小时，所以列车实际到站的时间是15 + 5 = 20（20:00）。

输入： arrivalTime = 13, delayedTime = 11
输入： 0
解释：列车正确点到站时间是 13:00 ，延错 11 点钟，所以列车实际到站的时间是 13 + 11 = 24（在中楶桶 24 00 :00 ，所以返回 0）。

1 <= arrivaltime < 24
1 <= delayedTime <= 24

解题思路

思路：使用列车正点到站时间arrivalTime与列车延误小时数delayedTime相加再模以24即可。

    int findDelayedArrivalTime(int arrivalTime, int delayedTime) {
        return (arrivalTime+delayedTime)%24;
    }

6391：倍数求和

题目描述

描述：给你一个正确的整数n，请你计算在[1，n]范围内能被3、5、7整除的所有整数之和。

返回一个整数，用于表示给定范围内所有满足约条件的数字之和。

输入： n = 7
输入： 21
解释：在[1, 7]范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7。数字之和为21。

输入： n = 10
输入： 40
解释：在[1, 10]范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9、10。数字之和为40。

输入： n = 9
输入： 30
解释：在[1, 9]范围内能被 3、5、7 整除的所有整数分别是 3、5、6、7、9。数字之和为30。

1 <= n <= 103

解题思路

思路：使用res记录结果，初始化为0，从1遍历到n，判断i%3==0或者i%5==0或者i%7==0，如果是则将i加入res。

 int sumOfMultiples(int n) {
        int res=0;
        for(int i=3;i<=n;i++)
            if(i%3==0||i%5==0||i%7==0)
                res+=i;
        return res;
    }

6390：滑动子数组的美丽值

题目描述

描述：给你一个长度为 n 的整数数组 nums ，请你求出每个长度为 k 的子数组的 美丽值 。

一个子数组的 美丽值 定义为：如果子数组中第 x 小整数 是 负数 ，那么美丽值为第 x 小的数，否则美丽值为 0 。

请你返回一个包含 n - k + 1 个整数的数组，依次 表示数组中从第一个下标开始，每个长度为 k 的子数组的 美丽值 。

子数组指的是数组中一段连续 非空 的元素序列。

输入：nums = [1,-1,-3,-2,3], k = 3, x = 2
输出：[-1,-2,-2]
解释：总共有 3 个 k = 3 的子数组。
第一个子数组是 [1, -1, -3] ，第二小的数是负数 -1 。
第二个子数组是 [-1, -3, -2] ，第二小的数是负数 -2 。
第三个子数组是 [-3, -2, 3] ，第二小的数是负数 -2 。

输入：nums = [-1,-2,-3,-4,-5], k = 2, x = 2
输出：[-1,-2,-3,-4]
解释：总共有 4 个 k = 2 的子数组。
[-1, -2] 中第二小的数是负数 -1 。
[-2, -3] 中第二小的数是负数 -2 。
[-3, -4] 中第二小的数是负数 -3 。
[-4, -5] 中第二小的数是负数 -4 。

输入：nums = [-3,1,2,-3,0,-3], k = 2, x = 1
输出：[-3,0,-3,-3,-3]
解释：总共有 5 个 k = 2 的子数组。
[-3, 1] 中最小的数是负数 -3 。
[1, 2] 中最小的数不是负数，所以美丽值为 0 。
[2, -3] 中最小的数是负数 -3 。
[-3, 0] 中最小的数是负数 -3 。
[0, -3] 中最小的数是负数 -3 。

n == nums.length
1 <= n <= 105
1 <= k <= n
1 <= x <= k
-50 <= nums[i] <= 50

解题思路

思路：遍历滑动窗口，使用i表示滑动窗口起始值，使用j表示滑动窗口元素下标，窗口大小为k，使用优先队列存储长度为x的大根堆，其中第x小的元素即长度为x的大根堆的堆顶元素。具体做法如下：当堆的大小小于x时将当前元素压入堆，反之当堆的大小等于x时，判断当前元素与堆顶元素的关系，如果当前元素小于堆顶元素，则弹出堆顶元素，再压入当前元素，遍历完一个窗口后，判断堆顶元素是否小于0，如果是则加入堆顶元素到结果数组res中，反之加入0。（超时）

vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        int n=nums.size();
        vector<int> res;
        for(int i=0;i<n&&i+k-1<n;i++)
        {
            priority_queue<int> pq;  //长度为x的优先级队列 大根堆 第x小
            for(int j=i;j<i+k&&j<n;j++)
            {
                if(pq.size()==x) //长度等于x判断当前元素和堆顶关系
                {
                    if(nums[j]<pq.top()) //如果当前元素小于堆顶元素 弹出堆顶元素 压入当前元素
                    {
                        pq.pop();
                        pq.push(nums[j]);
                    }
                }
                else if(pq.size()<x) //长度小于x压入堆
                    pq.push(nums[j]);
            }
            if(pq.top()<0)
                res.push_back(pq.top());
            else
                res.push_back(0);
        }
        return res;
    }

int get_min(deque<int> dq,int x)
    {
        priority_queue<int> pq;
        int temp;
        while(dq.size()) //注意dq.size()在不断变化
        {
            temp=dq.front();
            if(pq.size()==x)
            {
                if(temp<pq.top())
                {
                    pq.pop();
                    pq.push(temp);
                }
            }
            else if(pq.size()<x)
                pq.push(temp);
            dq.pop_front();
        }
        return pq.top();
    }
    vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
        int n=nums.size();
        vector<int> res;
        deque<int> dq;
        int minx;
        for(int i=0;i<n;i++)
        {
            dq.push_back(nums[i]);
            if(dq.size()==k)
            {
                minx=get_min(dq,x);
                if(minx<0)
                    res.push_back(minx);
                else
                    res.push_back(0);
                dq.pop_front();
            }
        }
        return res;
    }

上述方法都超时啦！！要想办法优化哇！！

优化：由于元素值范围为-50到50，所以可以使用一维数组记录元素值与元素个数的映射关系，因为存在负数，所以可以将整体元素值加以50，这样-50~50就转化为0~100，即可以创建一个长度为100的hash数组。具体实现方法是：首先记录第一个窗口的第x小的数值，其是遍历下标为0~49的hash数组，统计负数-50~-1的个数，如果对应个数大于等于x，则表明对应元素即为第x小的元素，返回i-50，反之第x小的元素不为负数，即返回0；接着遍历剩余的剩余窗口，每次将窗口中进一个元素出一个元素再求窗口内的第x小的数值。

int getMin(int hash[],int x)  //注意数组传参int hash[]
{
    int count=0; //记录负数出现的次数
    for(int i=0;i<=49;i++) //-50~-1对应0~49
    {
        count+=hash[i];
        if(count>=x)
           return i-50;
    }
    return 0; //没有则返回0
}
vector<int> getSubarrayBeauty(vector<int>& nums, int k, int x) {
    int n=nums.size();
    vector<int> res(n-k+1);
    int hash[101]={0}; //元素-元素个数 -50~50 将其元素值加50对应
    for(int i=0;i<k;i++) //统计第一个窗口元素个数
       hash[nums[i]+50]++;  
    res[0]=getMin(hash,x); //计算第一个窗口第x小值
    for(int i=k;i<n;i++)
    {
        hash[nums[i]+50]++; //进一个元素
        hash[nums[i-k]+50]--; //出一个元素
        res[i-k+1]=getMin(hash,x);
    }
    return res;
}

6392：使数组所有元素变成1的最少操作次数

题目描述

描述：给你一个下标从 0 开始的 正 整数数组 nums 。你可以对数组执行以下操作 任意 次：

选择一个满足 0 <= i < n - 1 的下标 i ，将 nums[i] 或者 nums[i+1] 两者之一替换成它们的最大公约数。
请你返回使数组 nums 中所有元素都等于 1 的 最少 操作次数。如果无法让数组全部变成 1 ，请你返回 -1 。

两个正整数的最大公约数指的是能整除这两个数的最大正整数。

输入：nums = [2,6,3,4]
输出：4
解释：我们可以执行以下操作：
- 选择下标 i = 2 ，将 nums[2] 替换为 gcd(3,4) = 1 ，得到 nums = [2,6,1,4] 。
- 选择下标 i = 1 ，将 nums[1] 替换为 gcd(6,1) = 1 ，得到 nums = [2,1,1,4] 。
- 选择下标 i = 0 ，将 nums[0] 替换为 gcd(2,1) = 1 ，得到 nums = [1,1,1,4] 。
- 选择下标 i = 2 ，将 nums[3] 替换为 gcd(1,4) = 1 ，得到 nums = [1,1,1,1] 。

输入：nums = [2,10,6,14]
输出：-1
解释：无法将所有元素都变成 1 。

2 <= nums.length <= 50
1 <= nums[i] <= 106

解题思路

使数组所有元素变成1的最少操作次数：最直观的想法是，分类讨论。如果数组元素中有1，则操作次数是n-cnt1次；如果所有元素的gcd大于1，那么无法将所有元素变成1，直接返回-1；如果元素中没有1，那么求长度最短的gcd为1的连续子数组的长度，首先将该子数组变出一个1，其需要min_size-1次，接着将其所有变成1，其需要n-1次，故一共min_size+n-2次。

int minOperations(vector<int>& nums) 
{
    int n=nums.size();
    int gcd_all=0; //当前所有元素的gcd值 0和任何为任何
    int cnt1=0; //1的个数
    for(int num:nums)
    {
       gcd_all=gcd(gcd_all,num); //记录所有元素的gcd
       cnt1+=num==1; //当当前元素为1记录
    }
    if(gcd_all>1) return -1; //所有gcd大于1不行
    if(cnt1) return n-cnt1; //元素中有1
    //元素中没1找gcd为1的连续子数组
    int min_size=n; //gcd为1的最短连续子数组
    for(int i=0;i<n;i++)
    {
        int g=0;
        for(int j=i;j<n;j++)
        {
           g=gcd(g,nums[j]);
           if(g==1)
           {
               min_size=min(min_size,j-i+1);
               break;
           }
        }
    }
    return min_size+n-2; //(min_size-1)+(n-1)
}

总结：C++中有gcd()函数，其求解两个数的gcd，即最大公约数。

风语者！平时喜欢研究各种技术，目前在从事后端开发工作，热爱生活、热爱工作。

站长推荐