当前位置：首页 > news >正文

day 10 贪心算法

news 来源：原创 2024/9/20 13:51:01

455. 分发饼干

饼干从大的开始利用，优先满足胃口大的；

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int res=0;int index=s.size()-1;for(int i=g.size()-1;i>=0;i--){if(index>=0&&s[index]>=g[i]) {//注意index不要越界,index的范围res+=1;index-=1;}}return res;}
};

另一种方法：

饼干从小的开始利用，优先满足胃口小的；

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {sort(g.begin(),g.end());sort(s.begin(),s.end());int index=0;int res=0;for(int i=0;i<s.size();i++){if(index<g.size()&&g[index]<=s[i]){res+=1;index+=1;}}return res;}
};

376. 摆动序列

class Solution {
public:int wiggleMaxLength(vector<int>& nums) {int res=1;if(nums.size()<=1) return nums.size();int pre=0;int cur=0;for(int i=0;i<nums.size()-1;i++){cur=nums[i+1]-nums[i];if((pre>=0&&cur<0)||(pre<=0&&cur>0)){res++;pre=cur;}}return res;}
};

53. 最大子数组和

class Solution {
public:int maxSubArray(vector<int>& nums) {int res=INT_MIN;int count=0;for(int i=0;i<nums.size();i++){count+=nums[i];if(count>res)res=count;if(count<0) count=0;}return res;}
};

122. 买卖股票的最佳时机 II

class Solution {
public:int maxProfit(vector<int>& prices) {int res=0;for(int i=0;i<prices.size()-1;i++){res+=max(prices[i+1]-prices[i],0);}return res;}
};

55. 跳跃游戏

class Solution {
public:bool canJump(vector<int>& nums) {int cover=0;for(int i=0;i<=cover;i++){cover=max(i+nums[i],cover);if(cover>=nums.size()-1) return true;}return false;}
};

45. 跳跃游戏 II

class Solution {
public:int jump(vector<int>& nums) {int res=0;int cur=0;int next=0;if(nums.size()==1)return 0;for(int i=0;i<nums.size();i++){next=max(i+nums[i],next);if(i==cur){res++;cur=next;if(cur>=nums.size()-1){break;}}}return res;}
};

1005. K 次取反后最大化的数组和

class Solution {
public:static bool cmp(int a,int b){return abs(a)>abs(b);}int largestSumAfterKNegations(vector<int>& nums, int k) {sort(nums.begin(),nums.end(),cmp);for(int i=0;i<nums.size();i++){if(nums[i]<0&&k>0){nums[i]*=-1;k--;}}if(k%2==1){nums[nums.size()-1]*=-1;}int res=0;for(int i=0;i<nums.size();i++){res+=nums[i];}return res;}
};

134. 加油站

感觉加油站这题做的很晕

class Solution {
public://1.从0遍历结束之后，rest>=0，就返回0//2.从0遍历结束之后，rest<0，返回-1//3.从0遍历，发现中间有rest<0,但整体>=0，那就从后遍历找rest累计能补掉这个漏洞的int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum=0;int min=INT_MAX;for(int i=0;i<cost.size();i++){int rest=gas[i]-cost[i];curSum+=rest;if(curSum<min){min=curSum;}}if(min>=0)return 0;if(curSum<0)return -1;for(int i=cost.size()-1;i>=0;i--){int rest=gas[i]-cost[i];min+=rest;if(min>=0)return i;}return -1;}
};

方法2：

class Solution {
public:int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {int curSum=0;int totalSum=0;int start=0;for(int i=0;i<gas.size();i++){curSum+=gas[i]-cost[i];totalSum+=gas[i]-cost[i];if(curSum<0){start=i+1;curSum=0;}}if(totalSum<0) return -1;return start;}
};

135. 分发糖果

