前言

在这里插入图片描述

个人主页:@小沈YO.
小编介绍:欢迎来到我的乱七八糟小星球
专栏:贪心算法
本章内容:贪心算法
记得 评论 +点赞 +收藏 +关注哦~


一、贪心算法:

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是最好或最优的算法。贪心算法解决问题的过程中,每一步都做出一个看似最优的决策,这个决策依赖于当前问题状态,不依赖于解决问题的前面的步骤和将来的步骤。这种方法在很多情况下并不会得到最优解,但是在某些问题上贪心算法的解就是最优解。

二、贪心算法示例:

1.1 柠檬⽔找零

  1. 题⽬链接:860. 柠檬⽔找零
  2. 题⽬描述
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    分情况讨论:
    a. 遇到 5 元钱,直接收下;
    b. 遇到 10 元钱,找零 5 元钱之后,收下;
    c. 遇到 20 元钱:
    i. 先尝试凑 10 + 5 的组合;
    ii. 如果凑不出来,拼凑 5 + 5 + 5 的组合;
  4. C++代码
class Solution {
public:
    bool lemonadeChange(vector<int>& bills) 
    {
        int five=0,ten=0;
        for(int i=0;i<bills.size();i++)
        {
            if(bills[i]==5)
                five++;
            else if(bills[i]==10)
            {
                ten++;
                if(five>0)five--;
                else return false;
            }
            else
            {
                if(ten>0&&five>0)//贪心
                {
                    ten--;
                    five--;
                }
                else if(five>=3)five-=3;
                else return false;
            }
        }
        return true;
    }
};

1.2 将数组和减半的最少操作次数

  1. 题⽬链接:2208. 将数组和减半的最少操作次数
  2. 题⽬描述:
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    a. 每次挑选出「当前」数组中「最⼤」的数,然后「减半」
    b. 直到数组和减少到⾄少⼀半为⽌。
    为了「快速」挑选出数组中最⼤的数,我们可以利⽤「堆」这个数据结构
  4. C++代码
class Solution {
    double sum=0,cnt=0;
    priority_queue<double,vector<double>,less<double>> pq;
public:
    int halveArray(vector<int>& nums) 
    {
        for(auto&e:nums)
        {  
            sum+=e;
            pq.push(e);
        }
        sum/=2.0;
        while(sum>0)
        {
            cnt++;
            double tmp=pq.top()/2;
            pq.pop();
            sum-=tmp;
            pq.push(tmp);
        }
        return cnt;
    }
};

1.3 最⼤数

  1. 题⽬链接:179. 最⼤数
  2. 题⽬描述
    在这里插入图片描述
  3. 解法(贪⼼):
    可以先优化:将所有的数字当成字符串处理,那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。
    贪⼼策略:按照题⽬的要求,重新定义⼀个新的排序规则,然后排序即可。
    排序规则:
    a. 「A 拼接 B」 ⼤于 「B 拼接 A」,那么 A 在前,B 在后;
    b. 「A 拼接 B」 等于 「B 拼接 A」,那么 A B 的顺序⽆所谓;
    c. 「A 拼接 B」 ⼩于 「B 拼接 A」,那么 B 在前,A 在后;
  4. C++代码
class Solution {
public:
    string largestNumber(vector<int>& nums) 
    {
        vector<string> v;
        for(auto&e:nums)
        v.push_back(to_string(e));
        string ret;
        sort(v.begin(),v.end(),[](string& s1,string& s2){
            return s1+s2>s2+s1;
        });
        for(int i=0;i<v.size();i++)
        {
            if(i==0&&v[i]=="0")return "0";
            ret+=v[i];
        }
        return ret;
    }
};

1.4 摆动序列

  1. 题⽬链接:376. 摆动序列
  2. 题⽬描述
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    对于某⼀个位置来说:
    ◦ 如果接下来呈现上升趋势的话,我们让其上升到波峰的位置;
    ◦ 如果接下来呈现下降趋势的话,我们让其下降到波⾕的位置。
    因此,如果把整个数组放在「折线图」中,我们统计出所有的波峰以及波⾕的个数即可。
  4. C++代码
class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) 
    {
        int left=0,ret=0;
        for(int i=0;i<nums.size()-1;i++)
        {
            int right=nums[i+1]-nums[i];
            if(right==0)continue;
            if(right*left<=0)ret++;
            left=right;
        }
        return ret+1;//加上最后一个
    }
};

1.5 最⻓递增⼦序列

  1. 题⽬链接:300. 最⻓递增⼦序列
  2. 题⽬描述:
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    我们在考虑最⻓递增⼦序列的⻓度的时候,其实并不关⼼这个序列⻓什么样⼦,我们只是关⼼最后⼀个元素是谁这样新来⼀个元素之后,我们就可以判断是否可以拼接到它的后⾯
    因此,我们可以创建⼀个数组,统计⻓度为 x 的递增⼦序列中,最后⼀个元素是谁。为了尽可能的让这个序列更⻓,我们仅需统计⻓度为 x 的所有递增序列中最后⼀个元素的「最⼩值」。
    统计的过程中发现,数组中的数呈现「递增」趋势,因此可以使⽤「⼆分」来查找插⼊位置
  4. C++代码
class Solution {
    int cnt=0;
public:
    int lengthOfLIS(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for(int i=1;i<nums.size();i++)
        {
            if(nums[i]>ret.back())ret.push_back(nums[i]);//可以拼接到后面
     //如果不可以拼接到末尾则需要找到ret中出现第一次>=nums[i]的值进行替换,也就是把这个第一次大的值换成小的nums[i]
            else
            {
                int left=0,right=ret.size()-1;
                while(left<right)
                {
                    int mid=left+(right-left)/2;
                    if(ret[mid]>=nums[i])right=mid;
                    else left=mid+1;
                }
                ret[left]=nums[i];
            }
        }
        return ret.size();
    }
};

1.6 递增的三元⼦序列

  1. 题⽬链接:334. 递增的三元⼦序列
  2. 题⽬描述
    在这里插入图片描述
  3. 解法(贪⼼):
    贪⼼策略:
    最⻓递增⼦序列的简化版。
    不⽤⼀个数组存数据,仅需两个变量即可。也不⽤⼆分插⼊位置,仅需两次⽐较就可以找到插⼊位置
  4. C++代码
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) 
    {
        int n=nums.size();
        vector<int> ret;
        ret.push_back(nums[0]);
        for(int i=1;i<n;i++)
        {
            if(nums[i]>ret.back())ret.push_back(nums[i]);
            else
            {
                int left=0,right=ret.size()-1;
                while(left<right)
                {
                    int mid=left+(right-left)/2;
                    if(nums[i]>ret[mid])left=mid+1;
                    else right=mid;
                }
                ret[left]=nums[i];
            }
        }
        return ret.size()>=3?true:false;
    }
};
----------------------------------------------------------------------------------------------
class Solution {
public:
    bool increasingTriplet(vector<int>& nums) 
    {
        int n=nums.size();
        int a=nums[0],b=INT_MAX;
        for(int i=1;i<n;i++)
        {
            if(nums[i]>b)return true;
            else
            {
                if(nums[i]<=a)a=nums[i];
                else b=nums[i];
            }
        }
        return false;
    }
};

点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部