Leetcode每日一题周汇总 (12.24-12.30)

Leetcode每日一题周汇总 (12.24-12.30)

1.Sunday (12.24)

题目链接：1954. 收集足够苹果的最小花园周长 - 力扣（LeetCode）

题目描述：

给你一个用无限二维网格表示的花园，每一个 整数坐标处都有一棵苹果树。整数坐标 (i, j) 处的苹果树有 |i| + |j| 个苹果。

你将会买下正中心坐标是 (0, 0) 的一块 正方形土地 ，且每条边都与两条坐标轴之一平行。

给你一个整数 neededApples ，请你返回土地的 最小周长 ，使得 至少 有 neededApples 个苹果在土地 里面或者边缘上。

|x| 的值定义为：

• 如果 x >= 0 ，那么值为 x
• 如果 x < 0 ，那么值为 -x

示例 1：

输入：neededApples = 1
输出：8
解释：边长长度为 1 的正方形不包含任何苹果。
但是边长为 2 的正方形包含 12 个苹果（如上图所示）。
周长为 2 * 4 = 8 。

示例 2：

输入：neededApples = 13
输出：16

示例 3：

输入：neededApples = 1000000000
输出：5040

提示：

• 1 <= neededApples <= 10^15

解题代码：

class Solution {
public:
  long long minimumPerimeter(long long neededApples) {
?    long long ret=0;
?    long long pre=0;
?        while(1){
?          if(pre+12*ret*ret>=neededApples){
?            return ret*8;
?          }
?          pre+=12*ret*ret;
?          ret++;
?        }
  }
};

解题思路：

我们对于第n层，我们能够计算出它的周长为8n，正好对应8n个苹果点位，我们通过规律可以发现，每一个点位的苹果数量最少值正好为n，总共为8n^{2，而每一层又可以被x，y轴以及4个顶点平分为8条线段，每条线段上的苹果数量，都是n加上一个等差数列，每个等差数列正好是从0加到n，8个等差数列的和通过公式可以得出是，4n}2+4n，而因为计算每条线段时端点都被计算了一次，实际上，只需要计算4次，所以再减去4n，那么可以得出每一层的苹果的数量，数量是12n^2，那么，我们从第一层开始累加当大于指定的苹果数量时即停止，得出的答案即为最终结果。

2.Monday(12.25)

题目来源：1276. 不浪费原料的汉堡制作方案 - 力扣（LeetCode）

题目描述：

圣诞活动预热开始啦，汉堡店推出了全新的汉堡套餐。为了避免浪费原料，请你帮他们制定合适的制作计划。

给你两个整数 tomatoSlices 和 cheeseSlices，分别表示番茄片和奶酪片的数目。不同汉堡的原料搭配如下：

• **巨无霸汉堡：**4 片番茄和 1 片奶酪
• **小皇堡：**2 片番茄和 1 片奶酪

请你以 [total_jumbo, total_small]（[巨无霸汉堡总数，小皇堡总数]）的格式返回恰当的制作方案，使得剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量都是 0。

如果无法使剩下的番茄片 tomatoSlices 和奶酪片 cheeseSlices 的数量为 0，就请返回 []。

示例 1：

输入：tomatoSlices = 16, cheeseSlices = 7
输出：[1,6]
解释：制作 1 个巨无霸汉堡和 6 个小皇堡需要 4*1 + 2*6 = 16 片番茄和 1 + 6 = 7 片奶酪。不会剩下原料。

示例 2：

输入：tomatoSlices = 17, cheeseSlices = 4
输出：[]
解释：只制作小皇堡和巨无霸汉堡无法用光全部原料。

示例 3：

输入：tomatoSlices = 4, cheeseSlices = 17
输出：[]
解释：制作 1 个巨无霸汉堡会剩下 16 片奶酪，制作 2 个小皇堡会剩下 15 片奶酪。

示例 4：

