🔥博客主页： A_SHOWY
🎥系列专栏：力扣刷题总结录 数据结构 云计算 数字图像处理 力扣每日一题_
本周总结：本周的每日一题比较针对于数学问题的一个应用，如二元一次方程组的求解或者数组求和，同时long long 的统一问题防止出界在这周题目中经常出现。还有当Sn随着n单调时降低时间复杂度要考虑二分法，当有限次数出现循环的时候考虑枚举方法。
【12.24】1954. 收集足够苹果的最小花园周长
1954. 收集足够苹果的最小花园周长
https://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. 不浪费原料的汉堡制作方案https://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. 保龄球游戏的获胜者https://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. 收集巧克力https://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用于计算数组或者容器类的元素总和。
