【每日一题】【12.24】 - 【12.28】

2023-12-28 17:04:01

🔥博客主页:?A_SHOWY
🎥系列专栏力扣刷题总结录?数据结构??云计算??数字图像处理??力扣每日一题_

本周总结:本周的每日一题比较针对于数学问题的一个应用,如二元一次方程组的求解或者数组求和,同时long long 的统一问题防止出界在这周题目中经常出现。还有当Sn随着n单调时降低时间复杂度要考虑二分法,当有限次数出现循环的时候考虑枚举方法。

?【12.24】1954. 收集足够苹果的最小花园周长

1954. 收集足够苹果的最小花园周长icon-default.png?t=N7T8https://leetcode.cn/problems/minimum-garden-perimeter-to-collect-enough-apples/

虽然是一道mid题目,但是其实又是一个数学题目,可以利用枚举,看什么时候总数值比这个needapples大,返回周长就可以。?

方法一:枚举?

上图是我自己的求这个当右上角设置为(n,n)时,苹果总数的方法,因为这个x轴和y轴坐标是对称的,所以可以求一个*2就可以,先求和公式算半边和乘2,然后注意一共有(2n+1)个边长。?

class Solution {
public:
    long long minimumPerimeter(long long neededApples) {
        long long n = 1;
        for(; 2 * n*(n + 1) * (2 * n + 1) < neededApples; ++n);
    return n * 8;//返回周长
    }
};

方法二:二分法

?由于Sn跟着n是单调递增的,所以联系方法1,可以使用二分法降低时间复杂度(logm).right值可以使用最大值开三次方根,也可以直接设置一个很大的数即可。常用的二分法模板要熟练,值得注意的是long long出界问题。

class Solution {
public:
    long long minimumPerimeter(long long neededApples) {
    long long int left = 0, right = 1000000, ans = 0;
    while(left <= right){
        long long  mid = left + ((right - left) / 2);
        if(mid * (mid + 1) * 2 *(2 * mid + 1) >= neededApples){
            ans = mid;
            right = mid -1;
        }
        else {
            left = mid + 1; 
        }
    } 
    return ans * 8;
    }
};

?【12.25】 1276.不浪费原料的汉堡制作方案?

1276. 不浪费原料的汉堡制作方案icon-default.png?t=N7T8https://leetcode.cn/problems/number-of-burgers-with-no-waste-of-ingredients/

是一道mid题,但是思路比较简单是个数学的求解二元一次方程组的数学问题,注意自变量范围即可

1. 设巨无霸汉堡有?x?个,皇堡有?y?个,由于所有的材料都需要用完,因此我们可以得到

二元一次方程组:
4x + 2y = tomatoSlices
x + y = cheeseSlices

?2.可以求解得到

 x= 1/2 * tomatoSlices ? cheeseSlices
 y=2 * cheeseSlices? 1/2 * tomatoSlices

3.根据题意,x>=0 y>=0因此需要满足

tomatoSlices = 2k,k∈N
tomatoSlices ≥ 2 * cheeseSlices
4 * cheeseSlices ≥ tomatoSlices
?

就是不满足题意返回空,满足题意返回方程求解的值所以直接写:

class Solution {
public:
    vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
        if(tomatoSlices %2 != 0 || tomatoSlices < 2 * cheeseSlices || tomatoSlices > 4 * cheeseSlices) return{};
        return{tomatoSlices /2 - cheeseSlices,2 * cheeseSlices - tomatoSlices/2};
    }
};

【12.27】 2660.保龄球游戏的获胜者

2660. 保龄球游戏的获胜者icon-default.png?t=N7T8https://leetcode.cn/problems/determine-the-winner-of-a-bowling-game/

比较简单的模拟题目,注意审题,是前两轮都要判断是否是10,同时要注意越界的问题?

class Solution {
public:
    int isWinner(vector<int>& player1, vector<int>& player2) {
        int sum1 = 0;
        int sum2 = 0;
        for(int i = 0; i < player1.size();i++)
        {
            if((i >= 1 && player1[i-1] == 10)||(i >= 2 &&player1[i-2] ==10)) sum1 += player1[i] *2;
            else sum1  += player1[i];
        }
        for(int j = 0; j < player2.size();j++)
        {
            if((j >= 1 && player2[j-1] == 10)||(j >= 2 &&player2[j-2] ==10)) sum2 += player2[j] *2;
            else sum2  += player2[j];
        }
        if(sum1 > sum2) return 1;
        else if(sum1 == sum2) return 0;
        else return 2;
    }
};

【12.28】 2735.收集巧克力

2735. 收集巧克力icon-default.png?t=N7T8https://leetcode.cn/problems/collecting-chocolates/

今天的题目是稍微有一些难度的题目,可以说是一个动态规划有关的枚举题目,思路比较难想,同时还要注意越界的问题。整体思路不那么想好,而且难度比较大。

1.大概意思就是有个价格盘nums,初始情况下[0,n?1]]类的巧克力价格对应着nums[0]到nums[n?1],可以把巧克力看成是排在了一个传送带上,旋转一次传送带的代价是x,巧克力iii将以旋转后对齐的nums值回收掉,问回收所有巧克力的最小代价。

2.很显然,最多旋转n?1次传送带,因为旋转nnn次相当于什么都没干,再增大旋转次数也是在重复这个模式,因此我们枚举旋转次数即可。预处理出cost数组,其中cost[i][j]表示巧克力iii在旋转j次时被回收的代价。

3.我们就可以枚举操作次数了,它的范围为 [0,n?1]。当操作次数为 k 时,初始类型为 i?的巧克力需要的成本就是最小值,我们就可以使用一个二维数组 f(i,k) 记录该值,它有如下的递推式:

f(i,0) = nums[i]
f(i,k) = min{f(i,k?1),nums[(i+k) mod n]}
?

即 f(i,k)相较于 f(i,k?1),多了一个 nums[(i+k)?mod?n 的选择

class Solution {
public:
    long long minCost(vector<int>& nums, int x) {
    int n = nums.size();
     vector<int>  f(nums);
    long long  ans = accumulate(f.begin(),f.end(),0LL);
   
    for(int k = 1; k < n; ++k){//k表示的是旋转多少次
        for(int i = 0; i< n; ++i){//i表示的是每一个巧克力
            f[i] = min(f[i],nums[(i+k) % n]);
        }
            ans = min(ans,  k *static_cast<long long> (x) + accumulate(f.begin(),f.end(),0LL));
    }
return ans;
    }
};

4.同时要注意越界问题,一直是long long,在最后算ans的时候,k或者x要通过static_cast转换成long long形式。accumulate用于计算数组或者容器类的元素总和。

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