算法训练营 - 贪心

目录

算法思想

        过程

该算法存在的问题

示例1.取所有局部最大值

示例二.找到尽可能多的区间

示例3.找到最早结束区间以容纳更多

---

算法思想

• 贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。
• 贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。
• 当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。运用贪心策略在每一次转化时
• 都取得了最优解。问题的最优子结构性质是该问题可用贪心算法求解的关键特征。贪心算法的每一次操作都对结果产生直接影响。贪心算法对每个子问题的解决方案都做出选择，不能回退。
• 贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止。
• 实际上，贪心算法适用的情况很少。一般对一个问题分析是否适用于贪心算法，可以先选择该问题下的几个实际数据进行分析，就可以做出判断。

过程

1.  建立数学模型来描述问题；
2.  把求解的问题分成若干个子问题；
3.  对每一子问题求解，得到子问题的局部最优解；
4.  把子问题的局部最优解合成原来解问题的一个解。

用白话说，即假设一个问题比较复杂，暂时找不到全局最优解，那么我们可以考虑把原问题拆成几个小问题（分而治之思想），分别求每个小问题的最优解，再把这些“局部最优解”叠起来，就“当作”整个问题的最优解了。

该算法存在的问题

• 不能保证求得的最后解是最佳的
• 不能用来求最大值或最小值的问题
• 只能求满足某些约束条件的可行解的范围

示例1.取所有局部最大值

[3, 2, 1, 0, 4]

我们一开始在位置 0 ，可以跳跃的最大长度为 3 ，因此最远可以到达的位置被更新为 3 ；

我们遍历到位置 1 ，由于 1≤3 ，因此位置 1 可达，加上它可以跳跃的最大长度 2 得到 3 ，没有超过最远可以到达的位置；

位置 2 、位置 3 同理，最远可以到达的位置不会被更新；

我们遍历到位置 4 ，由于 4>3 ，因此位置 4 不可达，我们也就不考虑它可以跳跃的最大长度了。

在遍历完成之后，位置 4 仍然不可达，因此我们返回 False 。

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int mostway=0;
        for(int i=0;i<nums.size();i++)
        {
            if(i<=mostway)//如果可以到达当前位置，则更新最大
            {
                mostway=max(mostway,i+nums[i]);
                if(mostway>=nums.size()-1) return true;//能到
            }
            else return false;
            
        }
        return false;
    }
};

示例二.找到尽可能多的区间

力扣

思路：

通过做图发现，我们只需要找到非重叠的最大区间，然后用总数-非重叠最大区间即可得到需要删除的重叠区间。

那么如何找到非重叠的最大区间呢？

        只需要每次选取结束时间最早的区间即可，因为早结束意味着后面可以容纳更多区间

方法：

设intervals[i][0]为区间开始，intervals[i][1]为区间结束

对结束区间排序，那么大于结束区间的第一个开始区间所对应的结束区间结束最早，以此类推，得到尽可能多的的区间

class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];//对第2个元素排序
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int num=1,i=0;
        for(int j=1;j<intervals.size();j++)
        {
            if(intervals[j][0]>=intervals[i][1])//如果右边元素的头>=左边元素的尾
            {
                i=j;
                num++;//说明不是重叠空间
            }
        }
        return intervals.size()-num;
    }
};

 oj版本

#include <iostream>
#include <vector>
#include <string>
#include<algorithm>
using namespace std;
int n;
bool cmp( const vector<int>& a,const vector<int>& b)
{
	return  a[1] < b[1];
}
int main()
{
	cin >> n;
	vector<vector<int>> v(n, vector<int>(2));
	for (int i = 0; i < n; i++) cin >> v[i][0] >> v[i][1];
	sort(v.begin(),v.end(),cmp);
	int num = 1, i = 0;
	for (int j = 1; j < v.size(); j++)
	{
		if (v[j][0] >= v[i][1])
		{
			i = j;
			num++;
		}
	}
	cout << v.size() - num<<endl;
	for (int i = 0; i < n; i++)
	{
		cout << v[i][0] << " " << v[i][1] << endl;
	}
 
 
	return 0;
}

示例3.找到最早结束区间以容纳更多

力扣 

小小复习：优先级队列priority_queue<>

//升序队列
priority_queue <int,vector<int>,greater<int> > q;
//降序队列
priority_queue <int,vector<int>,less<int> >q;
//对于基础类型 默认是大顶堆
priority_queue<int> a; 
//等同于 priority_queue<int, vector<int>, less<int> > a;
 

和队列基本操作相同:

• top 访问队头元素
• empty 队列是否为空
• size 返回队列内元素个数
• push 插入元素到队尾 (并排序)
• emplace 原地构造一个元素并插入队列
• pop 弹出队头元素
• swap 交换内容

 小结：

1. 每次选取结束时间最早的会议，可以得到最优解。按这种方法选择，可以为未安排活动留下尽可能多的时间
2. 找出最大天数n，遍历1到n表示有n天时间开会
3. 让结束时间升序排序，则可以通过天数依次选出结束时间最早的会议并参加（删除队列里结束时间小于i的会议：因为它们已经结束了，无法再选择）

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int maxDay = 0;
        // 构建一个【开始天】 和 【结束天】的映射
        unordered_map<int, vector<int>> day2days;
        for (vector<int>& event : events)
        {
            if (maxDay < event[1])
            {
                maxDay = event[1];
            }
            day2days[event[0]].push_back(event[1]);
        }
 
        // 记录参见会议的次数
        int res = 0;
        // 小顶堆队列
        priority_queue<int, vector<int>, greater<int>> q;
        for (int i = 1; i <= maxDay; ++i)
        {
            // 增加新的结束时间
            if (day2days.find(i) != day2days.end())
            {
                for (int day : day2days[i])
                {
                    q.push(day);
                }
            }
 
            // 删除队列里结束时间小于i的会议：因为它们已经结束了，无法再选择
            while (!q.empty() && q.top() < i)
            {
                q.pop();
            }
 
            // 直接取最小结束时间会议，次数+1
            if (!q.empty())
            {
                q.pop();
                ++res;
            }
        }
        return res;
    }
};