1--項目的最大利潤

題目描述：

????????輸入：正數數組 costs，costs[i] 表示項目 i 的花費；正數數組 profits，profits[i] 表示項目 i 的花費；正數 k 表示只能串行完成最多 k 個項目；m 表示擁有的資金，每完成一個項目后資金會立即更新（原始資金 + 利潤）；

? ? ? ? 輸出：求解最后獲得的最大利潤；

主要思路：

????????小根堆存儲所有項目，大根堆存儲可以進行的項目；

? ? ? ? 每次從小根堆解鎖項目添加到大根堆中，優先做大根堆利潤最高的項目；

#include <iostream>
#include <vector>
#include <queue>struct project{project(int c, int p) : cost(c), profit(p) {}int cost;int profit;
};class cmp1{
public:bool operator()(project* a, project* b){return a->cost > b->cost;}
};struct cmp2{bool operator()(project* a, project* b){return a->profit < b->profit;}
};class Solution{
public:int findMaxCapital(int m, int k, std::vector<int> costs, std::vector<int> profits){std::priority_queue<project*, std::vector<project*>, cmp1> minCostQ;std::priority_queue<project*, std::vector<project*>, cmp2> maxProfitQ;// 按cost按從小到大排序項目for(int i = 0; i < profits.size(); i++){minCostQ.push(new project(costs[i], profits[i]));}for(int i = 0; i < k; i++){while(!minCostQ.empty() && minCostQ.top()->cost <= m){// 可以解鎖新的項目maxProfitQ.push(minCostQ.top());minCostQ.pop();}if(maxProfitQ.empty()) return m; // 無法解鎖新的項目，直接返回// 更新資金m += maxProfitQ.top()->profit;maxProfitQ.pop();}return m;}
};int main(int argc, char *argv[]){int m = 1;int k = 2;std::vector<int> costs = {1, 1, 2, 2, 3, 4};std::vector<int> profits = {1, 4, 3, 7, 2, 10};Solution S1;int res = S1.findMaxCapital(m, k, costs, profits);std::cout << res << std::endl; 
}

2--數據流的中位數

主要思路：

? ? ? ? 分別使用大根堆和小根堆存儲數據，每添加一個數據，先將數據添加至大根堆，再將數據彈出并添加到小根堆；

? ? ? ? 當小根堆值的數量與大根堆值的數量相差 2 時，從小根堆彈出數據添加到大根堆中，保持兩個根堆的容量差不超過；

? ? ? ? 根據添加數據量是偶數還是奇數，返回對應的中位數；

#include <iostream>
#include <queue>class MedianFinder {
public:MedianFinder() {}void addNum(int num) {maxQ.push(num);minQ.push(maxQ.top());maxQ.pop();if(minQ.size() - maxQ.size() > 1){maxQ.push(minQ.top());minQ.pop();}}double findMedian() {// 奇數if((maxQ.size() + minQ.size()) % 2 != 0) return minQ.top();// 偶數else return( (maxQ.top() + minQ.top()) / 2.0);}
private:std::priority_queue<int, std::vector<int>, std::greater<int>> minQ;std::priority_queue<int, std::vector<int>, std::less<int>> maxQ;
};int main(int argc, char *argv[]){MedianFinder S1;S1.addNum(1);S1.addNum(2);S1.addNum(3);S1.addNum(4);S1.addNum(5);double res = S1.findMedian();std::cout << res << std::endl;
}