您现在的位置是:首页 >技术交流 >力扣贪心算法专题(三)力扣题 452、435、763、56、738、968、714 思路及C++实现网站首页技术交流

力扣贪心算法专题(三)力扣题 452、435、763、56、738、968、714 思路及C++实现

虚假自律就会真自律! 2024-06-26 14:23:43
简介力扣贪心算法专题(三)力扣题 452、435、763、56、738、968、714 思路及C++实现

贪心算法

  1. 贪心的本质是选择每一阶段的局部最优,从而达到全局最优。如何通过局部最优,推出整体最优。
  2. 贪心算法的套路就是常识性推导加上举反例
  3. 贪心算法解题思路:想清楚局部最优是什么,如果推导出全局最优,就够了。

452. 用最少数量的箭引爆气球

在这里插入图片描述

思路:

  • 只射重叠最多的气球,用的弓箭一定最少。
  • 贪心算法局部最优:当气球出现重叠,一起射,所用弓箭最少。全局最优:把所有气球射爆所用弓箭最少。

做法:

  • 把气球排序,从前到后(从后向前)遍历气球,仅跳过被射过的气球,记录箭的数量。
  • 按照气球的起始位置排序,从前向后遍历气球数组,靠左尽可能让气球重复。如果气球重叠了,重叠气球中右边边界的最小值 之前的区间一定需要一个弓箭。
  • 例如,[[10,16],[2,8],[1,6],[7,12]]为例。排序后,[[1,6], [2,8], [7,12], [10,16]]。首先第一组重叠气球[1,6]和[2,8],一定需要一支箭;[7,12]气球3的左边界大于了 第一组重叠气球[1,6]的最小右边界,所以还需要一支箭来射气球3。

代码:

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[0]<b[0];
    }
    int findMinArrowShots(vector<vector<int>>& points) {
        if(points.size()==0) return 0;//如果没有气球 不需要箭
        sort(points.begin(), points.end(), cmp);//排序
        int result = 1;//至少需要一支箭
        for(int i=1; i<points.size(); i++)//注意从第二个气球开始
        {
            //如果气球不重叠 当前气球的头 在 上一个气球的尾后面 需要一只箭
            //不取= 是因为题目中满足xstart ≤ x ≤ xend,则该气球会被引爆。
            //那么说明两个气球挨在一起不重叠也可以一起射爆
            if(points[i][0] > points[i-1][1]) result++;
            //如果气球重叠  更新重叠气球最小右边界
            else points[i][1] = min(points[i-1][1], points[i][1]);
        }
        return result;
    }
};

435. 无重叠区间

做法1 右边界排序 不重叠区间

思路: 这和452.用最少数量的箭引爆气球非常像,弓箭数相当于是非交叉区间的数量。不同的是,题目中认为[0,1]和[1,2]不是相邻区间,注意判断条件的修改,然后用总区间数减去弓箭数量 就是要移除的区间数量了。

代码:

class Solution {
public:
    static bool cmp_r(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];
    }
    static bool cmp_l(const vector<int>& a, vector<int>& b)
    {
        return a[0] < b[0];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return 0;
       
        //做法1 右边界排序 重叠区间
        sort(intervals.begin(), intervals.end(), cmp_r);
        int count = 1;//不重叠区间数
        for(int i=1; i<intervals.size(); i++)
        {
            //注意 [0,1]和[1,2]不是相邻区间
            if(intervals[i][0] >= intervals[i-1][1]) count++;
            else intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);
        }
        return intervals.size() - count;
    }
};

做法2 右边界排序 不重叠区间

思路: 让区间尽可能重叠,首先右边界按照从小到大排序,从左向右遍历记录非交叉区间的个数,最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

代码:

class Solution {
public:
    static bool cmp_r(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];
    }
    static bool cmp_l(const vector<int>& a, vector<int>& b)
    {
        return a[0] < b[0];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return 0;

        //做法2 右边界排序 不重叠区间
        sort(intervals.begin(), intervals.end(), cmp_r);
        int count = 1;//记录非交叉区间的个数
        int end = intervals[0][1];//分割点
        for(int i=1; i<intervals.size(); i++)
        {
            //如果当前区间的尾巴 在 上一个区间的头前面 说明不重叠
            if(end <= intervals[i][0])
            {
                count++;
                end = intervals[i][1];//更新区间尾巴
            }
        }
        return intervals.size() - count;
    }
};

做法3 左边界排序 重叠区间

代码:

class Solution {
public:
    static bool cmp_r(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];
    }
    static bool cmp_l(const vector<int>& a, vector<int>& b)
    {
        return a[0] < b[0];
    }

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.size()==0) return 0;

        //做法3 左边界排序 重叠区间
        sort(intervals.begin(), intervals.end(), cmp_l);
        int count = 0;//记录重叠区间
        for(int i=1; i<intervals.size(); i++)
        {
            //如果当前区间的头 在 上一个区间的尾巴前面 说明重叠
            //注意 [0,1]和[1,2]不是相邻区间
            if(intervals[i][0] < intervals[i-1][1])
            {
                intervals[i][1] = min(intervals[i][1], intervals[i-1][1]);//更新最小右边界
                count++; 
            }
        }
        return count;
    }
};

