> 作者：?舊言~
> 座右銘：松樹千年終是朽，槿花一日自為榮。

> 目標：了解什么是貪心算法，并且掌握貪心算法。

> 毒雞湯：有些事情，總是不明白，所以我不會堅持。早安!

> 專欄選自：貪心算法_?舊言~的博客-CSDN博客

> 望小伙伴們點贊👍收藏?加關注喲💕💕

一、算法講解

貪心算法的定義：

貪心算法是指在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優上加以考慮，只做出在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇，選擇的貪心策略必須具備無后效性，即某個狀態以前的過程不會影響以后的狀態，只與當前狀態有關。

解題的一般步驟是：

1. 建立數學模型來描述問題；
2. 把求解的問題分成若干個子問題；
3. 對每一子問題求解，得到子問題的局部最優解；
4. 把子問題的局部最優解合成原來問題的一個解。

如果大家比較了解動態規劃，就會發現它們之間的相似之處。最優解問題大部分都可以拆分成一個個的子問題，把解空間的遍歷視作對子問題樹的遍歷，則以某種形式對樹整個的遍歷一遍就可以求出最優解，大部分情況下這是不可行的。貪心算法和動態規劃本質上是對子問題樹的一種修剪，兩種算法要求問題都具有的一個性質就是子問題最優性(組成最優解的每一個子問題的解，對于這個子問題本身肯定也是最優的)。

動態規劃方法代表了這一類問題的一般解法，我們自底向上構造子問題的解，對每一個子樹的根，求出下面每一個葉子的值，并且以其中的最優值作為自身的值，其它的值舍棄。而貪心算法是動態規劃方法的一個特例，可以證明每一個子樹的根的值不取決于下面葉子的值，而只取決于當前問題的狀況。換句話說，不需要知道一個節點所有子樹的情況，就可以求出這個節點的值。由于貪心算法的這個特性，它對解空間樹的遍歷不需要自底向上，而只需要自根開始，選擇最優的路，一直走到底就可以了。

二、算法習題

---

2.1、第一題

題目鏈接：409. 最長回文串 - 力扣（LeetCode）

題目描述：

算法思路：?盡可能多的字符去構造回?串

1. 如果字符出現偶數個，那么全部都可以?來構造回?串；
2. 如果字符出現奇數個，減去?個之后，剩下的字符能夠全部?來構造回?串；
3. 最后再判斷?下，如果有字符出現奇數個，就把它單獨拿出來放在中間。?

代碼呈現：

class Solution {
public:int longestPalindrome(string s) {// 1. 計數 - ?數組模擬哈希表int hash[127] = {0};for (char ch : s)hash[ch]++;// 2. 統計結果int ret = 0;for (int x : hash) {ret += x / 2 * 2;}return ret < s.size() ? ret + 1 : ret;}
};

2.2、第二題

題目鏈接：942. 增減字符串匹配 - 力扣（LeetCode）

題目描述：

??

算法思路：?

• 當遇到 'I' 的時候，為了讓下?個上升的數可選擇的「范圍更多」，當前選擇「最?」的那個數；
• 當遇到 'D' 的時候，為了讓下?個下降的數可選擇的「范圍更多」，選擇當前「最?」的那個數。

代碼呈現：

class Solution {
public:vector<int> diStringMatch(string s) {int left = 0, right = s.size(); // ? left，right 標記最?值和最?值vector<int> ret;for (auto ch : s) {if (ch == 'I')ret.push_back(left++);elseret.push_back(right--);}ret.push_back(left); // 把最后?個數放進去return ret;}
};

2.3、第三題

題目鏈接：455. 分發餅干 - 力扣（LeetCode）

題目描述：

??

算法思路：?

先將兩個數組排序。針對胃?較?的孩?，從?到?挑選餅?：

1. 如果當前餅?能滿?，直接喂（最?的餅?都能滿?，不要浪費?餅?）；
2. 如果當前餅?不能滿?，放棄這個餅?，去檢測下?個餅?（這個餅?連最?胃?的孩?都?法滿?，更別提那些胃??的孩?了）。

代碼呈現：

class Solution {
public:int findContentChildren(vector<int>& g, vector<int>& s) {// 先排序sort(g.begin(), g.end());sort(s.begin(), s.end());// 利?雙指針找答案int ret = 0, n = s.size();for (int i = 0, j = 0; i < g.size() && j < n; i++, j++) {while (j < n && s[j] < g[i])j++; // 找餅?if (j < n)ret++;}return ret;}
};

2.4、第四題

題目鏈接：553. 最優除法 - 力扣（LeetCode）

題目描述：

??

算法思路：?

• 在最終的結果中，前兩個數的位置是?法改變的。
• 因為每?個數的都是?于等于 2 的，為了讓結果更?，我們應該盡可能的把剩下的數全都放在「分?」上。

代碼呈現：

class Solution {
public:string optimalDivision(vector<int>& nums) {int n = nums.size();// 先處理兩個邊界情況if (n == 1) {return to_string(nums[0]);}if (n == 2) {return to_string(nums[0]) + "/" + to_string(nums[1]);}string ret = to_string(nums[0]) + "/(" + to_string(nums[1]);for (int i = 2; i < n; i++) {ret += "/" + to_string(nums[i]);}ret += ")";return ret;}
};

2.4、第五題

題目鏈接：45. 跳躍游戲 II - 力扣（LeetCode）

題目描述：

??

算法思路：?

• ?類似層序遍歷的過程，將第 i 次跳躍的「起始位置」和「結束位置」找出來，?這次跳躍的情況，更新出下?次跳躍的「起始位置」和「終?位置」。
• 這樣「循環往復」，就能更新出到達 n - 1 位置的最?跳躍步數。

代碼呈現：

class Solution {
public:int jump(vector<int>& nums) {int left = 0, right = 0, maxPos = 0, ret = 0, n = nums.size();while (left <= right) // 保險的寫法，以防跳不到 n - 1 的位置{if (maxPos >= n - 1) // 先判斷?下是否已經能跳到最后?個位置{return ret;}// 遍歷當成層，更新下?層的最右端點for (int i = left; i <= right; i++) {maxPos = max(maxPos, nums[i] + i);}left = right + 1;right = maxPos;ret++;}return -1; // 跳不到的情況}
};

2.6、第六題

題目鏈接：55. 跳躍游戲 - 力扣（LeetCode）

題目描述：

??

算法思路：

和 跳躍游戲II ?樣，僅需修改?下返回值即可。

代碼呈現：

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

三、結束語?

今天內容就到這里啦，時間過得很快，大家沉下心來好好學習，會有一定的收獲的，大家多多堅持，嘻嘻，成功路上注定孤獨，因為堅持的人不多。那請大家舉起自己的小手給博主一鍵三連，有你們的支持是我最大的動力💞💞💞，回見。