前置知識(shí)
貪心算法的本質(zhì)
貪心的本質(zhì)是選擇每一階段的局部最優(yōu)，從而達(dá)到全局最優(yōu)。
例如，有一堆鈔票，你可以拿走十張，如果想達(dá)到最大的金額，你要怎么拿？
指定每次拿最大的，最終結(jié)果就是拿走最大數(shù)額的錢。
每次拿最大的就是局部最優(yōu)，最后拿走最大數(shù)額的錢就是推出全局最優(yōu)。
什么時(shí)候用貪心算法?
- 感覺(jué)像是可以用貪心
- 用題中的案例試一下, 發(fā)現(xiàn)沒(méi)問(wèn)題
- 嘗試舉一下反例, 發(fā)現(xiàn)沒(méi)問(wèn)題
- 那就可以用了
所以貪心算法并沒(méi)有固定的規(guī)律和套路, 也不會(huì)要求你論證背后算法的合理性和有效性, 只要能解決問(wèn)題, 通過(guò)測(cè)試案例即可.
ps:個(gè)人認(rèn)為貪心非常虛無(wú)縹緲呀, 還是動(dòng)態(tài)規(guī)劃更加有跡可循;
并且在實(shí)踐過(guò)程中, 可以用貪心算法的, 基本都可以用動(dòng)態(tài)規(guī)劃.
什么時(shí)候不能用貪心?
當(dāng)局部最優(yōu), 不一定可以達(dá)到全局最優(yōu)的時(shí)候, 如:
有一堆盒子，你有一個(gè)背包體積為n，如何把背包盡可能裝;
如果還每次選最大的盒子，就不行了。
這時(shí)候就需要?jiǎng)討B(tài)規(guī)劃。
貪心算法的解題步驟
- 將問(wèn)題分解為若干個(gè)子問(wèn)題
- 找出適合的貪心策略
- 求解每一個(gè)子問(wèn)題的最優(yōu)解
- 將局部最優(yōu)解堆疊成全局最優(yōu)解
這樣的敘述非常抽象, 實(shí)踐過(guò)程中還是要把握思想: 選擇每一階段的局部最優(yōu)，從而達(dá)到全局最優(yōu)
參考文章：關(guān)于貪心算法, 你該了解這些
455.分發(fā)餅干
題目描述
LeetCode鏈接：https://leetcode.cn/problems/assign-cookies/description/
解題思路
思路: 先將兩個(gè)數(shù)組都srot
遍歷g數(shù)組, 優(yōu)先滿足胃口最小的孩子
遍歷g數(shù)組中的元素gg的時(shí)候, 依次遍歷s數(shù)組, 選擇能滿足gg的最小尺寸餅干
代碼
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
int ans=0;
sort(g.begin(), g.end());
sort(s.begin(), s.end());
int ss=0;
for(int gg : g){
for(; ss<s.size(); ++ss){
if(s[ss] >= gg){
s[ss] = 0;
ans++;
break;
}
}
}
return ans;
}
};
376. 擺動(dòng)序列
題目描述
LeetCode鏈接：https://leetcode.cn/problems/wiggle-subsequence/description/
解題思路
<代>: 其實(shí)過(guò)程中不需要對(duì)數(shù)組進(jìn)行操作, 只需要看有多少個(gè)點(diǎn)是符合要求的即可;
具體過(guò)程比較復(fù)雜, 建議參考其原文.
代碼
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
int n=nums.size();
if(n==0 || n==1 || (n==2 && nums[0]!=nums[1]))
return n;
int curDiff = 0;
int preDiff = 0;
int ans=1;
for(int i=0; i<n-1; ++i){
curDiff = nums[i+1] - nums[i];
if((preDiff<=0 && curDiff>0) || (preDiff>=0 && curDiff<0)){
ans++;
preDiff = curDiff;
}
}
return ans;
}
};
53. 最大子序和
題目描述
LeetCode鏈接：https://leetcode.cn/problems/maximum-subarray/description/
暴力解法
思路: 暴力解法
對(duì)數(shù)組中每個(gè)數(shù), 都依次向后遍歷所有子數(shù)組, 求和, 和ans取max
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans=INT_MIN;
for(int i=0; i<nums.size(); ++i){
int sum=0;
for(int j=i; j<nums.size(); ++j){
sum += nums[j];
ans = max(ans, sum);
}
}
return ans;
}
};
動(dòng)態(tài)規(guī)劃
不出所料的, 超出時(shí)間限制;
用動(dòng)態(tài)規(guī)劃, 創(chuàng)建數(shù)組maxSumnums[0]的maxSum[0]就是自己本身
之后的nums[i]的maxSum[i]=max(nums[i], maxSum[i-1]+nums[i])
class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size()==1)
return nums[0];
vector<int> maxSum(nums.size());
maxSum[0] = nums[0];
int ans=nums[0];
for(int i=1; i<nums.size(); ++i){
maxSum[i] = max(nums[i], maxSum[i-1]+nums[i]);
ans = max(ans, maxSum[i]);
}
return ans;
}
};
優(yōu)化: 不用數(shù)組用pre
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = nums[0];
int pre = nums[0];
for(int i=1; i<nums.size(); ++i){
pre = max(pre+nums[i], nums[i]);
ans = max(ans, pre);
}
return ans;
}
};
貪心算法
選取一個(gè)個(gè)"區(qū)間", 過(guò)程中用count記錄區(qū)間內(nèi)的和;
當(dāng)count<0時(shí), 將其清空(=0)
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int ans = INT_MIN;
int count=0;
for(int i=0; i<nums.size(); ++i){
count += nums[i];
ans = max(ans, count);
if(count<0)
count = 0;
}
return ans;
}
};
總結(jié)
相比于動(dòng)態(tài)規(guī)劃, 貪心算法的思路難把握的多, 也很難以揣摩;
所以過(guò)程中如果想不出來(lái), 第一反應(yīng)應(yīng)該是嘗試動(dòng)態(tài)規(guī)劃, 或者直接看題解;
一方面不要在做題過(guò)程中硬磕貪心算法;
另一方面在學(xué)習(xí)的時(shí)候, 不要過(guò)于較真, 對(duì)于貪心這一部分的內(nèi)容, 可以適當(dāng)抱著"了解"和:"探索學(xué)習(xí)"的心態(tài).
把精力多花在可以比較快比較好地掌握和把握的部分和方法上.文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-700735.html
本文參考：
分發(fā)餅干
擺動(dòng)序列
最大子序和文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-700735.html
到了這里，關(guān)于LeetCode刷題筆記【23】：貪心算法專題-1（分發(fā)餅干、擺動(dòng)序列、最大子序和）的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
