数据结构第三章-贪心算法

预备知识：贪心法，钞票支付问题

] 当加入7元面额时，就不存在倍数关系了，当前最优解就不一定是全局最优解

分发饼干

#easy 455. 分发饼干 - 力扣（LeetCode）每个孩子有需求因子g，每个糖果有大小s，当s>=某的孩子的需求因子g，表示可以满足这个孩子，每个孩子只能用1个糖果满足 实现方法如下

class Solution {

public:

    int findContentChildren(vector<int>& g, vector<int>& s) {

       std::sort(g.begin(),g.end());

       std::sort(s.begin(),s.end()); //对g和s进行排序

       int child = 0;

       int cookie = 0;//child表示以满足了几个孩子，cookie表示尝试了几个糖果

       while(child<g.size()&&cookie<s.size()){//当糖果或孩子全被吃光

            if(g[child]<=s[cookie]){//当满足因子小于或者等于糖果大小时候

                child++;//糖果满足孩子，孩子指针后移

            }

            cookie++;//无论成功失败，每一个糖果只尝试一次

       }

       return child;//最终chlid即为得到满足的孩子的个数

    }

};

摇摆序列

#medium 376. 摆动序列 - 力扣（LeetCode）摇摆序列的定义

一个整数系列，如果两个相邻元素的差恰好正负（负正）交替出现 一个小于2的元素序列直接为摇摆序列比如[1,6,4,9,2,5]为摇摆序列，而[1,4,7,2,5]不是.

给定一个随机序列，求这个满足摇摆序列定义的最长子序列的长度

子序列：任意删除或者不删除某个元素，且不改变顺序。

显然选择15最好，因为15给予后面数字的下降的空间要更大，更贪 所以我们可以总结以下规律： ~~TMD怎么又是自动机~~

class Solution {

public:

    int wiggleMaxLength(vector<int>& nums) {

        if(nums.size() < 2){

            return nums.size();

        }

        static const int BEGIN = 0;

        static const int UP = 1;

        static const int DOWN = 2;

        int STATE = BEGIN;

        int max_length =1;//摇摆序列长度至少为1

        for(int i = 1;i<nums.size();i++){//从第二个元素开始扫描

            switch(STATE){//起始状态

                case BEGIN:

                if(nums[i-1]<nums[i]){

                    STATE = UP;

                    max_length++; //每次切换状态长度加一

                }

                else if(nums[i-1]>nums[i]){

                    STATE = DOWN;

                    max_length++;

                }

                break;

                case UP://上升状态

                if(nums[i-1]>nums[i]){

                    STATE = DOWN;

                    max_length++;

  

                }

                break;

                case DOWN://下降状态

                if(nums[i-1]<nums[i]){

                    STATE = UP;

                    max_length++;

                }

                break;

            }

        }

        return max_length;

    }

};

如果要求出最长子序列的话相当于切换的时候把对应的数字push进一个vector

移除k个数字

#medium 402. 移掉 K 位数字 - 力扣（LeetCode）已知使用字符串表示的非负整数num，将num里面的k个数字移除，求移除k个数字后，可以获得的_最小的_数字,长度最大可以到10002 显然不能枚举，枚举也没法比较，大等数加减会溢出思路一定是线性的示例

输入num = “1432219” k =3 输出：1219

算法思路

当所有数字扫描完成，k依然大于0，怎么办

继续弹栈直到k归零

当数字有0出现怎么办

number是0不代表不能加进栈里，只要栈不空就可以加,别让0023这种情况出现就行

            if(number!=0||S.size() != 0 ){

                S.push_back(number);

            }

如何将最后结果存储为字符串并返回

可以用vector当作栈，因为vector可以遍历，就是从尾部pop push就好了

解决方法如下

class Solution {

public:

    string removeKdigits(string num, int k) {

        std::vector<int> S;//使用vector当作栈（因为vector可以遍历

        std::string result = "";//存储最终结果的字符串

        for(int i = 0 ;i<num.length();i++){//从最高位循环扫描数字

            int number = num[i] - '0';//转化为整数

            while(S.size()!= 0 && k>0 && S.back()>number){

                S.pop_back();  //当栈不空，栈顶元素大于number,可以删,弹出栈顶元素

                k--;

            }

            if(number!=0||S.size() != 0 ){

                S.push_back(number);

            }

        }

        while(S.size()!=0 && k>0 ){//栈不空且k>0仍然可以删除数字

            S.pop_back();

            k--;

        }    

        for(int i =0 ;i<S.size();i++){//遍历并放入字符串

                result.append(1,'0'+S[i]);

        }

        if( result == ""){

            result = "0";//如果空就返回0

  

        }

        return result;

    }

};

其中 result.append(1,'0'+S[i]); 是把字符追加进字符串里的意思，第一个参数是追加字符串的数量，第二个参数是追加的字符

中途休息

leetcode可以看点赞量，一般赞的多的题会好一些

跳跃游戏

#medium 55. 跳跃游戏 - 力扣（LeetCode）一个数组存储了非负整型数据，数组中的第i个元素num[i] 代表了可以从数组第i个位置最多向前跳跃nums[i]步，已知各元素，能不能从0跳到数组最后示例

【2，3，1，1，4】可以【3，2，1，0，4】不可以

index表示该点最远可以跳到的位置 算法思路 jump一直往前走，直到jump<max_index 为止

解决方法如下

#include<vector>

class Solution {

public:

    bool canJump(vector<int>& nums) {

            std::vector<int> index;//最远可跳至的位置

            for(int i = 0;i<nums.size();i++){

                index.push_back(i+nums[i]); //计算index数组

            }

            int jump = 0;

            int max_index = index[0];//初始化jump和max_index

            while( jump <= max_index && jump<index.size()){//开始扫描，跳完或者大于max_index结束

                if(max_index<index[jump]){

                    max_index = index[jump];//如果可以跳的更远，就更新max_index

                }

                jump++;//扫描junp

            }

            if(jump == index.size()){//若jump跳至数组为，返回真

                return true;

            }

            return false;

    }

};

跳跃游戏II

#medium 45. 跳跃游戏 II - 力扣（LeetCode）确认可以跳跃到结尾，求最少需要跳跃几次 算法思路 目前最远的位置是current_max_index ,当i超过这个数，说明这个数不够用了，说明应该跳到从上一次循环到current_max_index之间能够跳到最远的那个位置然后重复

解决方案如下

class Solution {

public:

    int jump(vector<int>& nums) {

        if(nums.size() < 2){//如果数组长度小于2说明不用跳跃

            return 0;

        }

        int current_max_index = nums[0];//当前可到达的最远位置

        int pre_max_max_index = nums[0];//遍历各个位置过程中，可到达的最远位置

        int jump_min = 1;

        for(int i = 1;i<nums.size();i++){

            if(i>current_max_index){//无法向前移动之后再进行跳跃

                jump_min++;

                current_max_index = pre_max_max_index;// 更新当前可达到的最远的位置

            }

            if(pre_max_max_index<nums[i]+i){

                pre_max_max_index = nums[i] + i;//更新pre_max_max_index

            }

        }

        return jump_min;

    }

};

你可能没看懂 ~~我也没看懂~~ 再解释以下：

current_max_index 指的是目前能够到达的最远处(此处指的是i+1),当i指向i+1的位置的时候，i 并没有到达数组尾部，说明目前最远的位置也无法跳完数组。此时就需要从上一次跳跃的结尾(此处是0)，到本次跳跃的结尾之间找到能跳跃最远的位置，也就是pre_max_max_index(此处是i-2 他跳跃的目的地是n)，也就是说在本次跳跃里面能到达的最远的位置就是n。如果n还没到，就重复下一次循环。上一次的pre_max_max_index就是下一次的current_max_index

射击气球