输入：tomatoSlices = 0, cheeseSlices = 0
输出：[0,0]

示例 5：

输入：tomatoSlices = 2, cheeseSlices = 1
输出：[0,1]

提示：

• 0 <= tomatoSlices <= 10^7
• 0 <= cheeseSlices <= 10^7

解题代码：

class Solution {
public:
  vector<int> numOfBurgers(int tomatoSlices, int cheeseSlices) {
?      vector<int>v;
?        if((tomatoSlices-cheeseSlices*2)%2==0){
?          int x1=(tomatoSlices-cheeseSlices*2)/2;
?          int x2=cheeseSlices-x1;
?           if(x1>=0&&x2>=0){
?            v.push_back(x1);
?            v.push_back(x2);
?        }
?        }       
?        return v;
  }
};

解题思路：

本题可以用数学方法解决，联立方程解出X1和X2的表达式，如果两个解均大于等于零，并且为整数，即说明为正确答案。

3.Tuesday (12.26)

题目来源：1349. 参加考试的最大学生数 - 力扣（LeetCode）

题目描述：

给你一个 m * n 的矩阵 seats 表示教室中的座位分布。如果座位是坏的（不可用），就用 '#' 表示；否则，用 '.' 表示。

学生可以看到左侧、右侧、左上、右上这四个方向上紧邻他的学生的答卷，但是看不到直接坐在他前面或者后面的学生的答卷。请你计算并返回该考场可以容纳的同时参加考试且无法作弊的 最大 学生人数。

学生必须坐在状况良好的座位上。

示例 1：

输入：seats = [["#",".","#","#",".","#"],
              [".","#","#","#","#","."],
              ["#",".","#","#",".","#"]]
输出：4
解释：教师可以让 4 个学生坐在可用的座位上，这样他们就无法在考试中作弊。 

示例 2：

输入：seats = [[".","#"],
              ["#","#"],
              ["#","."],
              ["#","#"],
              [".","#"]]
输出：3
解释：让所有学生坐在可用的座位上。

示例 3：

输入：seats = [["#",".",".",".","#"],
              [".","#",".","#","."],
              [".",".","#",".","."],
              [".","#",".","#","."],
              ["#",".",".",".","#"]]
输出：10
解释：让学生坐在第 1、3 和 5 列的可用座位上。 

提示：

• seats 只包含字符 '.' 和``'#'
• m == seats.length
• n == seats[i].length
• 1 <= m <= 8
• 1 <= n <= 8

解题代码：

class Solution {
public:
  int maxStudents(vector<vector<char>>& seats) {
?    int m=seats.size();
?    int n=seats[0].size();
?    int N=pow(2,n);
?    vector<vector<int>> dp(m+1,vector<int>(N)); 
?    for(int i=1;i<=m;i++){
?      for(int j=0;j<N;j++){
?        bitset<8>bt(j);
?        bool ok=true;
?        for(int k=0;k<n;k++){
?          if((bt[k]&&seats[i-1][k]=='#')||(k+1<n&&bt[k]&&bt[k+1])){
?            ok=false;
?            break;
?          }
?        }
?        if(!ok){
?          dp[i][j]=-1;
?          continue;
?        }
?        else{
?          for(int k=0;k<N;k++){
?            if(dp[i-1][k]==-1){
?              continue;
?            }
?            bitset<8>last(k);
?            bool flag=true;
?            for(int q=0;q<n;q++){
?              if((q>0&&last[q]&&bt[q-1])||(q+1<n&&last[q]&&bt[q+1])){
?                flag=false;
?                break;
?              }
?            }
?            if(flag){
?              dp[i][j]=max(dp[i][j],dp[i-1][k]+(int)bt.count());
?            }
?          }
?        }
?      }
?    }
?    int maxnum=0;
?    for(int i=0;i<N;i++){
?      if(dp[m][i]>maxnum){
?        maxnum=dp[m][i];
?      }
?    }
?    return maxnum;
  }
};

