C++【算法】【贪心算法】
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。
目录
贪心选择是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素。
一、分隔平衡字符串
在一个 平衡字符串 中，'L' 和 'R' 字符的数量是相同的。
给你一个平衡字符串 s，请你将它分割成尽可能多的平衡字符串。
注意：分割得到的每个字符串都必须是平衡字符串，且分割得到的平衡字符串是原平衡字符串的连续子串。
返回可以通过分割得到的平衡字符串的 最大数量 。
示例 1：
输入：s = "RLRRLLRLRL"
输出：4
解释：s 可以分割为 "RL"、"RRLL"、"RL"、"RL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
示例 2：输入：s = "RLLLLRRRLR"
输出：3
解释：s 可以分割为 "RL"、"LLLRRR"、"LR" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
示例 3：输入：s = "LLLLRRRR"
输出：1
解释：s 只能保持原样 "LLLLRRRR".
示例 4：输入：s = "RLRRRLLRLL"
输出：2
解释：s 可以分割为 "RL"、"RRRLLRLL" ，每个子字符串中都包含相同数量的 'L' 和 'R' 。
提示：
1 <= s.length <= 1000
s[i] = 'L' 或 'R'
s 是一个 平衡 字符串
通过次数90,999提交次数107,480来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/split-a-string-in-balanced-strings
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
贪心策略：不让平衡字符串嵌套
class Solution {
public:
public:
int balancedStringSplit(string s) {
int cnt = 0;
int balance = 0;
for(int i = 0; i < s.size(); i++){
if(s[i] == 'L')
balance--;
if(s[i] == 'R')
balance++;
if(balance == 0)
cnt++;
} return cnt;
}
};二、买卖股票的最佳实际
给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。
返回 你能获得的 最大 利润 。
示例 1：
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
总利润为 4 + 3 = 7 。
示例 2：输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
总利润为 4 。
示例 3：输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。
提示：
1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
贪心：
连续上涨：上涨的最低点买入，上涨的最高点卖出（每天买卖的绝对利润相同）
连续下跌：不进行买卖
class Solution {
public:
int maxProfit(vector<int>& prices) {
int profit=0;
for(int i=1;i<prices.size();++i)
{
//判断趋势
if(prices[i]>prices[i-1])
{
profit+=prices[i]-prices[i-1];
}
}
return profit;
}
};三、跳跃游戏
给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。
示例 1：
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。
示例 2：输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。
提示：
1 <= nums.length <= 3 * 104
0 <= nums[i] <= 105来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/jump-game
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
贪心：站在每一个位置，更新最远可以到达的位置。
class Solution {
public:
bool canJump(vector<int>& nums) {
int max1=0;
int pos=nums.size()-1;
for(int i=0;i<=pos;++i)
{
//判断是否可以到达当前位置
if(max1>=i)
{
max1=max(max1,i+nums[i]);
//判断最远的位置是否包含最后一个位置
if(max1>=pos)
{
return true;
}
}
else
{
return false;
}
}
return true;
}
};四、钱币找零
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？
贪心：每次用符合条件的所有纸币中，面值最大的纸币
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
struct cmp
{
bool operator()(vector<int>&array1,vector<int>&array2)
{
return array1[0]>array2[0];
}
};
int maxNum(vector<vector<int>> & moneyMat,int money)
{
//0：面值，1：个数
//按照面值进行排序：递减
sort(moneyMat.begin(),moneyMat.end(),cmp());
int cnt=0;
for(auto arr:moneyMat)
{
//计算需要当前面值的纸币个数
int c=money/arr[0];
c=min(c,arr[1]);
//减去找过去的钱
money-=c*arr[0];
cnt+=c;
}
//纸币是不够的
if(money!=0)
{
return -1;
}
return cnt;
}
int main()
{
//一块钱的有3张，两块钱的有1张，以此类推
vector<vector<int>> moneyMat={ { 1, 3 }, { 2, 1 }, { 5, 4 }, { 10, 3 }, { 20, 0},{50, 1}, { 100, 10 } };
int money;
cout << "请输入要支付的钱" << endl;
cin >> money;
cout<<maxNum(moneyMat,money)<<endl;
return 0;
}五、多机调度问题
某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中
断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间
输入
第一行T（1<T<100)表示有T组测试数据。每组测试数据的第一行分别是整数n，m（1<=n<=10000，
1<=m<=100），接下来的一行是n个整数ti（1<=t<=100)。
输出
所需的最短时间
贪心：每次选取剩余作业中执行时间最长的，分配给最先结束作业的机器
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
bool cmp(const int &x, const int &y)
{
return x > y;
}
int findMax(const vector<int>& machines)
{
int ret = machines[0];
for (const auto& cur : machines)
{
if (ret < cur)
ret = cur;
}
return ret;
}
int greedStrategy(vector<int>& works, vector<int>& machines) {
// 按作业时间从大到小排序
sort(works.begin(), works.end(), cmp);
int workNum = works.size();
int machineNum = machines.size();
// 作业数如果小于机器数，直接返回最大的作业时间
if (workNum <= machineNum) {
int minimalTime = works[0];
return minimalTime;
} else {
// 为每一个作业选择机器
for (int i = 0; i < workNum; i++) {
// 选择最小的机器
int flag = 0;
//首先假设用第一个机器处理
int tmp = machines[flag];
// 从剩余机器中选择作业时间最小的
for (int j = 1; j < machines.size(); j++) {
if (tmp > machines[j]) {
flag = j;
tmp = machines[j];
}
} // 将当前作业交给最小的机器执行
machines[flag] += works[i];
} // 从所有机器中选出最后执行完作业的机器
int minimalTime = findMax(machines);
return minimalTime;
}
}
int main()
{
int n, m;
cout << "请输入作业数和机器数" << endl;
cin >> n >> m;
vector<int> works(n);
vector<int> machines(m,0);
cout << "请输入执行每一个任务的时间" << endl;
for (int i = 0; i < n; ++i)
cin >> works[i];
cout << greedStrategy(works, machines) << endl;
return 0;
} 
六、活动选择
有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。每个活动a[i]都有一个
开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重
叠，a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。
贪心：每次选取结束时间最早的活动，可以得到最优解。
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;
bool cmp(const pair<int,int>& a, const pair<int,int>& b)
{
return a.second < b.second;
}
int greedyActivitySelector(const vector<pair<int,int>>& act)
{
//贪婪策略：每次选择最早结束的活动
//num是统计举办的活动个数
int num = 1, i = 0;
for (int j = 1; j < act.size(); j++)
{
//后一个活动的开始时间小于前一个活动的结束时间
if (act[j].first >= act[i].second)
{
i = j;
num++;
}
}
return num;
}
int main()
{
int number;
cin >> number;
vector<pair<int, int>> act(number);
int idx = 0;
for (int i = 0; i < act.size(); ++i)
{
cin >> act[i].first >> act[i].second;
} //按照活动截止时间从小到大排序
sort(act.begin(), act.end(), cmp);
int ret = greedyActivitySelector(act);
cout << ret << endl;
}七、无重叠区间
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/non-overlapping-intervals
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
首先将所有的区间按照起始位置进行递增排序
1.如果是[1,2],[2,3]不冲突，就保留。
2.如果[1,2],[1,3]也就是后面一个区间包裹住了前面一个区间，我们就将后面这个区间删除
3.如果是 [1,3][2,4]，就将后面一个区间删除，为后面的区间留出更大的区间
bool cmp(const vector<int>& a, const vector<int>& b)
{
//按起点递增排序
return a[0] < b[0];
}
class Solution {
public:
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
if (intervals.size() == 0) {
return 0;
} //按起点递增排序
sort(intervals.begin(), intervals.end(), cmp);
int end = intervals[0][0], prev = 0, count = 0;
for (int i = 1; i < intervals.size(); i++) {
//前一个事件的结束时间比后一个事件的开始时间晚
if (intervals[prev][1] > intervals[i][0]) {
//前一个时间的结束时间比后一个事件的结束时间晚
if (intervals[prev][1] > intervals[i][1]) {
//情况2
prev = i;
} //情况3
count++;
} else {
//情况1
//前一个事件的结束时间比后一个时间的起始时间早
prev = i;
}
} return count;
}
};
开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！
更多推荐
11
0- 0
已为社区贡献4条内容
所有评论(0)