leetcode 455 分配餅干


嘗試將最大的餅干給最貪心的朋友
如果滿足，則+1
如果不滿足，則將最大的餅干給次貪心的朋友，一次類推

試圖讓最多的小朋友開心

在這里插入代碼片 #include<iostream> #include<vector>using namespace std;class Solution{private:public:int findContentChildren(vector<int>& g, vector<int>& s){sort(g.begin(),g.end(),greater<int>());//因為在c++里面sort默認是將函數從小到大進行排列，//加上greater是將數組從大到小進行排列sort(s.begin(),s.end(),greater<int>()); int si=0,gi=0;//分別指向最大的餅和最貪心的朋友int res=0;while(gi<g.size() && si<s.size()){if(s[si]>=g[gi]){res++;si++;gi++}elsegi++;} return res;} }; int main(){return 0;}

leetcode 392

貪心算法與動態規劃之間的關系
leetcode 435 區間不重疊

第一種情況，至少刪除一組區間，第二種至少刪除兩組區間
等價情況：最多保留多少個區間？

按照起始點進行排序

//區間不重疊 #include<iostream> #include<vector>using namespace std;struct Interval{int start;int end;Interval(): start(0), end(0){}Interval(int s, int e): start(s), end(e){} }; bool compare(const Interval &a, const Interval &b){if(a.start != b.start()) return a.start<b.startreturn a.end<b.end } class Solution{ private:public:int eraseOverlapIntervals(vector<Interval>& intervals){if(interval.size()==0)return 0;sort(intervals.begin(),intervals.end(),compare);//memo[i]表示使用intervals[0...i]的區間能構成的最長不重疊區間序列 vector<int> memo(intervals.size(),-1);for(int i=1; i<intervals.size();i++)for(int j=0; j<i; j++)if(intervals[i].start>>intervals[j].end()) memo[i]=max(memo[i],1+memo[j]);int res=0;for(int i=0;i<memo.size();i++)res=max(res,memo[i]);return intervals.size()-res; }}; int main(){return 0;}

//區間不重疊 貪心算法實現 #include<iostream> #include<vector>using namespace std;struct Interval{int start;int end;Interval(): start(0), end(0){}Interval(int s, int e): start(s), end(e){} }; bool compare(const Interval &a, const Interval &b){if(a.start != b.start()) return a.start<b.startreturn a.end<b.end } class Solution{ private:public:int eraseOverlapIntervals(vector<Interval>& intervals){if(interval.size()==0)return 0;sort(intervals.begin(),intervals.end(),compare);//memo[i]表示使用intervals[0...i]的區間能構成的最長不重疊區間序列 int res=1;int pre=0;for(int i=1; i<intervals.size();i++)if(intervals.start>=intervals[pre].end){res++;pre=i;}return intervals.size()-res; }}; int main(){return 0;}

貪心選擇性質：如果無法使用貪心算法，舉出反例就可
數學歸納法和反證法

總結

以上是生活随笔為你收集整理的玩转算法之面试第十章-贪心算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。