解题思路：

这段代码是用来解决一个问题：在一个教室中，有些座位被占用，我们需要找出最多可以坐多少学生，同时满足以下条件：每个学生必须坐在一个空的座位上，且这个座位周围（前、后、左、右、左上、右上、左下、右下）都没有其他学生。

这个问题是一个典型的动态规划问题，具体步骤如下：

1. 初始化变量：m 和 n 分别表示教室的行数和列数。N 是 2^n，表示每一行可能的座位状态（每个座位可能被占用或空着）。dp 是一个二维数组，dp[i][j] 表示前 i 行座位，第 i 行座位状态为 j 时，最多可以坐多少学生。
2. 遍历每一行，对于每一行的每一种座位状态，使用 bitset 将状态 j 转换为二进制表示。检查这种座位状态是否合法（即没有相邻的学生，也没有学生坐在被占用的座位上）。如果不合法，dp[i][j] 被设置为 -1，然后跳过这种状态。如果合法，就需要找出第 i-1 行的座位状态，使得第 i 行和第 i-1 行的座位状态都合法，且 i 行的学生数量最多。
3. 遍历 dp[m]，找出最大值，即最多可以坐多少学生。

这个算法的时间复杂度是 O(m * 2^n * 2^n)，空间复杂度是 O(m * 2^n)，其中 m 是行数，n 是列数。

下面是一些更细节的讲解：

这段代码主要用了动态规划和位编码的算法，我们用编码可以快速的计算这种坐法是否合理。

我们可以首先得知，如果一行有八个座位，那么，每种座位只有两种情况，0与1，那么总共就有二的八次方种情况，而我们把0看成没坐，1看成已经有坐，那么，我们通过遍历0到2的八次方中的每一种结果，即可判断所有操作情况是否合理。我们可以通过位运算，如果两个未编码的与运算，得到的结果如果为零，则说明可行，如果不为零，就说明其中有两位都为1，那么一定是冲突的。而对于dp，如果对于某一种不可行的状态，他把它赋值为-1，下次可跳过这种情况，而当他找到一种可行的状态的时候，他会遍历他的上一行的所有状态中可行的状态，我们可以发现，座位的坐法只有前面的那一排会影响到后面相邻的那一排，除此之外，都不会影响。因此，当某一排m的座位遍历至一种情况时时，在这种情况下，前面的m-1排的最大座位总量，也一定是这一排m的下一排m+1排针对前面那0到m-1排的最大座位量，所以在每一个dp，我们只用保留前面的所有座位的最大值加上当前状态的座位数，dp[ i ] [ j ]中保存的是当前i排的一种状态j下的座位最多数量，这样能确保在下一层进行遍历时仍然符合该规定，最后，我们只用遍历最后一排的所有情况，找出最大值即可。

4.Wednesday (12.27)

题目来源：2660. 保龄球游戏的获胜者 - 力扣（LeetCode）

题目描述：

给你两个下标从 0 开始的整数数组 player1 和 player2 ，分别表示玩家 1 和玩家 2 击中的瓶数。

保龄球比赛由 n 轮组成，每轮的瓶数恰好为 10 。

假设玩家在第 i 轮中击中 xi 个瓶子。玩家第 i 轮的价值为：

• 如果玩家在该轮的前两轮的任何一轮中击中了 10 个瓶子，则为 2xi 。
• 否则，为 xi 。

玩家的得分是其 n 轮价值的总和。

返回

• 如果玩家 1 的得分高于玩家 2 的得分，则为 1 ；
• 如果玩家 2 的得分高于玩家 1 的得分，则为 2 ；
• 如果平局，则为 0 。

示例 1：

输入：player1 = [4,10,7,9], player2 = [6,5,2,3]
输出：1
解释：player1 的得分是 4 + 10 + 2*7 + 2*9 = 46 。
player2 的得分是 6 + 5 + 2 + 3 = 16 。
player1 的得分高于 player2 的得分，所以 play1 在比赛中获胜，答案为 1 。