763.划分字母区间

在这里插入图片描述

做法1

思路:
用最远出现距离模拟了圈字符的行为,要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了,可以分为如下两步:

  • 统计每一个字符最后出现的位置;
  • 从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点。

代码:

class Solution {
public:
    vector<int> partitionLabels(string s) {
        int hash[27] = {0};//保存字母最后出现的位置 
        //统计字母最后出现的位置
        //i为字符,hash[i]为字符出现的最后位置
        for(int i=0; i<s.size(); i++)
        {
            hash[s[i] - 'a'] = i;
        }
        vector<int> result;
        int left = 0;
        int right = 0;
        //找到最远边界
        for(int i=0; i<s.size(); i++)
        {
            right = max(right, hash[s[i] - 'a']);
            if(i == right)//最远边界和下标相同
            {
                result.push_back(right - left + 1);
                left = i + 1;//left要更新 跳到i+1位置开始新的划分起点
            }
        }
        return result;
    }
};

做法2

思路:
统计字符串中所有字符的起始和结束位置,记录这些区间,实际上也就是435.无重叠区间题目里的输入,将区间按左边界从小到大排序,找到边界将区间划分成组,互不重叠,找到的边界就是答案。
首先要获得435.无重叠区间题目里的输入,然后按照435.无重叠区间题目里的思路去写。

代码:

class Solution {
public:
    //做法2
    //首先获得区间输入
    vector<vector<int>> countLabels(string s)
    {
        vector<vector<int>> hash(26, vector<int>(2, INT_MIN));//记录区间 默认26哥字母
        vector<vector<int>> hash_filter;
        //记录每个字母出现的起始位置
        for(int i=0; i<hash.size(); ++i)
        {
            if(hash[s[i] - 'a'][0] == INT_MIN) hash[s[i] - 'a'][0] = i;//最开始位置
            hash[s[i] - 'a'][1] = i;//最末尾位置
        }
        //去掉s中没有出现的字母的区间
        for(int i=0; i<s.size(); ++i)
        {
            if(hash[i][0] != INT_MIN) hash_filter.push_back(hash[i]);//存放出现字母对应区间
        }
        return hash_filter;
    }

    //排序 左边界排序
    static bool cmp(vector<int>& a, vector<int>& b)
    {
        return a[0] < b[0];
    }
    //找出重叠区间的长度个数
    vector<int> partitionLabels(string s)
    {
        vector<int> result;//记录区间分割点
        //获得s各字母的起始区间
        vector<vector<int>> hash = countLabels(s);
        sort(hash.begin(), hash.end(), cmp);//按照左边界排序
        int right = hash[0][1];// 记录最大右边界
        int left = 0;
        //找到分割点
        for(int i=1; i<hash.size(); ++i)
        {
            //当前区间的头 在 上一区间的尾部 前面
            if(hash[i][0] > right)
            {
                result.push_back(right - left + 1);//存放长度
                left = hash[i][0];//left左边界更新 找下一个重叠区间长度
            }
            right = max(right, hash[i][1]);//right最远右边界更新 找下一个重叠区间长度
        }
        result.push_back(right - left + 1);//最右端
        return result;
    }
};

56. 合并区间

在这里插入图片描述

思路:
和435.无重叠区间题目思路类似,找重叠区间,不同的是用合并区间后左边界和右边界,作为一个新的区间,加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。

代码:

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        vector<vector<int>> result;
        //lambda表达式 左边界排序
        sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});
        //左边界排序后 result.back()的左边界一定是最小值 只需要跟新右区间
        result.push_back(intervals[0]);//先存放第一个区间左边界 肯定是最小的边界
        for(int i=1; i<intervals.size(); i++)
        {
            // 区间重叠 当前区间的头部 在上一个区间的 尾部前面
            if(result.back()[1] >= intervals[i][0]) result.back()[1] = max(result.back()[1], intervals[i][1]);
            else result.push_back(intervals[i]);// 区间不重叠
        }
        return result;
    }
};

738.单调递增的数字

在这里插入图片描述

暴力解法

依次取位,从个位开始向高位依次判断,数字是否递增;从大到小遍历

代码:

class Solution {
private:
    bool isup(int num)
    {
        int max = 10, temp = 0;//个位最大取9
        while(num)
        {
            temp = num % 10;
            if(max >= temp) max = temp;
            else return false;
            num = num / 10;//前进一位
        }
        return true;
    }
public:
    int monotoneIncreasingDigits(int n) {
        for(int i=n; i>=0; i--)//从大到小逐个判断
        {
            if(isup(i)) return i;
        }
        return 0;
    }
};

贪心算法

一个两位数xy,找小于等于xy的最大单调递增整数,如果x>y,让x–,y=9,即(x-1)9;如果x≤y,不变。从后向前遍历数字。
不可以从前往后遍历,如果按照上述操作,对于三位数等多位数有可能会导致结果不对,例如543,从前往后遍历就变成了439,百位大于十位,不是单调递增数字。从后往前遍历,就是543→539→499

