原文連結（點選原文連結擷取更多學習幹貨）：
http://blog.bools.cn/archives/1277
- 貪心算法：采用貪心的政策，保證每次操作都是局部最優的，進而使最後得到的結果是全局最優的。在對問題求解時，總是做出在目前看來是最好的選擇，也就是說，不從整體最優上考慮，他所做出的僅是在某種意義上的局部最優解。貪心算法不是對所有問題都能得到整體最優解，但對範圍相當廣泛的許多問題他能産生整體最優解或者整體最優解的近似解。
- 解題的一般步驟是：
- 建立數學模型來描述問題
- 把求解的問題分成若幹個子問題
- 對每一子問題求解，得到子問題的局部最優解
- 把子問題的局部最優解合成原來問題的一個解。
3.該算法存在問題
- 不能保證求得的最後解是最佳的
- 不能用來求最大或最小解問題
- 隻能求滿足某些限制條件的可行解的範圍
4.應用
- 配置設定問題
有一群孩子和一堆餅幹，每個孩子有一個饑餓度，每個餅幹都有一個大小。每個孩子隻能吃最多一個餅幹，且隻有餅幹的大小大于孩子的饑餓度時，這個孩子才能吃飽。求解最多有多少孩子可以吃飽。
輸入輸出樣例
輸入：1 2
1 2 3
輸出：2
題解：
因為饑餓度最小的孩子最容易吃飽，是以我們先考慮這個孩子。為了盡量使得剩下的餅幹可以滿足饑餓度更大的孩子，是以我們應該把大于等于這個孩子饑餓度的、且大小最小的餅幹給這個孩子。滿足了這個孩子之後，我們采取同樣的政策，考慮剩下孩子裡饑餓度最小的孩子，直到沒有滿足條件的餅幹存在。
public class FindContentChildren {
static int solution(int[]children,int[ ]cookies) {
Arrays.sort(children);
Arrays.sort( cookies);
int child =0 ;//能吃飽的孩子數量
int cookie = 0 ;
while (child < children.length && cookie < cookies.length){
if ( children[child] <=cookies[cookie++])
child++;
}
return child ;
}
}
- 買賣股票的最佳時機
給定一個數組 prices ，其中 prices[i] 是一支給定股票第 i 天的價格。
設計一個算法來計算你所能擷取的最大利潤。你可以盡可能地完成更多的交易（多次買賣一支股票）。
注意：你不能同時參與多筆交易（你必須在再次購買前出售掉之前的股票）。
示例 1:
輸入: prices = [7,1,5,3,6,4]
輸出: 7
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 3 天（股票價格 = 5）的時候賣出, 這筆交易所能獲得利潤 = 5-1 = 4 。
随後，在第 4 天（股票價格 = 3）的時候買入，在第 5 天（股票價格 = 6）的時候賣出, 這筆交易所能獲得利潤 = 6-3 = 3 。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
int n = prices.size();
for (int i = 1; i < n; ++i) {
ans += max(0, prices[i] - prices[i - 1]);
}
return ans;
}
};
-
設定路燈
題目描述
小Q正在給一條長度為n的道路設計路燈安置方案。
為了讓問題更簡單,小Q把道路視為n個方格,需要照亮的地方用'.'表示, 不需要照亮的障礙物格子用'X'表示。
小Q現在要在道路上設定一些路燈, 對于安置在pos位置的路燈, 這盞路燈可以照亮pos - 1, pos, pos + 1這三個位置。
小Q希望能安置盡量少的路燈照亮所有'.'區域, 希望你能幫他計算一下最少需要多少盞路燈。
輸入描述:
輸入的第一行包含一個正整數t(1 <= t <= 1000), 表示測試用例數
接下來每兩行一個測試資料, 第一行一個正整數n(1 <= n <= 1000),表示道路的長度。
第二行一個字元串s表示道路的構造,隻包含'.'和'X'。 輸出描述:
對于每個測試用例, 輸出一個正整數表示最少需要多少盞路燈。 示例1
輸入
2
3
.X.
11
...XX....XX 輸出
1
3 思路：這是一個貪心算法。每遇到一個`.`，就是放置一個路燈，然後從這開始的三個位置都不用考慮。如果遇到了`'X'`，就是直接跳過。
// 貪心 每次遇到.；在.的後邊一個位置放置路燈，這樣就會用最少的路燈了
#include <string>
#include <iostream>
int main(void) {
int n;
std::cin>>n; // 測試案例個數
while(n--) {
int count =0; // 每個測試案例
int length;
std::string lamps;
std::cin>>length; // 路燈長度
std::cin>>lamps; // 路燈
for(int pos =0; pos < length; ) {
if(lamps[pos] =='.') {
pos +=3;
++count;
}
else {
pos +=1;
}
} //for
// 每次通過一個測試案例，就是輸出一次
std::cout<<count<<std::endl;
} //while
return 0;
}
歡迎關注技術公衆号，擷取更多C++學習幹貨！
我們能為你提供什麼？
技術輔導：C++、Java、嵌入式軟體/硬體
項目輔導：軟體/硬體項目、大廠實訓項目
就業輔導：就業全流程輔導、技術創業支援
對接企業HR：培養輸送優質性人才