解题代码：

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){
?        if(player1[0]==10){
?          sum1+=player1[i];
?        }
?        sum1+=player1[i];
?      }
?      else if(i>1){
?        if(player1[i-1]==10||player1[i-2]==10){
?          sum1+=player1[i];
?        }
?        sum1+=player1[i];
?      }
?      else{
?        sum1+=player1[i];
?      }
?    }
?    for(int i=0;i<player2.size();i++){
?      if(i==1){
?        if(player2[0]==10){
?          sum2+=player2[i];
?        }
?        sum2+=player2[i];
?      }
?      else if(i>1){
?        if(player2[i-1]==10||player2[i-2]==10){
?          sum2+=player2[i];
?        }
?        sum2+=player2[i];
?      }
?      else{
?        sum2+=player2[i];
?      }
?    }
?    if(sum1>sum2){
?      return 1;
?    }
?    else if(sum1==sum2){
?      return 0;
?    }
?    else return 2;
  }
};

解题思路：

本题遍历两次，针对不同情况计算不同得分，即可得到答案。

5.Thursday(12.28)

题目来源：2735. 收集巧克力 - 力扣（LeetCode）

题目描述：

给你一个长度为 n、下标从 0 开始的整数数组 nums，nums[i] 表示收集位于下标 i 处的巧克力成本。每个巧克力都对应一个不同的类型，最初，位于下标 i 的巧克力就对应第 i 个类型。

在一步操作中，你可以用成本 x 执行下述行为：

• 同时修改所有巧克力的类型，将巧克力的类型 ith 修改为类型 ((i + 1) mod n)th。

假设你可以执行任意次操作，请返回收集所有类型巧克力所需的最小成本。

示例 1：

输入：nums = [20,1,15], x = 5
输出：13
解释：最开始，巧克力的类型分别是 [0,1,2] 。我们可以用成本 1 购买第 1 个类型的巧克力。
接着，我们用成本 5 执行一次操作，巧克力的类型变更为 [1,2,0] 。我们可以用成本 1 购买第 2 个类型的巧克力。
然后，我们用成本 5 执行一次操作，巧克力的类型变更为 [2,0,1] 。我们可以用成本 1 购买第 0 个类型的巧克力。
因此，收集所有类型的巧克力需要的总成本是 (1 + 5 + 1 + 5 + 1) = 13 。可以证明这是一种最优方案。

示例 2：

输入：nums = [1,2,3], x = 4
输出：6
解释：我们将会按最初的成本收集全部三个类型的巧克力，而不需执行任何操作。因此，收集所有类型的巧克力需要的总成本是 1 + 2 + 3 = 6 。

解题代码：

class Solution {
public:
  long long minCost(vector<int>& nums, int x) {
?    int n=nums.size();
?    vector<int>v(nums.begin(),nums.end());
?    long long ans=accumulate(v.begin(),v.end(),0LL);
?    for(int k=1;k<n;k++){
?      for(int i=0;i<n;i++){
?        v[i]=min(v[i],nums[(i+k)%n]);
?      }
?      ans=min(ans,accumulate(v.begin(),v.end(),0LL)+(long long)k*x);
?    }
?    return ans;
  }
};

解题思路：

