一、分隔平衡字符串

力扣

在一个平衡字符串中，'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;
    }
};