DAY37
先二刷昨天的3道题目,每种方法都写:是否已完成:是。
报告:134加油站的朴素法没写对。原因是:在if中缺少了store>=0的判断,只给出了index==i的判断。前进法没写出来。因为忘记了总油量的判断。Sum。注意变量的初始化。分配糖果注意if里面放的是ratings;
860柠檬水找零
网上摘得思路,看来我还是得冷静下来多想多模拟,最好把文字思路写下来,慢慢打磨:
思路:
- 遇10元要消耗5元数量,遇到20元可消耗10元和5元数量,由于要保证后面还可能需要5元
2. 那么,遇到20元时就要优先消耗10元的数量
- class Solution {
- public:
- bool lemonadeChange(vector<int>& bills) {
- int five=0,ten=0,twenty=0;
- for(int bill:bills){
- if(bill==5) five++;
- else if(bill==10){
- if(five==0) return false;
- five--,ten++;
- }
- else if(bill=20){
- if(ten>0&&five>0){
- ten--,five--,twenty++;
- }
- else if(five>=3){
- five-=3,twenty++;
- }
- else
- return false;
- }
- }
- return true;
- }
- };
406根据身高重建队列
想不出来,不知道该怎么模拟。
力扣博主Sunny的题解:
渔(套路):一般这种数对,还涉及排序的,根据第一个元素正向排序,根据第二个元素反向排序,或者根据第一个元素反向排序,根据第二个元素正向排序,往往能够简化解题过程。
在本题目中,我首先对数对进行排序,按照数对的元素 1 降序排序,按照数对的元素 2 升序排序。原因是,按照元素 1 进行降序排序,对于每个元素,在其之前的元素的个数,就是大于等于他的元素的数量,而按照第二个元素正向排序,我们希望 k 大的尽量在后面,减少插入操作的次数。
作者:Sunny
链接:https://leetcode.cn/problems/queue-reconstruction-by-height/solutions/486493/xian-pai-xu-zai-cha-dui-dong-hua-yan-shi-suan-fa-g/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
讲得非常好,我们自己编程实现一下:
不会语法。
很好,学到新东西了,尤其是重载pair类运算符,还有insert记得传入res.begin()的写法:
- class Solution {
- public:
- //注意person是vector<int> 不是pair.因为是对内部的元素排,而内部元素是vector<int>类型
- static bool mycmp(vector<int>&a,vector<int>&b){
- if(a[0]==b[0]) return a[1]<b[1];
- return a[0]>b[0];
- }
- vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
- vector<vector<int>> res;
- sort(people.begin(),people.end(),mycmp);
- for(auto person:people){
- int size=(int)res.size();
- if(person[1]>=size)
- res.push_back(person);
- else
- res.insert(res.begin()+person[1],person);
- }
- return res;
- }
- };
学习代码随想录的解法:
引用:
“本题有两个维度,h和k,看到这种题目一定要想如何确定一个维度,然后再按照另一个维度重新排列。在135. 分发糖果 (opens new window)我就强调过一次,遇到两个维度权衡的时候,一定要先确定一个维度,再确定另一个维度。”
思路一样的,但是讲解的话,力扣博主要更清晰易懂,以后优先看力扣博主的讲解,都吸收。
这里相当于再写一遍:
- class Solution {
- public:
- static bool mycmp(vector<int>&a,vector<int>&b){
- if(a[0]==b[0]) return a[1]<b[1];
- return a[0]>b[0];
- }
- vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
- vector<vector<int>> res;
- sort(people.begin(),people.end(),mycmp);
- for(auto person :people){
- int size=(int)(res.size());
- if(person[1]>=size) res.push_back(person);
- else res.insert(res.begin()+person[1],person);
- }
- return res;
- }
- };
还需要额外学习手写vector的insert操作:
- void insert(vector<int>& vec, int pos, int val) {
- // Check if the position is valid
- if (pos < 0 || pos > vec.size()) {
- throw invalid_argument("Position is out of range.");
- }
- // Increase the size of the vector
- vec.resize(vec.size() + 1);
- // Move the elements after the position to create space for the new element
- for (int i = vec.size() - 1; i > pos; i--) {
- vec[i] = vec[i - 1];
- }
- // Insert the new element
- vec[pos] = val;
- }
452用最少数量的箭引爆气球
本题考察区间合并,在ACWING学了模版,但是已经记不起来了,还是得多学多做多复习(显然不太可能,尽力吧):
还是写不出来区间合并。仔细读题,这题并不是单纯的区间合并
复习ACWING区间合并,学习记忆ACWING模版,力扣高赞题解,代码随想录题解、COZE的解法(主要还是要学会区间合并,COZE的解法并不能走天下)。已完成。
COZE:
注意先sort再去取end;
- class Solution {
- public:
- static bool mycmp(vector<int>&a,vector<int>&b){
- return a[1]<b[1];
- }
- int findMinArrowShots(vector<vector<int>>& points) {
- sort(points.begin(),points.end(),mycmp);
- int res=1,end=points[0][1];
- for(int i=1;i<points.size();i++){
- if(points[i][0]<=end) continue;
- res++;
- end=points[i][1];
- }
- return res;
- }
- };
Leetcode优质题解:
思路和上面一样:有交集就好,没交集就res++,并更新end;
代码随想录官方题解:
学到了:如果按左端点来排序,那么应当从后向前开始遍历。遇到重叠时候:重叠气球的最小右边界就是射箭地方。
- class Solution {
- public:
- static bool mycmp(vector<int>&a,vector<int>&b){
- return a[0]<b[0];
- }
- int findMinArrowShots(vector<vector<int>>& points) {
- int result=1;
- sort(points.begin(),points.end(),mycmp);
- for(int i=1;i<points.size();i++){
- //不重叠
- if(points[i][0]>points[i-1][1]){
- result++;
- }
- //重叠
- else{
- points[i][1]=min(points[i][1],points[i-1][1]);
- }
- }
- return result;
- }
- };
ACWING803区间合并
有很多细节:-2e9,注意负号的位置。
- #include<iostream>
- #include<vector>
- #include<algorithm>
- using namespace std;
- const int N=100010;
- typedef pair<int,int> PII;
- vector<PII> segs;
- //看一下const N怎么用的?
- void mymerge(vector<PII>&segs){
- sort(segs.begin(),segs.end());
- vector<PII> res;
- int st=-2e9,ed=-2e9;
- for(auto seg:segs){
- //无交集
- if(ed<seg.first){
- if(st!=-2e9) res.push_back({st,ed});
- st=seg.first,ed=seg.second;
- }
- //有交集
- else{
- ed=max(seg.second,ed);
- }
- }
- //防止空区间进入
- if(st!=-2e9) res.push_back({st,ed});
- segs=res;
- }
- int main(){
- int n;
- scanf("%d",&n);
- while(n--){
- int l,r;
- scanf("%d%d",&l,&r);
- segs.push_back({l,r});
- }
- mymerge(segs);
- printf("%d\n",segs.size());
- return 0;
- }
学习贪心算法:
来源:
[一个视频搞懂贪心算法]
(https://www.bilibili.com/video/BV1Hz4y117CP/?share_source=copy_web&vd_source=20ecc36fbdd0ac45969ae149b0333409)
- 分配问题。
分配饼干,因为饥饿度最小的孩子最容易吃饱,先考虑他。
做过了。
- 区间问题-Leetcode435 无重叠区间
在选择要保留区间时,区间的结尾十分重要:选择的区间结尾越小,余留给其它区间的空间就越大,就越能保留更多的区间。
因此,我们采取的贪心策略为,优先保留结尾小且不相交的区 间。具体实现方法为,先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选 择的区间不重叠的区间。
给定多个区间,计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。
- class Solution {
- public:
- static bool mycmp(vector<int>&a,vector<int>&b){
- return a[1]<b[1];
- }
- int eraseOverlapIntervals(vector<vector<int>>& intervals) {
- int remove=0;
- sort(intervals.begin(),intervals.end(),mycmp);
- int end=intervals[0][1];
- for(int i=1;i<intervals.size();i++){
- if(intervals[i][0]<end) {
- remove++;
- continue;
- }
- end=intervals[i][1];
- }
- return remove;
- }
- };
做出来了!不会也别怕,做过类似的就增长能力了,下次就能举一反三。
- 买卖股票的最佳时机 Leetcode121,简单
又不会了,因为当时没彻底弄懂吧。
朴素法,超时了:
- class Solution {
- public:
- int maxProfit(vector<int>& prices) {
- int res=INT_MIN;
- for(int i=0;i<prices.size()-1;i++){
- int j=i+1;
- while(j<prices.size()){
- int tmp=prices[j]-prices[i];
- if(tmp>res) res=tmp;
- j++;
- }
- }
- if(res<0) return 0;
- return res;
- }
- };
动态规划:画图!
- class Solution {
- public:
- int maxProfit(vector<int>& prices) {
- int pastprice=INT_MAX,res=0;
- for(int price:prices){
- res=max(res,price-pastprice);
- pastprice=min(price,pastprice);
- }
- return res;
- }
- };
- 买卖股票的最佳时机ii,中等
画图发现,[1,4,6]不管是{1买入,4卖出;4买入,6卖出}还是{1买入,6卖出}结果一样,所以每日res>0的话就加入到结果中:如果今天买明天卖能赚钱,那么就今天买入。
- class Solution {
- public:
- int maxProfit(vector<int>& prices) {
- if(prices.size()==1) return 0;
- int pro=0;
- for(int i=1;i<prices.size();i++){
- int res=prices[i]-prices[i-1];
- if(res>0) pro+=res;
- }
- return pro;
- }
- };