我们可以很容易的知道，当操作k次之后，所有的价钱都会回归原点，而中途还要额外产生操作的费用。所以正确答案一定在0次操作一直到k-1次操作之间，我们可以首先计算出需要的总成本，然后开始遍历第1次和第k- 1次之间的所有结果，在每一次操作时，我们都会把所有的巧克力遍历一次。注意，在本题的理解上，有一些误区，问题要得出最小的成本，而不是这0次和k-1次操作之间每一次操作成本总和中的最小值，我们可以先购买其中的一部分，在之后的操作中，再逐渐购买经过操作后成本下降的那一部分。因此，对于每一个巧克力，我们一定都是以最优的成本来购买它，那么这个价钱一定也是他的所有可能成本中最小的，所以我们不需要来频繁的记录它的下标和它的购买状态，我们只用每一次比对最小值，如果该值不是最小值，那么它会被替换，如果他已经是一个最优解，那么其他的解自然也不可能对它造成影响，当然，在每一次比对完一种情况之后，我们再次更新总成本即可。

6.Friday(12.29)

题目来源：2706. 购买两块巧克力 - 力扣（LeetCode）

题目描述：

给你一个整数数组 prices ，它表示一个商店里若干巧克力的价格。同时给你一个整数 money ，表示你一开始拥有的钱数。

你必须购买 恰好 两块巧克力，而且剩余的钱数必须是 非负数 。同时你想最小化购买两块巧克力的总花费。

请你返回在购买两块巧克力后，最多能剩下多少钱。如果购买任意两块巧克力都超过了你拥有的钱，请你返回 money 。注意剩余钱数必须是非负数。

示例 1：

输入：prices = [1,2,2], money = 3
输出：0
解释：分别购买价格为 1 和 2 的巧克力。你剩下 3 - 3 = 0 块钱。所以我们返回 0 。

示例 2：

输入：prices = [3,2,3], money = 3
输出：3
解释：购买任意 2 块巧克力都会超过你拥有的钱数，所以我们返回 3 。

解题代码：

class Solution {
public:
  int buyChoco(vector<int>& prices, int money) {
?    priority_queue<int, vector<int>, greater<int>> q;
?    for(int i=0;i<prices.size();i++){
?      q.push(prices[i]);
?    }
?    int a1=q.top();
?    q.pop();
?    int a2=q.top();
?    int ret=money-a1-a2;
?    if(ret>=0){
?      return ret;
?    }
?    else return money;
  }
};

解题思路：

本题可以通过一个优先队列来简化代码行数，通过计算最小的两块巧克力的总价钱，来判断答案即可。

7.Saturday(12.30)

题目来源：1185. 一周中的第几天 - 力扣（LeetCode）

题目描述：

给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。

输入为三个整数：day、month 和 year，分别表示日、月、年。

您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。

示例 1：

输入：day = 31, month = 8, year = 2019
输出："Saturday"

提示：

• 给出的日期一定是在 1971 到 2100 年之间的有效日期。

解题代码：

class Solution {
public:
  string dayOfTheWeek(int day, int month, int year) {
?    int sum=0;
?      for(int i=1971;i<=year-1;i++){
?        if((i%4==0&&i%100!=0)||(i%400==0)){
?          sum+=366;
?        }
?        else{
?          sum+=365;
?        }
?      }
?      for(int i=1;i<=month-1;i++){
?        if(i==1||i==3||i==5||i==7||i==8||i==10||i==12){
?          sum+=31;
?        }
?        else if(i==2){
?          if((year%4==0&&year%100!=0)||(year%400==0)){
?          sum+=29;
?        }
?        else{
?          sum+=28;
?        }
?        }
?        else{
?          sum+=30;
?        }
?      }
?      sum+=day;
?      int k=(4+sum)%7;
?      string str;
?      if(k==1){
?        str="Monday";
?      }
?      else if(k==2){
?        str="Tuesday";
?      }
?      else if(k==3){
?        str="Wednesday";
?      }
?      else if(k==4){
?        str="Thursday";
?      }
?      else if(k==5){
?        str="Friday";
?      }
?      else if(k==6){
?        str="Saturday";
?      }
?      else{
?        str="Sunday";
?      }
?      return str;
  }
};

解题思路：

本题可以通过查阅日历，得出一个基准值，然后经过遍历计算，即可得到答案，当然也可以通过用一个字符串数组来简化代码行数。