~~我踏马社保~~ #medium 452. 用最少数量的箭引爆气球 - 力扣（LeetCode）已知平面上有一定数量的气球，平面可以看作一个坐标系，平面的x周不同位置安排弓箭手向y轴方向射箭，弓箭可以走无穷远，给定气球宽度xstart<=x<=xend 问至少需要几个弓箭手，才能全部打爆气球样例：

输出：2
解释：气球可以用2支箭来爆破:
-在x = 6处射出箭，击破气球[2,8]和[1,6]。
-在x = 11处发射箭，击破气球[10,16]和[7,12]。

应该用贪心算法废话 算法思路

解决方法如下

bool cmp(const std::vector<int>&a,const std::vector<int>&b);

class Solution {

public:

    int findMinArrowShots(vector<vector<int>>& points) {

            if(points.size() == 0){

                return 0; //传入的数据可能为空

            }

            std::sort(points.begin(),points.end(),cmp);//对气球按照左端点从小到达排序

            int shoot_num = 1;   //初始化弓箭手数量

            int shoot_begin = points[0][0]; //初始化射击区间

            int shoot_end = points[0][1]; //为两端点

            for(int i = 1;i < points.size();i++){

                if(points[i][0] <= shoot_end){//如果新的左端点比shoot_end小

                    shoot_begin = points[i][0];//更新的射击区间左端点位新气球左端点

                    if(shoot_end>points[i][1]){//当射击右端点大于新气球右端点的时候

                        shoot_end = points[i][1];

                    }

                }

                else {//在保证当前气球被射穿的条件下，射击区间不能再更新了，需要添加一个新的射击区间

                    shoot_num++;

                    shoot_begin = points[i][0];

                    shoot_end = points[i][1];

                }  

            }

            return shoot_num;

    }

};

  

bool cmp(const std::vector<int>&a,const std::vector<int>&b){

    return a[0]<b[0];

}

两个if语句嵌套是因为只有当外层if语句的条件满足时，才会执行内层的if语句，在这种情况下，内层的if语句用于更新shoot_end的值为新气球的右端点（points[i][1]），如果它小于当前的shoot_end值。这样可以确保射击范围覆盖到目前为止遇到的所有气球。内层的if语句仅在新气球的左端点（points[i][0]）小于或等于shoot_end时才相关，这是由外层的if语句检查的。

最优加油方法

#hard 2431 -- Expedition (poj.org) 一辆公路上，有一个起点和一个终点，这之间有N个加油站，已知这N个加油站到终点的距离d与各个加油站可以加油的量l，起点位置至终点的距离L，与起始时刻油箱中的汽油量P，假设1个单位的汽油走一个单位的距离，油箱没有上限，最少加几次油能从起点开到终点，到不了就返回-1 示例如下

Input

* Line 1: A single integer, N  
  
* Lines 2..N+1: Each line contains two space-separated integers describing a fuel stop: The first integer is the distance from the town to the stop; the second is the amount of fuel available at that stop.  
  
* Line N+2: Two space-separated integers, L and P

Output

* Line 1: A single integer giving the minimum number of fuel stops necessary to reach the town. If it is not possible to reach the town, output -1.

Sample Input

4
4 4
5 2
11 5
15 10
25 10

Sample Output

2

