贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
int cover =0;
if(nums.size()<=1) return true;
for(int i=0;i<=cover;i++){
cover = max(nums[i]+i,cover);
if(cover>=nums.size()-1){
return true;
}
}
return false;
}
};
K 次取反后最大化的数组和
class Solution {
public:
int largestSumAfterKNegations(vector<int>& nums, int k) {
int sum=0;
for(int i=0;i<nums.size();i++){
sum+=nums[i];
}
for(int i=0;i<k;i++){
int minv=INT32_MAX;
for(int j=0;j<nums.size();j++){
minv=min(nums[j],minv);
}
for(int j=0;j<nums.size();j++){
if(minv==nums[j]){
nums[j]=-1*nums[j];
sum+=nums[j]*2;
break;
}
}
}
return sum;
}
};
加油站
class Solution {
public:
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
int oil = 0;
int size = gas.size();
int num=0;
for(int i=0;i<size;i++){
gas.push_back(gas[i]);
cost.push_back(cost[i]);
}
for(int i=0;i<size*2;i++){
if(oil+gas[i]-cost[i]<0){
oil=0;
num=0;
cout<<i<<endl;
}else{
oil=oil+gas[i]-cost[i];
num++;
}
if(num==size){
return i-size+1;
}
}
return -1;
}
};
