概念：
局部最優(yōu)
題目
-
1. 分發(fā)餅干 (easy 455)
思路：
image.png
給最小孩子以能滿足的最小餅干
代碼：
方法一：
時(shí)間復(fù)雜度為O(n^2)；
using namespace std;
int MaxChildren(vector<int>&children,vector<int>&cookies){
int ans=0;
sort(children.begin(),children.end());
sort(cookies.begin(),cookies.end());
for(int i=0;i<children.size();i++){
for(int j=0;j<cookies.size();j++){
if(children[i]<=cookies[j]){
ans++;
cookies[j]-=children[i]:
}
}
}
return ans;
}
方法二：
時(shí)間復(fù)雜度
using namespace std;
int MaxChildren(vector<int>&children,vector<int>&cookies){
int ans=0;
makeheap(children.begin(),children.end(),greater<int>);
makeheap(cookies.begin(),cookies.end(),greater<int>);
for(int i=0;i<children.size();i++){
for(int j=0;j<cookies.size();j++){
pop_heap(children.begin(),children.end(),greater<int>);
pop_heap(cookies.begin(),cookies.end(),greater<int>);
if(children[-1]<=cookies[-1]){
ans++;
cookies[-1]-=children[-1];
children.pop_back();
cookies.pop_back();
//若餅干可以吃剩下的
//if(cookies[-1]==0) { cookies.pop_back(); }
}
else{ cookies.pop_back(); }
}
}
return ans;
-
2.股票的最大收益
思路：
f[4]-f[1]=(f[4]-f[3])+(f[3]-f[2])+(f[2]-f[1])
即局部最優(yōu)可以保證全局最優(yōu)庸诱，因此可以使用貪心捻浦。
from 知乎
代碼：
int MaxInterest(vector<int>& prices){
int ans=0;
for(int i=1;i<prices.size();i++){
if(prices[i]>prices[i-1]){ans+=prices[i]-prices[i-1];}
}
return ans;
}
-
種植問(wèn)題：
代碼：
bool canPlant(vector<int>& plant,int n){
if(n<=0)return true;
int i=0;
if(plant[plant.size()-1]==0&&plant[plant.size()-2]==0){n--;plant[plant.size()-1]=1;}
while(i<plant.size()){
if(plant[i-1]=0&&plant[i+1]=0)n--;
if(n==0)return true;
i++;
}
return false;
-
Kruskal和Prim算法
Kurskal算法思想：對(duì)邊排序，每次取最小邊桥爽，若不構(gòu)成環(huán)路則加入朱灿，所有點(diǎn)入集合時(shí)循環(huán)終止
偽代碼：
void Krukskal(Grap& map,vector<string>&Kvertex){
sort(map);
int i=0,j=0;
vector<vector<int>>&Tvertex;
while(i<num){
if(Tvertex[map[j][0]][map[j][1]]==0){
Kvertex[++i]=to_string([map[j][0]])+(string)[map[j][1]]；
Tvertex[map[j][0]][map[j][1]]==1;
}
j++;
}
}
Prim算法思想：取點(diǎn)的最小邊钠四，更新點(diǎn)集合盗扒，每次取集合的最小鄰邊，所有點(diǎn)入集合時(shí)循環(huán)終止
代碼：
vector<int> Prim(Grap &G){
int count=1,v=0;
vector<int>(num,0)w;
while(count<G.num){
v=Sort(w,G,count);//Sort,在G種形导，取w的前count個(gè)元素的臨邊环疼，找到最小值，返回最小值的臨邊朵耕；
w[count++]=v;
}
return w;
-
Dijikstra算法
思想：取點(diǎn)的最小邊炫隶，更新點(diǎn)集合，再更新到當(dāng)前點(diǎn)的最短距離阎曹；和Prim類似伪阶，區(qū)別在于會(huì)更新最小距離。
image.png
代碼：
void Dij(Graph &G,int start, vector<int>Dist){
int n=G.num;
vector<int>Final(num,0);
vector<int>Path(num,-1);
Final[start]=1;
Path[start]=-1;
Dist[start]=0;
int min_value=Maxsize;
int min_index=start;
while(Ture){
int flag=0;
for(int i=0;i<n;i++){
if(Final[i]){
for(int j=0;j<n;j++){
if(Dist[i]+G[i][j]<Dist[i]) {
Dist[i]= (Dist[i]+G[i][j];
Path[j]=i;
}
}
}
else{
min_value=Dist[i]>min_value?min_value:Dist[i];
min_index=i;
}
}
Final[min_index]=1;
for(int i=0;i<n;i++){
if(!Final[i]){flag=1;}
}
if(flag=0)break;
}
}