思路如下 思路和[[第三章：贪心算法#跳跃游戏II|跳跃游戏II]]类似，都是到不能解决问题之后再返回 算法思路

解决方法如下

bool cmp(const std::pair<int,int>&a,const std::pair<int,int>&b){
    return a.first>b.first;
}

bool cmp(const std::pair<int,int>&a,const std::pair<int,int>&b);
int get_minimum_stop(int L,int P,std::vector<std::pair<int,int> >&stop){
    std::priority_queue<int> Q;//存储油量的最大堆 
    int result = 0;
    stop.push_back(std::make_pair(0,0));//将终点也作为一个停靠点
    std::sort(stop.begin(),stop.end(),cmp); //以停靠点至终点距离从大到小进行排序
    for(int i = 0;i<stop.size();i++){//遍历各个停靠点 
        int dis = L-stop[i].first;//当前要走的距离即为当前距离终点的距离 L减去下一个停靠点距离终点距离 
        while(P < dis&&!Q.empty()){//走不到且Q不空 ，一直加油直到能走过
            P=P+Q.top();//加油 
            Q.pop();//弹出最大油 
            result++;//加一次次数 
        } 
        if(P< dis&&Q.empty()){//空了，走不到 
            return -1;
        }
        P = P - dis;//重置油量
        L =stop[i].first;//重置距离
        Q.push(stop[i].second);/把油放进堆里面
    } 
    return result;
}

输入输出代码

int main(){
    std::vector<std::pair<int,int > >stop;
    int N;
    int L;
    int P;
    int distance;
    int fuel;
    scanf("%d",&N);
    for(int i = 0;i<N;i++){
        scanf("%d %d",&distance,&fuel);
        stop.push_back(std::make_pair(distance,fuel));
        
    }
    scanf("%d %d",&L,&P);
    printf("%d\n",get_minimum_stop(L,P,stop));
    return 0;
}

下课

下节课传送门[[第四章：递归，回溯和分治]]

本次课程的DLC

北理工也有一道经典题型是用贪心算法来解决的，题目如下 没找到OJ,没准乐学有，估计也没法提交了~~C语言程序设计基础第六周~~

北理工的恶龙

#easy 我刚发现这道题的题源是UVa 11292就改了一个名字，少了重复输入 题目如下最近，北理工出现了一只恶龙，它长着很多头，而且还会吐火，它将会把北理工烧成废墟，于是，校长下令召集全校所有勇士杀死这只恶龙。（~~龙腾：你确定？？~~）要杀死这只龙，必须把它所有的头都砍掉，每个勇士只能砍一个龙头，龙的每个头大小都不一样，一个勇士只有在身高不小于龙头的直径的情况下才能砍下它。而且勇士们要求，砍下一个龙头必须得到和自己身高厘米数一样的学分。校长想花最少的学分数杀死恶龙，于是找到你寻求帮助

输入输出示例如下

输入：
第一行 龙头数 n , 勇士人数 m （ 1<=n, m<=100 ） 接下来 n 行，每行包含一个整数，表示龙头的直径 接下来 m 行，每行包含一个整数，表示勇士的身高 l

输出：
如果勇士们能完成任务，输出校长需要花的最小费用；否则输 出 "bit is doomed! ”

序号	测试输入	期待的输出
1	`2 3↵`
`5↵`
`4↵`
`7↵`
`8↵`
`4↵`	`11↵`	0
2	`2 1↵`
`5↵`
`5↵`
`10↵`	`bit is doomed!↵`

思路 ~~这回真的是我自己的~~ 所以在本道题里，局部的目标就是以最矮的学生唔叼来处理最小的龙，学生从最小的开始遍历，直到杀完龙 贪心规律 我们用队列来处理龙，把龙和学生从小到大排列，把龙放进一个队列里，当学生（目前能杀这跳龙的最小的一位）能够杀这一条龙的时候，把这条龙头弹出队列，继续遍历

解决方法如下

#include<vector>
#include<algorithm>
#include<queue>
#include<stdio.h>
bool cmp(int a,int b){
    return a<b;
}
int dead_or_not(std::vector<int> dragon,std::vector<int>hero,int n,int m){
    sort(dragon.begin(),dragon.end(),cmp);//对龙和人进行从小到大的排序 
    sort(hero.begin(),hero.end(),cmp);
    std:: queue<int> dragon_q;//定义队列龙 
    for(int i =0;i<n;i++){
        dragon_q.push(dragon[i]);//把龙压入队列 
    }
    int score = 0;//初始化成绩为0 
    for(int i = 0;i<m;i++){//遍历所有学生 
        if(hero[i] >= dragon_q.front()){//如果学生的值比龙大 
            dragon_q.pop();//弹出龙 
            score= score+hero[i];//计算成绩 
        }
        if(dragon_q.empty()){//如果遍历过程中龙空了，说明龙已经杀完了 
            break; //弹出 
        }	
    }
    if(dragon_q.empty()){//如果龙空了 
        return score;//返回成绩 
    }
    else{
        return 0;//返回0，你总不能一条也没杀吧 
    }
    
}

测试代码如下

int main(void){
    int n;
    int m;
    std::vector<int>dragon;
    std::vector<int>hero;
    scanf("%d %d",&n,&m);//获得数量 
    for(int i = 0;i<n;i++){//龙头和人头， 
        int temp;
        scanf("%d",&temp);
        dragon.push_back(temp);
    }
    for(int i = 0; i<m;i++){
        int temp;
        scanf("%d",& temp);
        hero.push_back(temp);
    }
    int score = dead_or_not(dragon,hero,n,m);//获得成绩 
    if(score){
        printf("%d",score);
    }
    else{
        printf("bit is doomed!");
    }

    return 0;
}

BTW

if(dragon_q.empty()){//如果遍历过程中龙空了，说明龙已经杀完了 
            break; //弹出 
        }

这行代码用于判断遍历过程中龙的队列会不会空，如果空了之后还进行pop操作可能会导致意外的结果

总时间复杂度为O($n\log{n}+m\log{m}+m$)

关于UVa 11292的解法的源码我po在下面，和北理工的恶龙一样，只是多了层循环嵌套而已，别忘了在第二次输入的时候清空vector ，还有设置终止命令 UVa太卡了可以上poj-3646平替一下，这俩是一道题

#include<vector>
#include<algorithm>
#include<queue>
#include<stdio.h>
bool cmp(int a,int b){
    return a<b;
}
int dead_or_not(std::vector<int> dragon,std::vector<int>hero,int n,int m){
    sort(dragon.begin(),dragon.end(),cmp);//对龙和人进行从小到大的排序 
    sort(hero.begin(),hero.end(),cmp);
    std:: queue<int> dragon_q;//定义队列龙 
    if(n==0&&m==0){//设置结束点 
        return -1;
    }
    for(int i =0;i<n;i++){
        dragon_q.push(dragon[i]);//把龙压入队列 
    }
    int score = 0;//初始化成绩为0 
    for(int i = 0;i<m;i++){//遍历所有学生 
        if(hero[i] >= dragon_q.front()){//如果学生的值比龙大 
            dragon_q.pop();//弹出龙 
            score= score+hero[i];//计算成绩 
        }
        if(dragon_q.empty()){//如果遍历过程中龙空了，说明龙已经杀完了 
            break; //弹出 
        }	
    }
    if(dragon_q.empty()){//如果龙空了 
        return score;//返回成绩 
    }
    else{
        return 0;//返回0
    }
    
} 
/*输入输出代码*/
int main(void){
    int n;
    int m;
    std::vector<int>dragon;
    std::vector<int>hero;
    std::vector<int>score;
    scanf("%d %d",&n,&m);//获得数量 
    while(n!=0&&m!=0){
    
        for(int i = 0;i<n;i++){//龙头和人头， 
            int temp;
            scanf("%d",&temp);
            dragon.push_back(temp);
        }
        for(int i = 0; i<m;i++){
            int temp;
            scanf("%d",& temp);
            hero.push_back(temp);
        }
        score.push_back(dead_or_not(dragon,hero,n,m));//获得成绩 
        dragon.clear();
        hero.clear();
        scanf("%d %d",&n,&m);//获得数量 
    }
        for(int i = 0; i<score.size();i++){
            if(score[i]&&score[i]!=-1){
                printf("%d\n",score[i]); //如果没结束而且杀了
            }
            else if(score[i] == 0){//如果没杀了
                printf("Loowater is doomed!\n");
            }
            else{//如果结束了
                return 0;//当输入为0 0 是函数结束 
            }
        }
    
        return 0;
}

就这样了，顺带一提，就这么直接借鉴人家的题真的好么

就这样，这下是真结束了