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,总共为8n2,而每一层又可以被x,y轴以及4个顶点平分为8条线段,每条线段上的苹果数量,都是n加上一个等差数列,每个等差数列正好是从0加到n,8个等差数列的和通过公式可以得出是,4n2+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;
}
};
解题思路:
这段代码是用来解决一个问题:在一个教室中,有些座位被占用,我们需要找出最多可以坐多少学生,同时满足以下条件:每个学生必须坐在一个空的座位上,且这个座位周围(前、后、左、右、左上、右上、左下、右下)都没有其他学生。
这个问题是一个典型的动态规划问题,具体步骤如下:
- 初始化变量:
m
和n
分别表示教室的行数和列数。N
是2^n
,表示每一行可能的座位状态(每个座位可能被占用或空着)。dp
是一个二维数组,dp[i][j]
表示前i
行座位,第i
行座位状态为j
时,最多可以坐多少学生。 - 遍历每一行,对于每一行的每一种座位状态,使用
bitset
将状态j
转换为二进制表示。检查这种座位状态是否合法(即没有相邻的学生,也没有学生坐在被占用的座位上)。如果不合法,dp[i][j]
被设置为-1
,然后跳过这种状态。如果合法,就需要找出第i-1
行的座位状态,使得第i
行和第i-1
行的座位状态都合法,且i
行的学生数量最多。 - 遍历
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;
}
};
解题思路:
本题可以通过查阅日历,得出一个基准值,然后经过遍历计算,即可得到答案,当然也可以通过用一个字符串数组来简化代码行数。
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!