代码:

class Solution {
//贪心算法
public:
    int monotoneIncreasingDigits(int n) {
        //先转成字符串
        string strnum = to_string(n);
        //标记赋值9从哪里开始,设置默认值为strnum.size()
        //防止第二个for循环在flag没有被赋值的情况下执行
        int mark = strnum.size();
        for(int i = strnum.size()-1; i>0; i--)
        {
            if(strnum[i-1] > strnum[i]) 
            {
                mark = i;//标记
                strnum[i-1]--;
            }
        }
        //在标记位置赋值为9
        for(int i = mark; i<strnum.size(); i++)
        {
            strnum[i] = '9';
        }
        return stoi(strnum);
    }

};

968.监控二叉树

分析:

  1. 摄像头都没有在叶子节点上。如果放在叶子节点上,就会浪费一层覆盖;放在叶子节点的父节点位置,才能充分利用摄像头的覆盖面积,即摄像头可以覆盖上中下三层。
  2. 从下往上看。如果从上往下看,头结点不放置,可以省一个摄像头。

思路:
从下往上遍历,后序遍历,左右中顺序,回溯时先给叶子节点父节点放个摄像头,然后隔两个节点放一个摄像头,直至到二叉树头结点。
局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少。

如何放置摄像头?
状态转移的公式,三个数字来表示:
0:该节点无覆盖
1:本节点有摄像头
2:本节点有覆盖
空节点的状态只能是有覆盖,无摄像头就是无覆盖或者有覆盖的状态

单层递归的四种情况:

  1. 情况1:左右节点都有覆盖,那么中间节点就是无覆盖了
  2. 情况2:左右节点至少有一个无覆盖的情况,则中间节点(父节点)应该放摄像头:
  • left == 0 && right == 0 左右节点无覆盖
  • left == 1 && right == 0 左节点有摄像头,右节点无覆盖
  • left == 0 && right == 1 左节点有无覆盖,右节点摄像头
  • left == 0 && right == 2 左节点无覆盖,右节点覆盖
  • left == 2 && right == 0 左节点覆盖,右节点无覆盖
    此时摄像头的数量要加一,并且return 1,代表中间节点放摄像头。
  1. 情况3:左右节点至少有一个有摄像头,那么其父节点就是覆盖的状态
  • left == 1 && right == 2 左节点有摄像头,右节点有覆盖
  • left == 2 && right == 1 左节点有覆盖,右节点有摄像头
  • left == 1 && right == 1 左右节点都有摄像头
  1. 头结点没有覆盖,递归结束之后,还要判断根节点,如果没有覆盖,result++

代码:

class Solution {
private:
    int result;
    /*
    0---无覆盖
    1---有摄像头
    2---有覆盖
    */
    int traversal(TreeNode* cur)
    {
        //空节点,该节点有覆盖
        if(cur == NULL) return 2;
        int left = traversal(cur->left);
        int right = traversal(cur->right);

        //1.左右都有节点 中间节点无覆盖
        if(left == 2 && right == 2) return 0;
        //2.左右节点至少有一个是覆盖  中间节点放摄像头
        if(left == 0 || right == 0)
        {
            result++;
            return 1;
        }
        //3.左右节点至少有一个有摄像头 中间节点有覆盖
        if(left == 1 || right == 1) return 2;

          return -1;
    }

public:
    int minCameraCover(TreeNode* root) {
        result = 0;
        //4.判断头结点无覆盖 +1
        if(traversal(root) == 0) result++;
        return result;
    }
};

714.买卖股票的最佳时机含手续费

在这里插入图片描述
思路:
涉及手续费,要考虑什么时候买卖股票,因为有可能买卖利润不足以支付手续费。
最低价买股票,即买入日期,此时股价最小值。
扣除手续费的最高价卖股票,即卖出日期。只要当前价格大于最低价格+手续费,就可以收获利润。而最终的卖出日期是连续收获利润区间里的最后一天。
收获利润操作时的三种情况:
情况一:最低价时,买入股票
情况二:不买不卖,保持原有状态,买不便宜,卖亏本
情况三:当前价格大于最低价格+手续费时卖出股票,计算利润,不是真的卖出股票,同时记录最小价格,最后一次计算计算利润才是真的卖出股票

代码:

class Solution {
public:
    int maxProfit(vector<int>& prices, int fee) {
        int result = 0;
        int minprice = prices[0];
        for(int i=1; i<prices.size(); i++)
        {
            //低价买入 买入日期
            if(prices[i] < minprice) minprice = prices[i];

            //不买不卖 买不便宜 卖亏本
            if(prices[i] >= minprice && prices[i] <= minprice+fee) continue;

            //计算利润 最后一天计算利润才是真的卖出日期
            if(prices[i] > minprice+fee)
            {
                result += prices[i] - minprice - fee;
                minprice = prices[i] - fee;//每天要更新最低价格
            }
        }
        return result;
    }
};
风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。