堆結構和lambda表達式的應用（IPO問題）

文章和資源同步更新至微信公眾號：演算法工程師之路

之前有篇文章講解了堆結構以及堆排序，堆可以分為大根堆和小根堆，那麼我們如何使用么？筆試時需不需要自己重新實現一個堆結構呢？這個問題怎麼說，從底層實現是應該會的，也不難，但實際用的時候就不用自己重新造輪子了！C++標準庫中有類似堆結構的東西——Priority_Queue!

lambda表達式

段落來源轉自簡書--小白將

在開始今天的內容之前，我們先來說一說C++中的lambda表達式，大家學過Python的都知道lambda表達式的好處，可以省略大量代碼而且使得閱讀邏輯更加清晰，在C++中其表現結構一般為：

[ 俘獲變數 ] （形參） { 函數體 }

lambda表達式最前面的方括弧的意義何在？其實這是lambda表達式一個很要的功能，就是閉包。lambda表達式的大致原理：每當你定義一個lambda表達式後，編譯器會自動生成一個匿名類（這個類當然重載了()運算符），我們稱為閉包類型（closure type）。那麼在運行時，這個lambda表達式就會返回一個匿名的閉包實例，其實一個右值。所以，我們上面的lambda表達式的結果就是一個個閉包。閉包的一個強大之處是其可以通過傳值或者引用的方式捕捉其封裝作用域內的變數，前面的方括弧就是用來定義捕捉模式以及變數，我們又將其稱為lambda捕捉塊。

捕獲的方式可以是引用也可以是複製，但是具體說來會有以下幾種情況來捕獲其所在作用域中的變數：

那麼捕獲域是怎麼使用呢？我們可以看下面的例子：

int main(int argc, char** argv){ int x =10; auto add_x = [x](int a){return a+x;}; auto multipy_x = [&x](int a){return a*x;};

cout<<"add "<<add_x(10)<<" "<<"multipy "<< multipy_x(10)<<endl;
}

[]：默認不捕獲任何變數；
[=]：默認以值捕獲所有變數；
[&]：默認以引用捕獲所有變數；
[x]：僅以值捕獲x，其它變數不捕獲；
[&x]：僅以引用捕獲x，其它變數不捕獲；
[=, &x]：默認以值捕獲所有變數，但是x是例外，通過引用捕獲；
[&, x]：默認以引用捕獲所有變數，但是x是例外，通過值捕獲；
[this]：通過引用捕獲當前對象（其實是複製指針）；
[*this]：通過傳值方式捕獲當前對象；

一般我們通常使用前三種形式！！！

PriorityQueue(優先順序隊列)

C++標準庫中的優先順序隊列其底層數據一般為vector形式，並以堆結構進行數據管理的，我們通過前面的知識也知道堆分為大根堆和小根堆，其中大根堆的根節點是最大值，而小根堆的根節點是最小值。因此，我們在定義PriorityQueue時候需要指定其比較器，特別是當存儲類型為自定義對象時！

我們首先來看PriorityQueue的模板定義，其中less< value_type >是一個標準庫中的函數對象，因此我們知道了模板參數中的第三個位置是一個比較函數的函數對象。因此我們可以自己新建一個函數對象來進行傳遞！

template <class T, class Container = vector<T>, class Compare =
less<typename Container::value_type> > class priority_queue;

下面例子介紹了幾種構造優先順序隊列的方法：

通過一個類重載()來構成函數對象，用於自定義比較器使用
對於基礎類型，可以使用標準庫中的函數對象，如less和more
使用lambda表達式，由於lambda表達式返回的是一個匿名對象，因此必須在實例化同時將其作為參數傳遞到priority_queue中去！
構建的比較器中<表示less（降序）表示小根堆，反之>表示大根堆

#include <queue> #include <vector> #include <iostream> template<typename T> void print_queue(T& q) { while(!q.empty()) { std::cout << q.top() << " "; q.pop(); } std::cout << ; }

