• 1

  • 449

  • 收藏

贪心算法 —— Leetcode系列

2个月前
  • 本文章系列为笔者leetcode刷题的记录、复习与分享,有错误的地方欢迎指正。

贪心算法(又称贪婪算法)是指,在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。

分配问题

分发饼干

思路: 把孩子和饼干排序,给最小饥饿度的孩子分配最小的能饱腹的饼干。

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        int child = 0;
        int cookies = 0;
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        while(child < g.size() && cookies < s.size()){
            if(g[child]<=s[cookies]) child++;
            cookies++;
        }
        return child;
    }
};
复制代码

分发糖果

思路:需要简单的两次遍历,把所有孩子的糖果数初始化为 1;先从左往右遍历一遍,如果右边孩子的评分比 左边的高,则右边孩子的糖果数更新为左边孩子的糖果数加1;再从右往左遍历一遍,如果左边孩子的评分比右边的高,且左边孩子当前的糖果数不大于右边孩子的糖果数,则左边孩子的糖果数更新为右边孩子的糖果数加1。

这里的贪心策略即为,在每次遍历中,只考虑并更新相邻一侧的大小关系。

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        if(size<2) return size;
        vector<int> candy(size,1);
        for(int i =0;i <size-1;i++){
            if(ratings[i+1]>ratings[i]){
                candy[i+1] = candy[i]+1;
            }
        }
        for(int i = size -1;i>0;i--){
            if(ratings[i-1]>ratings[i]){
                candy[i-1] = max(candy[i-1],candy[i]+1);
            }
        }
        return accumulate(candy.begin(),candy.end(),0);
    }
};
复制代码

种花问题

思路:从左向右遍历花坛,在可以种花的地方就种一朵,能种就种(因为在任一种花时候,不种都不会得到更优解),就是一种贪心的思想。

这里可以种花的条件是:

  • 自己为空
  • 左边为空 或者 自己是最左
  • 右边为空 或者 自己是最右

代码如下:

class Solution {
public:
    bool canPlaceFlowers(vector<int>& flowerbed, int n) {
        int s = flowerbed.size();
        for(int i =0;i<s;i++){
            if(flowerbed[i] ==0 && (i==0 || flowerbed[i-1]==0 ) && (i==s-1 || flowerbed[i+1]==0)){
                n--;
                if(n<=0) return true;
                flowerbed[i] =1;
            }
        }
        return n<=0;
    }
};
复制代码

区间问题

无重叠区间

思路: 先把区间按照结尾的大小进行增序排序,每次选择结尾最小且和前一个选择的区间不重叠的区间

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()) return 0;
        int n = intervals.size();
        if(n<2) return 0;
        sort(intervals.begin(),intervals.end(), [](vector<int> a,vector<int>b){
            return a[1]<b[1];
        });
        int count =0,prev = intervals[0][1];
        for(int i = 1;i<n;i++){
            if(intervals[i][0]<prev){
                count++;
            } else {
                prev = intervals[i][1];
            }
        }
        return count;
    }
};
复制代码

用最少数量的箭引爆气球

思路:区间贪心问题:给定n个闭区间[x,y],插入一个点使得落到最多的闭区间中,问最少需要确定多少个点

  • 区间结尾排序
  • 拿当前区间的右端作为标杆(在保证当面区间被射到的前提下,尽可能找多的重合区间)。
  • 只要下一个区间的左端<=标杆下一个区间的左端<=标杆,则重合,继续寻求与下一个区间重合
  • 直到遇到不重合的区间,弓箭数+1
  • 拿新区间的右端作为标杆,重复以上步骤

代码如下:

class Solution {
public:
    int findMinArrowShots(vector<vector<int>>& points) {
        int n = points.size();
        if(n<=1) return n;
        sort(points.begin(), points.end(), [](vector<int> A, vector<int> B){
            return A[1]<B[1];//不可以用开头排序,因为不能确保包含的区间是否重合(如[0,9],[0,6],[7,8])
        });
        int cur = points[0][1],count = 1;
        for(int i = 1; i<n;i++){
            if(points[i][0]>cur){
                count++;
                cur = points[i][1];
            }
        }
        return count;
    }
};
复制代码

划分字母区间

思路:由于同一个字母只能出现在同一个片段,显然同一个字母的第一次出现的下标位置和最后一次出现的下标位置必须出现在同一个片段。因此需要遍历字符串,得到每个字母最后一次出现的下标位置 在得到每个字母最后一次出现的下标位置之后,可以使用贪心的方法将字符串划分为尽可能多的片段,具体做法如下。

  • 从左到右遍历字符串,遍历的同时维护当前片段的开始下标start和结束下标end,初始时start=end=0

  • 对于每个访问到的字母,得到当前字母的最后一次出现的下标位置,令end=max(end,end1)

  • 当访问到下标end 时,当前片段访问结束,当前片段的长度为end−start+1,将当前片段的长度添加到返回值,然后令start=end+1,继续寻找下一个片段。

重复上述过程,直到遍历完字符串。

class Solution {
public:
    vector<int> partitionLabels(string S) {
        int map[26] = {-1};
        vector<int> res;
        int star = 0, end = 0;
        for(int i = 0; i < S.size(); i++) {
            map[S[i] - 'a'] = i;
        }
        for(int i = 0; i < S.size();i++){
            end = max(end, map[S[i] - 'a']);
            if(i == end){
                res.push_back(end-star+1);
                star = i+1;
            }
        }
        return res;
    }
};
复制代码
免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

程序员

449

相关文章推荐

未登录头像

暂无评论