《九日集训》第十五轮 (第六讲) 贪心
2022/4/3 0:07:09
本文主要是介绍《九日集训》第十五轮 (第六讲) 贪心,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
知识点
贪心
题目分析
题目1
1913. 两个数对之间的最大乘积差
分析
两个最大的数减去最小的两个数就行了
代码
class Solution { public: int maxProductDifference(vector<int>& nums) { int max1=0,max2=0,min1=INT_MAX,min2=INT_MAX; for(auto num:nums){ if(max1<num){ max2=max1; max1=num; }else if(max2<num){ max2=num; } if(min1>num){ min2=min1; min1=num; }else if(min2>num){ min2=num; } } return max2*max1-min1*min2; } };
题目2
976. 三角形的最大周长
分析
昨天刷过了qwq
代码
class Solution { public: int largestPerimeter(vector<int>& nums) { sort(nums.begin(),nums.end()); for(int i=nums.size()-1;i>=2;i--){ if(nums[i]<nums[i-1]+nums[i-2])return nums[i]+nums[i-1]+nums[i-2]; } return 0; } };
题目3
561. 数组拆分 I
分析
把大的和大的取最小值,小的和小的取最小值总和才是最大。也就是先排序,然后两两分组取最小值相加
代码
class Solution { public: int arrayPairSum(vector<int>& nums) { int sum=0; sort(nums.begin(),nums.end()); for(int i=0;i<nums.size();i+=2){ sum+=min(nums[i],nums[i+1]); } return sum; } };
题目4
881. 救生艇
分析
昨天刷过了qwq
代码
class Solution { public: int numRescueBoats(vector<int>& people, int limit) { int l=0,r=people.size()-1,res=0; sort(people.begin(),people.end()); while(l<=r){ if(people[l]+people[r]<=limit){ l++; r--; res++; }else if(people[l]>limit)return -1; else{ r--; res++; } } return res; } };
题目5
324. 摆动排序 II
分析
把数组排序分为大数和小数部分,然后穿插。用 \(O(n)\) 时间复杂度和 / 或原地 \(O(1)\) 额外空间想不到qwq,以后补票
代码
class Solution { public: void wiggleSort(vector<int>& nums) { vector<int>temp(nums.begin(),nums.end()); sort(temp.begin(),temp.end()); int r=nums.size()-1; for(int i=1;i<nums.size();i+=2){ nums[i]=temp[r--]; } for(int i=0;i<nums.size();i+=2) nums[i]=temp[r--]; } };
题目6
455. 分发饼干
分析
先排序一下,尽量用小的饼干满足小的孩子,可以满足孩子数加一,因为饼干只能用一次,而且如果不满足只能往下找,所以不管满不满足饼干都要加一
代码
class Solution { public: int findContentChildren(vector<int>& g, vector<int>& s) { sort(g.begin(),g.end()); sort(s.begin(),s.end()); int i=0,j=0;//i----小孩,j---饼干 while(i<g.size()&&j<s.size()){ if(s[j]>=g[i]){ i++; } j++; } return i; } };
题目7
1827. 最少操作使数组递增
分析
如果\(nums[n]>=nums[n-1]\)的话
\[nums[n]=nums[n-1]+c \]次数为c+1的总和
代码
class Solution { public: int minOperations(vector<int>& nums) { if(nums.size()==1)return 0; int res=0; for(int i=0;i<nums.size()-1;i++){ if(nums[i]>=nums[i+1]){ res+=nums[i]-nums[i+1]+1;//计算需要的次数 nums[i+1]=nums[i]+1;//改变nums[i+1]的值 } } return res; } };
题目8
945. 使数组唯一的最小增量
分析
先排序一下,然后判断$nums[i]\leq nums[i-1] \(是否为真,如果为真的话,总和为他们相减加上1之和。要记得把\)nums[i]$变成改变后的样子,思路和1827. 最少操作使数组递增差不多qwq
代码
class Solution { public: int minIncrementForUnique(vector<int>& nums) { sort(nums.begin(),nums.end()); int res=0; for(int i=1;i<nums.size();i++){ if(nums[i]<=nums[i-1]){ res+=nums[i-1]+1-nums[i]; nums[i]=nums[i-1]+1; } } return res; } };
题目9
611. 有效三角形的个数
分析
固定第一个数,然后枚举第二和第三个数,第二和第三个数之间的距离总和就是结果
代码
public: int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); int res=0; for(int i=0;i<nums.size();i++){ for(int j=i-1,k=0;j>0&&k<j;j--){ while(k<j&&nums[k]<=nums[i]-nums[j])k++; res+=j-k; } } return res; } };
总结
对贪心不熟练,还得多练一练qwq。写完碎觉( ̄▽ ̄)~*
这篇关于《九日集训》第十五轮 (第六讲) 贪心的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现