class Solution {
public:int candy(vector<int>& ratings) {vector<int>candyVec(ratings.size(),1);for(int i=1;i<ratings.size();i++){if(ratings[i]>ratings[i-1]) candyVec[i]=candyVec[i-1]+1;}//从后往前遍历for(int i=ratings.size()-2;i>=0;i--){if(ratings[i]>ratings[i+1]) candyVec[i]=max(candyVec[i],candyVec[i+1]+1);}int res=0;for(int i=0;i<ratings.size();i++){res+=candyVec[i];}return res;}
};

860. 柠檬水找零

class Solution {
public:bool lemonadeChange(vector<int>& bills) {int five=0,ten=0,twenty=0;for(int i=0;i<bills.size();i++){if(bills[i]==5) five++;if(bills[i]==10){if(five==0)return false;else {five--;ten++;}}if(bills[i]==20){if(ten>0&&five>0){ten--;five--;twenty++;}else if(five>=3){five-=3;twenty++;}else return false;}}return true;}
};

406. 根据身高重建队列

class Solution {
public:static bool cmp(const vector<int>& a,const 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) {sort(people.begin(),people.end(),cmp);vector<vector<int>>que;for(int i=0;i<people.size();i++){int position=people[i][1];que.insert(que.begin()+position,people[i]);}return que;}
};

改进：容器使用了list,list底层是链表实现的，比起vector能减少时间复杂度

class Solution {
public:static bool cmp(const vector<int>& a,const 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) {sort(people.begin(),people.end(),cmp);list<vector<int>>que;for(int i=0;i<people.size();i++){int position=people[i][1];auto it=que.begin();while(position--){it++;}que.insert(it,people[i]);}return vector<vector<int>>(que.begin(),que.end());}
};

452. 用最少数量的箭引爆气球

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>&b){return a[0]<b[0];}int findMinArrowShots(vector<vector<int>>& points) {sort(points.begin(),points.end(),cmp);int res=1;for(int i=1;i<points.size();i++){if(points[i][0]>points[i-1][1]){res++;}else{points[i][1]=min(points[i-1][1],points[i][1]);}}return res;}
};

435. 无重叠区间

按照区间末端进行排序

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[1]<b[1];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);int count=1;int end=intervals[0][1];for(int i=1;i<intervals.size();i++){if(intervals[i][0]>=end){count++;end=intervals[i][1];}else continue;}return intervals.size()-count;}
};

按照区间前段进行排序：

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}int eraseOverlapIntervals(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);int count=0;int end=intervals[0][1];for(int i=1;i<intervals.size();i++){if(intervals[i][0]>=end){end=intervals[i][1];}else {count++;end=min(end,intervals[i][1]);}}return count;}
};

763. 划分字母区间

class Solution {
public:vector<int> partitionLabels(string s) {//初始化每个字符的最远位置int hash[26]={0};//遍历 初始化for(int i=0;i<s.size();i++){hash[s[i]-'a']=i;}//遍历，寻找最远距离vector<int>res;int left=0;int right=0;for(int i=0;i<s.size();i++){right=max(right,hash[s[i]-'a']);if(right==i){res.push_back(right-left+1);left=right+1;}}return res;}
};

56. 合并区间

class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}vector<vector<int>> merge(vector<vector<int>>& intervals) {sort(intervals.begin(),intervals.end(),cmp);    vector<vector<int>>res;res.push_back(intervals[0]);for(int i=1;i<intervals.size();i++){if(intervals[i][0]<=res.back()[1]){res.back()[1]=max(res.back()[1],intervals[i][1]);}else {res.push_back(intervals[i]);}}return res;}
};

738. 单调递增的数字

class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum=to_string(n);//flag标记从哪里开始被赋值成9int flag=strNum.size();for(int i=strNum.size()-1;i>0;i--){if(strNum[i]<strNum[i-1]){flag=i;strNum[i-1]--;}}for(int i=flag;i<strNum.size();i++){strNum[i]='9';}return stoi(strNum);}
};