class myGreater{
public:
bool operator()(const int a, const int b){
return a > b;
}
};

int main() {
// 情況1：默認為大根堆，相當於<int, vector<int>, less<int>> q;
std::priority_queue<int> q;
for(int n : {1,8,5,6,3,4,0,9,7,2})
q.push(n);
print_queue(q);
// 情況2：自定義函數對象
std::priority_queue<int, std::vector<int>, myGreater > q2;
for(int n : {1,8,5,6,3,4,0,9,7,2})
q2.push(n);
print_queue(q2);
// 情況3：使用lambda表達式構建，decltype獲取匿名函數類型
auto cmp = [](int left, int right) { return left < right;};
std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
for(int n : {1,8,5,6,3,4,0,9,7,2})
q3.push(n);
print_queue(q3);
}

IPO問題

（來自LeetCode）為了以更高的價格將股票賣給風險投資公司，力扣希望在 IPO 之前開展一些項目以增加其資本。由於資源有限，它只能在 IPO 之前完成最多 k 個不同的項目。幫助力扣設計完成最多 k 個不同項目後得到最大總資本的方式。
給定若干個項目。對於每個項目 i，它都有一個純利潤 Pi，並且需要最小的資本 Ci 來啟動相應的項目。最初，你有 W

資本。當你完成一個項目時，你將獲得純利潤，且利潤將被添加到你的總資本中。
總而言之，從給定項目中選擇最多 k 個不同項目的列表，以最大化最終資本，並輸出最終可獲得的最多資本。例子：輸入: k=2, W=0, Profits=[1,2,3], Capital=[0,1,1].輸出: 4

解釋: 由於你的初始資本為 0，你盡可以從 0 號項目開始。在完成後，你將獲得 1 的利潤，你的總資本將變為 1。此時你可以選擇開始 1
號或 2 號項目。由於你最多可以選擇兩個項目，所以你需要完成 2 號項目以獲得最大的資本。因此，輸出最後最大化的資本，為 0 + 1 +3 = 4。

演算法原理：

這個問題使用最大堆和最小堆就可以很簡單的實現，並且我們使用貪心演算法，具體的貪心策略如下：

首先將每個項目按照所需要的資本排序放進最小堆中，然後逐個取出堆頂的元素並進行判斷是否小於初始資金W，這樣就可以得到當前可以啟動的項目的集合！
然後將這個項目集合按照獲得的收益放進最大堆，然後取出這個堆頂也就是最大的收益，相加後得到新的資金W，然後再去判斷最小堆中是否可以解鎖新的項目，如果有，添加到最大堆，如果沒有，繼續執行取出最大堆堆頂的操作！
這樣保證了我們做的每個項目都是收益最高，而且是滿足條件（資金允許）可以做的！

具體代碼為：

// 第二種形式，使用pair方式，只能傳遞二個參數 int findMaximizedCapital(int k, int W, vector<int> &Profits, vector<int> &Capital) { // pair<int, int> cost, profit auto cmp1 = [](const pair<int, int> &a, const pair<int, int> &b) { if(a.first > b.first){ return true; } // 小根堆 return false; };

auto cmp2 = [](const pair<int, int> &a, const pair<int, int> &b) {
if(a.second < b.second){
return true;
} // 大根堆
return false;
};
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp1)> minCost(cmp1);
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp2)> maxProfit(cmp2);
for (int i = 0;i < Profits.size(); i++){
minCost.emplace(Capital[i], Profits[i]);
}
for (int i = 0;i < k; i++){
while(!minCost.empty() && minCost.top().first <= W){
maxProfit.push(minCost.top());
minCost.pop();
}
if(maxProfit.empty()){
cout << endl;
return W;
}
W += maxProfit.top().second;
cout << maxProfit.top().second << "...";
maxProfit.pop();
}
cout << endl;
return W;
}