您好,登錄后才能下訂單哦!
今天小編給大家分享一下C++貪心算法怎么應(yīng)用的相關(guān)知識(shí)點(diǎn),內(nèi)容詳細(xì),邏輯清晰,相信大部分人都還太了解這方面的知識(shí),所以分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后有所收獲,下面我們一起來了解一下吧。
我們熟知的選擇排序,其采用的就是貪心策略。 它所采用的貪心策略即為每次從未排序的數(shù)據(jù)中選取最小值,并把最小值放在未排序數(shù)據(jù)的起始位置,直到未排序的數(shù)據(jù)為0,則結(jié)束排序。
void swap(int* arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } void selectSort(int* arr, int n) { //降序 for (int i = 0; i < n; i++) { int maxIndex = i; for (int j = i+1; j < n; j++) { if (arr[j] >= arr[maxIndex]) maxIndex = j; } swap(arr, i, maxIndex); } }
問題描述:
在一個(gè) 平衡字符串 中,‘L' 和 ‘R' 字符的數(shù)量是相同的。
給你一個(gè)平衡字符串 s,請(qǐng)你將它分割成盡可能多的平衡字符串。
注意:分割得到的每個(gè)字符串都必須是平衡字符串,且分割得到的平衡字符串是原平衡字符串的連續(xù)子串。
返回可以通過分割得到的平衡字符串的 最大數(shù)量 。
貪心策略:從左往右掃描,只要達(dá)到平衡,就立即分割,不要有嵌套的平衡。
故可以定義一個(gè)變量balance,在遇到不同的字符時(shí),向不同的方向變化,當(dāng)balance為0時(shí)達(dá)到平衡,分割數(shù)更新。
比如:從左往右掃描字符串s,遇到L,balance-1,遇到R,balance+1.當(dāng)balance為0時(shí),更新cnt++ 如果最終cnt==0,說明s只需要保持原樣,返回1
代碼實(shí)現(xiàn):
class Solution { public: int balancedStringSplit(string s) { if(s.size() == 1) return 0; int cnt = 0; int balance = 0; for(int i = 0; i < s.size(); i++) { if(s[i] == 'R') --balance; else ++balance; if(balance == 0) cnt++; } if(cnt == 0) return 1; return cnt; } };
問題描述:
給定一個(gè)數(shù)組 prices ,其中 prices[i] 是一支給定股票第 i 天的價(jià)格。
設(shè)計(jì)一個(gè)算法來計(jì)算你所能獲取的最大利潤。你可以盡可能地完成更多的交易(多次買賣一支股票)。
注意:你不能同時(shí)參與多筆交易(你必須在再次購買前出售掉之前的股票)。
貪心策略:
連續(xù)上漲交易日:第一天買最后一天賣收益最大,等價(jià)于每天都買賣。
連續(xù)下降交易日:不買賣收益最大,即不會(huì)虧錢。
故可以遍歷整個(gè)股票交易日價(jià)格列表,在所有上漲交易日都買賣(賺到所有利潤),所有下降交易日都不買賣(永不虧錢)
例如從10到50是連續(xù)上漲的5天,可以第一天買入,最后一天賣出,利潤為40,等價(jià)于第一天買入第二天賣出,第二天再買入。。。以此類推
代碼實(shí)現(xiàn):
class Solution { public: int maxProfit(vector<int>& prices) { int profit = 0; for(int i = 0; i < prices.size() - 1; i++) { if(prices[i] <= prices[i+1]) profit += prices[i+1] - prices[i]; } return profit; } };
問題描述:
給定一個(gè)非負(fù)整數(shù)數(shù)組 nums ,你最初位于數(shù)組的 第一個(gè)下標(biāo) 。
數(shù)組中的每個(gè)元素代表你在該位置可以跳躍的最大長度。
判斷你是否能夠到達(dá)最后一個(gè)下標(biāo)。
貪心策略:
根據(jù)題目描述,對(duì)于數(shù)組中的任意一個(gè)位置y,只要存在一個(gè)位置x,它本身可以到達(dá),并且它跳躍的最大長度為x+nums[x],這個(gè)值大于等于y,即x+nums[x] >= y,那么位置y也可以到達(dá)。即對(duì)于每一個(gè)可以到達(dá)的位置x,它使得x+1,x+2,…,x+nums[x] >= y,那么位置y也可以到達(dá)。 一次遍歷數(shù)組中的每一個(gè)位置,并實(shí)時(shí)更新最遠(yuǎn)可以到達(dá)的位置。對(duì)于當(dāng)前遍歷到的位置x,如果它在最遠(yuǎn)可以到達(dá)的位置范圍內(nèi),那么我們就可以從起點(diǎn)通過若干次跳躍達(dá)到該位置,因此我們可以用x+nums[x]更新最遠(yuǎn)可以到達(dá)的位置。
在遍歷的過程中,如果最遠(yuǎn)可以到達(dá)的位置大于等于數(shù)組中的最后一個(gè)位置,那就說明最后一個(gè)位置可到達(dá),直接返回true。遍歷結(jié)束后,最后一個(gè)位置仍不可達(dá),返回false。
例如:[2, 3, 1, 1, 4]
一開始在位置0,可跳躍的最大長度為2,因此最遠(yuǎn)可以到達(dá)的位置倍更新為2;繼續(xù)遍歷到位置1,由于1<=2,因此位置1可達(dá)。用1加上它最大可跳躍的長度3,將最遠(yuǎn)可以到達(dá)的位置更新為4,4大于最后一個(gè)位置4,返回true
代碼實(shí)現(xiàn):
class Solution { public: bool canJump(vector<int>& nums) { int maxLen = nums[0]; for(int i = 0; i < nums.size(); i++) { if(i <= maxLen) { maxLen = max(i + nums[i],maxLen); if(maxLen >= nums.size() - 1) return true; } } return false; } };
問題描述:
假設(shè)1元、2元、5元、10元、20元、50元、100元的紙幣分別有c0, c1, c2, c3, c4, c5, c6張?,F(xiàn)在要用這些錢來支付K元,至少要用多少張紙幣?
貪心策略: 顯然,每一步盡可能用面值大的紙幣即可。在日常生活中我們也是這么做的。
代碼實(shí)現(xiàn):
//按面值降序 struct cmp { bool operator()(vector<int>& a1, vector<int>& a2) { return a1[0] > a2[0]; } }; int solve(vector<vector<int>>& moneyCount, int money) { int num = 0; sort(moneyCount.begin(), moneyCount.end(), cmp()); //首先選擇最大面值的紙幣 for (int i = 0; i < moneyCount.size() - 1; i++) { //選擇需要的當(dāng)前面值和該面值有的數(shù)量中的較小值 int c = min(money / moneyCount[i][0], moneyCount[i][1]); money -= c * moneyCount[i][0]; num += c; } if (money > 0) num = -1; return num; }
問題描述:
某工廠有n個(gè)獨(dú)立的作業(yè),由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的加工時(shí)間為ti,任何作業(yè)在被處理時(shí)不能中斷,也不能進(jìn)行拆分處理?,F(xiàn)廠長請(qǐng)你給他寫一個(gè)程序:算出n個(gè)作業(yè)由m臺(tái)機(jī)器加工處理的最短時(shí)間。
輸入:第一行T(1<T<100)表示有T組測試數(shù)據(jù)。每組測試數(shù)據(jù)的第一行分別是整數(shù)n,m(1<=n<=10000,1<=m<=100),接下來的一行是n個(gè)整數(shù)ti(1<=t<=100)。
輸出:所需的最短時(shí)間
貪心策略:
這個(gè)問題還沒有最優(yōu)解,但是用貪心選擇策略可設(shè)計(jì)出較好的近似算法(求次優(yōu)解) 當(dāng)n<=m時(shí),只要將作業(yè)分給每一個(gè)機(jī)器即可;當(dāng)n>m時(shí),首先將n個(gè)作業(yè)時(shí)間從大到小排序,然后依此順序?qū)⒆鳂I(yè)分配給下一個(gè)作業(yè)馬上結(jié)束的處理機(jī)。也就是說從剩下的作業(yè)中選擇需要處理時(shí)間最長的,然后依次選擇處理時(shí)間次長的,直到所有作業(yè)全部處理完畢,或者機(jī)器不能再處理其他作業(yè)為止。如果我們每次是將需要處理時(shí)間最短的作業(yè)分配給空閑的機(jī)器,那么可能就會(huì)儲(chǔ)秀安其它所有作業(yè)都處理完了只剩下所需時(shí)間最長的作業(yè)在處理的情況,這樣勢必效率較低。
代碼實(shí)現(xiàn):
struct cmp{ bool operator()(const int& x, const int& y){ return x > y; } }; int findMax(vector<int>& machines) { int ret = 0; for (int i = 0; i < machines.size(); i++) { if (machines[i] > machines[ret]) ret = i; } return machines[ret]; } int greedStrategy(vector<int>& works, vector<int>& machines) { //降序 sort(works.begin(), works.end(), cmp()); int n = works.size(); int m = machines.size(); for (int i = 0; i < n; i++) { int finish = 0; int machineTime = machines[finish]; for (int j = 1; j < m; j++) { if (machines[j] < machines[finish]) { finish = j; } } machines[finish] += works[i]; } return findMax(machines); }
問題描述:
有n個(gè)需要在同一天使用同一個(gè)教室的活動(dòng)a1, a2, …, an,教室同一時(shí)刻只能由一個(gè)活動(dòng)使用。每個(gè)活動(dòng)a[i]都有一個(gè)開始時(shí)間s[i]和結(jié)束時(shí)間f[i]。一旦被選擇后,活動(dòng)a[i]就占據(jù)半開時(shí)間區(qū)間[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重疊,a[i]和a[j]兩個(gè)活動(dòng)就可以被安排在這一天。求使得盡量多的活動(dòng)能不沖突的舉行的最大數(shù)量。
貪心策略:
1.每次都選擇開始時(shí)間最早的活動(dòng),不能得到最優(yōu)解。
2.每次都選擇持續(xù)時(shí)間最短的活動(dòng),不能得到最優(yōu)解。
3.每次選取結(jié)束時(shí)間最早的活動(dòng)(結(jié)束時(shí)間最早意味著開始時(shí)間也早),可以得到最優(yōu)解。按這種方法選擇,可以為未安排的活動(dòng)留下盡可能多的時(shí)間。如下圖的活動(dòng)集合S,其中各項(xiàng)活動(dòng)按照結(jié)束時(shí)間單調(diào)遞增排序。
代碼實(shí)現(xiàn):
struct cmp{ bool operator()(vector<int>& s1, vector<int>& s2){ return s1[1] < s2[1]; } }; int getMaxNum(vector<vector<int>>& events) { sort(events.begin(), events.end(), cmp()); int num = 1; int i = 0; for (int j = 1; j < events.size();j++) { if (events[j][0] >= events[i][1]) { ++num; i = j; } } return num; }
問題描述:
給定一個(gè)區(qū)間的集合,找到需要移除區(qū)間的最小數(shù)量,使剩余區(qū)間互不重疊。
注意:
可以認(rèn)為區(qū)間的終點(diǎn)總是大于它的起點(diǎn)。
區(qū)間 [1,2] 和 [2,3] 的邊界相互“接觸”,但沒有相互重疊。
貪心策略:
法一:與上題活動(dòng)選擇類似,用總區(qū)間數(shù)減去最大可同時(shí)進(jìn)行的區(qū)間數(shù)即為結(jié)果。
法二: 當(dāng)按照起點(diǎn)先后順序考慮區(qū)間時(shí),利用一個(gè)prev指針追蹤剛剛添加到最終列表中的區(qū)間。遍歷時(shí),可能遇到三種情況:
情況1:當(dāng)前考慮的兩個(gè)區(qū)間不重疊。這種情況下不移除任何區(qū)間,將prev賦值為后面的區(qū)間,移除區(qū)間數(shù)量不變。
情況2:兩個(gè)區(qū)間重疊,后一個(gè)區(qū)間的終點(diǎn)在前一個(gè)區(qū)間的終點(diǎn)之前。由于后一個(gè)區(qū)間的長度更小,可以留下更多空間,容納更多區(qū)間,將prev更新為當(dāng)前區(qū)間,移除區(qū)間的數(shù)量+1
情況3:兩個(gè)區(qū)間重疊,后一個(gè)區(qū)間的終點(diǎn)在前一個(gè)區(qū)間的終點(diǎn)之后。直接移除后一個(gè)區(qū)間,留下更多空間。因此,prev不變,移除區(qū)間的數(shù)量+1
代碼實(shí)現(xiàn): 法一:
struct cmp{ bool operator()(vector<int>& s1, vector<int>& s2){ return s1[1] < s2[1]; } }; class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { sort(intervals.begin(), intervals.end(), cmp()); int num = 1; int i = 0; for(int j = 1; j < intervals.size(); j++) { if(intervals[j][0] >= intervals[i][1]) { i = j; num++; } } return intervals.size() - num; } };
法二:
struct cmp{ bool operator()(vector<int>& s1, vector<int>& s2){ return s1[1] < s2[1]; } }; class Solution { public: int eraseOverlapIntervals(vector<vector<int>>& intervals) { if(intervals.empty()) return 0; sort(intervals.begin(), intervals.end(), cmp()); int prev = 0; int num = 0; for(int i = 1; i < intervals.size(); i++) { //情況1 不沖突 if(intervals[i][0] >= intervals[prev][1]) { prev = i; } else { if(intervals[i][1] < intervals[prev][1]) { //情況2 prev = i; } num++; } } return num; } };
以上就是“C++貪心算法怎么應(yīng)用”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家閱讀完這篇文章都有很大的收獲,小編每天都會(huì)為大家更新不同的知識(shí),如果還想學(xué)習(xí)更多的知識(shí),請(qǐng)關(guān)注億速云行業(yè)資訊頻道。
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請(qǐng)聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。