贪心算法及相关题目

贪心算法概念

????????贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解?。

贪心算法性质（判断是否可以使用贪心算法）

1、贪心选择性质

????????一个问题的整体最优解可通过一系列局部的最优解的选择达到，并且每次的选择可以依赖以前作出的选择，但不依赖于后面要作出的选择。这就是贪心选择性质。对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。

2、最优子结构性质

????????当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质。问题的最优子结构性质是该问题可用贪心法求解的关键所在。

例题：

1. 双核计算机处理任务的最短时间（面试题）

题目描述：

某台计算机为双核，可以同时处理两个任务，现在给出一组数据，每个数据表示一个任务处理完需要的时间，求这台双核计算机处理完这些任务需要的最短时间

示例：

????????输入：[12, 20, 30]

????????输出：32

思路：

我们看到题后先自己分析一波，怎样选择处理才能得到最短时间？

先尝试一下不同的组合方式：

先选12和20分别在两个内核处理，再将30交给处理12的内核（先处理小的）：最少42秒

先选30和20分别在两个内核处理，再将12交给处理20的内核（先处理大的）：最少32秒

我们发现先较大的一起处理，再将下一个数据交给较小的内核处理，最后两内核中较大的为最优解

局部最优解：每次将 耗时最多的 交给 用时较小的内核 处理

代码：

#include <iostream>
#include <algorithm>
using namespace std;

int getmintime(int* ar, const int n)
{
    int time = 0; //记录耗时
    int core[2] = {0}; //两个内核，元素为各个内核耗时
    sort(ar, ar + n, greater<int>()); //排序从大到小
    for(int i = 0; i < n; i++)
    {
        int j = core[0] <= core[1] ? 0 : 1; //选择用时少的内核
        core[j] += ar[i]; //将最大耗时的交给用时少的内核处理
        time = max(time,core[j]);
    }
    return time;
    
}

int main()
{
    int ar[] = {12,20,30};
    cout << getmintime(ar,3) << endl;
    return 0;
}

2. 分发饼干（力扣455）

题目描述：

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。

对每个孩子?i，都有一个胃口值?g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干?j，都有一个尺寸?s[j]?。如果?s[j]?>= g[i]，我们可以将这个饼干?j?分配给孩子?i?，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

?

示例1：

????????输入：g = [1,2,3]，s = [1,1]

? ? ? ? 输出：1

示例2：

? ? ? ? 输入：g = [1,2]，s = [1,2,3]

? ? ? ? 输出：2

思路：排序+双指针

局部最优解：小胃口吃小饼干，大胃口吃大饼干

代码：

#include <algorithm>
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) 
    {
        int num = 0;
        sort(g.begin(), g.end(), less<int>());
        sort(s.begin(), s.end(), less<int>());
        vector<int>::iterator it1 = g.begin();
        vector<int>::iterator it2 = s.begin();
        while (it1 != g.end() && it2 != s.end())
        {
            if (*it1 <= *it2)
            {
                num++;
                it1++;
                it2++;
            }
            else
            {
                it2++;
            }
        }
        return num;
    }
};

3. 摆动序列（力扣376）

题目描述：

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为?摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

• 例如，?[1, 7, 4, 9, 2, 5]?是一个?摆动序列?，因为差值?(6, -3, 5, -7, 3)?是正负交替出现的。

• 相反，[1, 4, 7, 2, 5]?和?[1, 7, 4, 5, 5]?不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为 它的最后一个差值为零。

子序列?可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组?nums?，返回?nums?中作为?摆动序列?的?最长子序列的长度?。

示例1：

? ? ? ? 输入：nums = {1,7,4,9,2,5};

? ? ? ? 输出：6

示例2：

? ? ? ? 输入：nums = {1,17,5,10,13,15,10,5,16,8};

? ? ? ? 输出：7

思路：我们先对示例画图这样就很清晰了，我们去掉图中红圈元素，剩下元素就可以构成摆动序列，且长度最长

局部最优解：去掉所有单调路径两端之间所有其他元素

代码：

class Solution {
public:
    int wiggleMaxLength(vector<int>& nums) {
        vector<int>::iterator it = nums.begin();
        while (it != nums.end() - 1)
        {
            if (*it > *(it + 1))
            {
                vector<int>::iterator it2 = it + 1;
                while (it2 != nums.end() - 1 && *it2 >= *(it2 + 1))
                {
                    it2 = nums.erase(it2);
                }
                it = it2;
            }
            else if (*it < *(it + 1))
            {
                vector<int>::iterator it2 = it + 1;
                while (it2 != nums.end() - 1 && *it2 <= *(it2 + 1))
                {
                    it2 = nums.erase(it2);
                }
                it = it2;
            }
            else
            {
                it = nums.erase(it);
            }
        }
        return nums.size();
    }
};

4. 最大子数组和（力扣53）

题目描述：

给你一个整数数组?nums?，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组?是数组中的一个连续部分。

示例1：

? ? ? ? 输入：nums = {2,1,-3,4,-1,2,1,-5,4}

? ? ? ? 输出：6

示例2：

? ? ? ? 输入：nums = {5,4,-1,7,8}

? ? ? ? 输出：23

思路：

如果之前连续和小于0，则舍弃之前连续和，当前连续和为当前值；

如果之前连续和大于0，则当前连续和为当前值加之前连续和；

最后最大连续和为结果

局部最优解：之前连续和小于0则舍弃之前和，从当前位置重新开始算

代码：

1.贪心解法

class Solution {
public:
    int maxSubArray(vector<int>& nums) 
    {
	    if (nums.size() == 1)
	    {
		    return nums[0];
	    }

	    int nowtotal = nums[0]; //当前和
	    int pretotal = nums[0]; //之前和
	    int maxtotal = nums[0]; //最大和
	    for (int i = 1; i < nums.size(); i++)
	    {
			if (pretotal < 0)
			{
				nowtotal = nums[i]; //舍弃与之前和相加，保留当前值作为目前和
				pretotal = nums[i];
				maxtotal = maxtotal > nowtotal ? maxtotal : nowtotal;
			}
		    else
		    {
			    nowtotal = nums[i] + pretotal;
			    pretotal = nowtotal;
			    maxtotal = nowtotal > maxtotal ? nowtotal : maxtotal;
		    }
	    }
	    return maxtotal;
    }
};

2.动态规划解法

#include <algorithm>
class Solution {
public:
	int maxSubArray(vector<int>& nums) 
	{
		vector<int> dp = nums; //dp数组，每个元素为当前连续和
		for (int i = 1; i < nums.size(); i++)
		{
			dp[i] = dp[i - 1] > 0 ? dp[i - 1] + dp[i] : dp[i];
		}
		sort(dp.begin(), dp.end(), greater<int>());
		return dp[0];
	}
};

5. 买股票的最佳时机II（力扣122）

题目描述：

给你一个整数数组?prices?，其中?prices[i]?表示某支股票第?i?天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候?最多?只能持有?一股?股票。你也可以先购买，然后在?同一天?出售。

返回?你能获得的?最大?利润?。

示例1：

? ? ? ? 输入：price = {7,1,5,3,6,4}

? ? ? ? 输出：7

示例2：

? ? ? ? 输入：price = {1,2,3,4,5}

? ? ? ? 输出：4

思路：

我们对于示例进行画图：

由于题目描述：在任何时候?最多?只能持有?一股?股票，因此我们可以使用双指针遍历

局部最优解为：上升段的值

代码：

class Solution {
public:
	int maxProfit(vector<int>& prices) 
	{
		int output = 0;
		for (int i = 0, j = 1; j < prices.size(); i++, j++)
		{
			if (prices[i] < prices[j])
			{
				output += prices[j] - prices[i];
			}
		}
		return output;
	}
};

6. 跳跃游戏（力扣55）

题目描述：

给你一个非负整数数组?nums?，你最初位于数组的?第一个下标?。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回?true?；否则，返回?false?。

示例1：

? ? ? ? 输入：nums = {2,3,1,1,4}

? ? ? ? 输出：true

示例2：

? ? ? ? 输入：nums = {3,2,1,0,4}

? ? ? ? 输出：false? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

思路：

第一种解法：从起始向后走 最大可以移动步数(maxcanwalk)

maxcanwalk <= 下一位可走的步数 =》maxcanwalk =?下一位可走的步数，并向后走1位

maxcanwalk > 下一位可走的步数?=》maxcanwalk -= 1，并向后走1位

走到最后位置返回true；maxcanwalk==0&&没到最后位置返回false。

第二种解法：最大覆盖范围

从0下标开始，每次向后走1步，总共走nums[0]步，保存最大覆盖范围，如果最大覆盖范围小于最后一位则false

局部最优解：每次走都是范围最大的

代码：

第一种方法：

class Solution {
public:
	bool canJump(vector<int>& nums)
	{
		if (nums.size() == 1) //只有一个元素
		{
			return true;
		}
		int index = 0;
		int maxcanwalk = nums[index];
		for (index; index < nums.size() - 1; index++)
		{
			if (maxcanwalk == 0 && index != nums.size() - 1)
			{
				return false;
			}
			if (maxcanwalk <= nums[index + 1])
			{
				maxcanwalk = nums[index + 1];
			}
			else
			{
				maxcanwalk -= 1;
			}
		}
		return true;
	}
};

第二种方法：

class Solution {
public:
	bool canJump(vector<int>& nums) 
	{
		if (nums.size() == 1)
		{
			return true;
		}
		int coverage = nums[0];
		for (int i = 0; i <= coverage; i++)
		{
			coverage = max(coverage, i + nums[i]);
			if (coverage >= nums.size() - 1)
			{
				return true;
			}
		}
		return false;
	}
};

7. 跳跃游戏II（力扣45）

题目描述：

给定一个长度为?n?的?0 索引整数数组?nums。初始位置为?nums[0]。

每个元素?nums[i]?表示从索引?i?向前跳转的最大长度。换句话说，如果你在?nums[i]?处，你可以跳转到任意?nums[i + j]?处:

• 0 <= j <= nums[i]?
• i + j < n

返回到达?nums[n - 1]?的最小跳跃次数。生成的测试用例可以到达?nums[n - 1]。

示例1：

? ? ? ? 输入：nums = {2,3,1,1,4}

? ? ? ? 输出：2

示例2：

? ? ? ? 输入：nums = {2,3,0,1,4}

? ? ? ? 输出：2

思路：

看到这道题最开始能想到的就是 每次我都能跳最远 这样我就能最少次数到终点。

我们需要记录 起点，终点，最大覆盖范围 。从起点到终点一一遍历，保存最大覆盖范围（注意边界不能超过size-1），当我们走到终点时则记为跳跃了一步，将终点设置为最大覆盖范围，这样循环直到走到size-1结束（特殊情况为只有1个元素）

局部最优解：每次跳跃到我当前位置能达到的最远位置

代码：

class Solution {
public:
    int jump(vector<int>& nums)
    {
	    if (nums.size() == 1) //特殊情况，只有一个元素
	    {
		    return 0;
	    }
	    int start = 0; //起点
	    int end = nums[0] < nums.size() - 1 ? nums[0] : nums.size() - 1; //第一次的终点
	    int max_boundary = end; //每次的最大覆盖范围
	    int steps = 0; //跳跃次数
	    for (start; start <= end; start++)
	    {
            //这一位置的覆盖范围（不能超过size - 1）
		    int nowcanwalk = start + nums[start] < nums.size() - 1 ? start + nums[start] : nums.size() - 1;
		    max_boundary = max(max_boundary, nowcanwalk);
		    if (start == end) //走到当前的终点记为一次跳跃
		    {
			    end = max_boundary; //更新终点
			    steps++;
		    }
	    }
	    return steps;
    }
};

8. K次取反后最大化的数组和（力扣1005）

给你一个整数数组?nums?和一个整数?k?，按以下方法修改该数组：

• 选择某个下标?i?并将?nums[i]?替换为?-nums[i]?。

重复这个过程恰好?k?次。可以多次选择同一个下标?i?。

以这种方式修改数组后，返回数组?可能的最大和?。

示例1：

? ? ? ? 输入：nums = {4,2,3}, k = 1

? ? ? ? 输出：5

示例2：

? ? ? ? 输入：nums = {3,-1,0,2}, k = 3

? ? ? ? 输出：6

思路：

按照绝对值大小，从大到小排序，然后按次数将负数取反，最后累加即可得到最大和

局部最优解：每次让绝对值大的负数变成正数

代码：

class Solution {
public:
    int largestSumAfterKNegations(vector<int>& nums, int k) 
    {
	    sort(nums.begin(), nums.end(), [](int a, int b) {
		    return abs(a) > abs(b); 
	    });
	    for (int i = 0; i < nums.size(); i++)
	    {
		    if (nums[i] < 0 && k > 0)
		    {
			    nums[i] *= -1;
			    k--;
		    }
	    }
	    if (k % 2 == 1)
	    {
		    nums[nums.size() - 1] *= -1;
	    }
	    int total = 0;
	    for (int x : nums)
	    {
		    total += x;
	    }
	    return total;
    }
};

9. 加油站（力扣134）

题目描述：

在一条环路上有?n?个加油站，其中第?i?个加油站有汽油?gas[i]?升。

你有一辆油箱容量无限的的汽车，从第?i?个加油站开往第?i+1?个加油站需要消耗汽油?cost[i]?升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组?gas?和?cost?，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回?-1?。如果存在解，则?保证?它是?唯一?的。

示例1：

? ? ? ? 输入：gas = { 1,2,3,4,5 }; cost = { 3,4,5,1,2 }

? ? ? ? 输出：3

示例2：

? ? ? ? 输入：gas = { 2,3,4?}; cost = { 3,4,3 }

? ? ? ? 输出：-1

思路：

从0下标开始，当你剩余油量和为负数且为最小负数时，你的下一位才可能是能让你跑完的起点。

局部最优解：从0下标开始，剩余油量和<0时，记录下一个位置为起始位置

代码：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
		{
			int costsum = 0; //剩余油量累积和
			int totalsum = 0; //总共剩余油量
			int start = 0;
			for (int i = 0; i < gas.size(); i++)
			{
				costsum += gas[i] - cost[i];
				totalsum += gas[i] - cost[i];
				if (costsum < 0)
				{
					start = i + 1;
					costsum = 0;
				}
			}
			if (totalsum < 0) //总共剩余油量<0代表无论从哪跑都无法跑一圈
			{
				return -1;
			}
			return start;
  	}
};

10. 分发糖果（力扣135）

题目描述：

n?个孩子站成一排。给你一个整数数组?ratings?表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

• 每个孩子至少分配到?1?个糖果。
• 相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的?最少糖果数目

?

示例1：

? ? ? ? 输入：ratings = {1,0,2}

? ? ? ? 输出：5

示例2：

? ? ? ? 输入：ratings = {1,2,87,87,87,2,1}

? ? ? ? 输出：13

思路：

这道题乍一看，觉得只需要一次遍历过去，两两比较大的比小的多1即可，但是这样是不对的！

这道题的关键点在于一个数要同时兼顾两边，而要做到同时兼顾两边的数，那么就需要先确定一边，才能确定另一边。

这道题我们可以分为这两种情况来兼顾两边：

（开始所有人糖果都为1）

①从左向右走，找右边比左边数大的，将右边的糖果数增加

②从右向左走，找左边比右边数大的，将左边的糖果数增加（此时需要注意保留①得到的结果和②结果中的最大值）

代码：

class Solution {
public:
	int candy(vector<int>& ratings) 
	{
		int size = ratings.size();
		vector<int> v(size, 1);
		for (int i = 0; i < size - 1; i++) //从左向右走,判断右边比左边大的情况
		{
			if (ratings[i + 1] > ratings[i])
			{
				v[i + 1] = v[i] + 1;
			}
		}
		int total = 0;
		for (int i = size - 1; i > 0; i--) //从右向左走，判断左边比右边大的情况
		{
			if (ratings[i - 1] > ratings[i])
			{
				v[i - 1] = max(v[i - 1], v[i] + 1); //保留 从左向右 和 从右向左 结果中的最大值
			}
			total += v[i];
		}
		total += v[0];
		return total;
	}
};

11. 柠檬水找零（力扣860）

在柠檬水摊上，每一杯柠檬水的售价为?5?美元。顾客排队购买你的产品，（按账单?bills?支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付?5?美元、10?美元或?20?美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付?5?美元。

注意，一开始你手头没有任何零钱。

给你一个整数数组?bills?，其中?bills[i]?是第?i?位顾客付的账。如果你能给每位顾客正确找零，返回?true?，否则返回?false?。

????????

示例1：

? ? ? ? 输入：bills = {5,5,5,10,20}

? ? ? ? 输出：true

示例2：

? ? ? ? 输入：bills = {5,5,10,10,20}

? ? ? ? 输出：false

思路：

这道题很简单，只需要根据2种情况判断手头是否有足够数量的此种支票即可。

给10要找5：判断手头是否右1张5

给20要找15：判断手头是否右1张10和1张5，没有再判断是否有3张5（1张10，1张5优先，5用的情况比较多）

代码：

class Solution {
public:
	bool lemonadeChange(vector<int>& bills) 
	{
		int five = 0;
		int ten = 0;
		for (int x : bills)
		{
			if (x == 5)
			{
				five++;
			}
			else if (x == 10)
			{
				ten++;
				if (five < 1)
				{
					return false;
				}
				five--;
			}
			else if (x == 20)
			{
				if (ten > 0 && five > 0)
				{
					ten--;
					five--;
				}
				else if (five >= 3)
				{
					five -= 3;
				}
				else
				{
					return false;
				}
			}
		}
		return true;
	}
};

12. 根据身高重建队列（力扣406）

题目描述：

假设有打乱顺序的一群人站成一个队列，数组?people?表示队列中一些人的属性（不一定按顺序）。每个?people[i] = [hi, ki]?表示第?i?个人的身高为?hi?，前面?正好?有?ki?个身高大于或等于?hi?的人。

请你重新构造并返回输入数组?people?所表示的队列。返回的队列应该格式化为数组?queue?，其中?queue[j] = [hj, kj]?是队列中第?j?个人的属性（queue[0]?是排在队列前面的人）。

示例1：

? ? ? ? 输入：people = { {7,0}, {4,4}, {7,1}, {5,0}, {6,1}, {5,2} }

? ? ? ? 输出：{ {5,0}, {7,0}, {5,2}, {6,1}, {4,4}, {7,1} }

思路：

与第10题分发糖果一样，遇到这种有两种维度影响的题，需要先确定一方，才能确定另一方

我们来先确定h身高这个维度，我们按照身高从大到小顺序先排列一下（其中身高一样的，根据k从小到大排），排完后按照k来进行插入，画图表示：

代码：

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

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) 
    {
	    sort(people.begin(), people.end(), cmp);
	    vector<vector<int>> queue;
	    for (int i = 0; i < people.size(); i++)
	    {
		    int index = people[i][1];
		    queue.insert(queue.begin() + index, people[i]);
	    }
	    return queue;
    }
};

13. 用最少数的箭引爆气球（力扣452）

题目描述：

有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组?points?，其中points[i] = [xstart, xend]?表示水平直径在?xstart?和?xend之间的气球。你不知道气球的确切 y 坐标。

一支弓箭可以沿着 x 轴从不同点?完全垂直?地射出。在坐标?x?处射出一支箭，若有一个气球的直径的开始和结束坐标为?xstart，xend，?且满足 ?xstart?≤ x ≤ xend，则该气球会被?引爆?。可以射出的弓箭的数量?没有限制?。 弓箭一旦被射出之后，可以无限地前进。

给你一个数组?points?，返回引爆所有气球所必须射出的?最小?弓箭数?。

示例1：

? ? ? ? 输入：points = { {10,16}, {2,8}, {1,6}, {7,12} }

? ? ? ? 输出：2

思路：排序 + 贪心

看到这道题时可以发现，也是有两个维度影响是否重叠的判断（左边界和右边界），因此我们需要确定一边再去看另一边。我们先根据左边界从小到大排序，然后根据右边界进行判断：

局部最优解：每次让重复区域尽可能包括多个气球

代码：

class Solution {
public:
    static bool cmp(vector<int>& a, 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 right = points[0][1];
	    int shutnum = 1;
	    for (int i = 1; i < points.size(); i++)
	    {
		    if (right < points[i][0])
		    {
			    shutnum++;
				right = points[i][1];
		    }
		    else
		    {
			    right = min(right, points[i][1]);
		    }
	    }
	    return shutnum;
    }
};

14. 无重叠区间（力扣435）

题目描述：

给定一个区间的集合?intervals?，其中?intervals[i] = [starti, endi]?。返回?需要移除区间的最小数量，使剩余区间互不重叠?。

示例1：

? ? ? ? 输入：intervals = { {1,2}, {2,3}, {3,4}, {1,3}?}

? ? ? ? 输出：1

思路：排序 + 贪心

这道题和上一道题其实思路差不多，有两个维度影响判断是否重叠，因此需要先确定一个方向再确定另一个。我们根据左边界从小到大排序，判断当前左边界和上一个的右边界大小关系：

①当前左边界 < 上一个右边界：说明有重叠，我们左边界已经按照从小到大排序，因此只需要剔除掉右边界更大的（左边界以确定，右边界越大可能覆盖的越多）

②否则：说明没有重叠，只需要更新右边界即可

局部最优解：有重叠时剔除覆盖范围大的那个。

代码：

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) 
    {
	    if (intervals.size() <= 1)
	    {
		    return 0;
	    }
	    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {return a[0] < b[0]; });
	    int delnum = 0;
	    int right = intervals[0][1];
	    for (int i = 1; i < intervals.size(); i++)
	    {
		    if (right > intervals[i][0])
		    {
			    delnum++;
			    right = min(right, intervals[i][1]);
		    }
		    else
		    {
			    right = intervals[i][1];
		    }
	    }
	    return delnum;
    }
};

15. 划分字母区间（力扣763）

题目描述：

给你一个字符串?s?。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是?s?。

返回一个表示每个字符串片段的长度的列表。

示例1：

? ? ? ? 输入：s = {"ababcbacadefegdehighklij"}

? ? ? ? 输出：{9, 7, 8}

示例2：

? ? ? ? 输入：s = {"eaaaabaaccd"}

? ? ? ? 输出：{1, 7, 2, 1}

思路：

我们看到这道题的正常思路是 从头开始走 判断当前字母的最远位置之前是否包括其他字母的最远位置，如果是则这个区间为一个单独的区间。那么我们该如何判断当前是否包括其他字母的最远位置呢？我来画个图帮大家理解一下：

局部最优解：从头开始走，走到 当前走过区域中元素最远距离的最大值 时，即为一个区间

代码：

class Solution {
public:
	vector<int> partitionLabels(string s) 
	{
		int hash[27] = { -1 };
		for (int i = 0; i < s.size(); i++)
		{
			hash[s[i] - 'a'] = i;  //a->0  b->1 ...
		}
		vector<int> outcome;
		int left = 0;
		int farthest_point = 0; //保存当前走过区域中元素最远距离的最大值
		for (int right = 0; right < s.size(); right++)
		{
			farthest_point = max(farthest_point, hash[s[right] - 'a']);
			if (right == farthest_point)
			{
				outcome.push_back(right - left + 1);
				left = right + 1;
			}
		}
		return outcome;
	}
};

16. 合并区间（力扣56）

题目描述：

以数组?intervals?表示若干个区间的集合，其中单个区间为?intervals[i] = [starti, endi]?。请你合并所有重叠的区间，并返回?一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间?。

?示例1：

? ? ? ? 输入：intervals = {{1,3}, {2,6}, {8,10}, {15,18}}

? ? ? ? 输出：{{1,6}, {8,10}, {15,18}}

示例2：

? ? ? ? 输入：intervals = {{1,4}, {4,5}}

? ? ? ? 输出：{{1,5}}

思路：

这道题和之前做过的区间有关的题差不多，按照我这个顺序做过的同学应该能很清楚的想到，这道题只是比之前的多一个合并的操作

代码：

class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) 
    {
        if(intervals.size() < 2)
        {
            return intervals;
        }
        sort(intervals.begin(), intervals.end(), [](const auto &a, const auto &b){return a[0] < b[0];});
        vector<vector<int>> vv;
        vv.push_back(intervals[0]);
        for(int i = 1; i < intervals.size(); i++)
        {
            if(vv.back()[1] >= intervals[i][0])
            {
                vv.back()[1] = max(vv.back()[1], intervals[i][1]);
            }
            else
            {
                vv.push_back(intervals[i]);
            }
        }
        return vv;
    }
};

17. 单调自增的数字（力扣738）

题目描述：

当且仅当每个相邻位数上的数字?x?和?y?满足?x <= y?时，我们称这个整数是单调递增的。

给定一个整数?n?，返回?小于或等于?n?的最大数字，且数字呈?单调递增?。

示例1：

? ? ? ? 输入：n = 10

? ? ? ? 输出：9

示例2：

? ? ? ? 输入：n = 332

? ? ? ? 输出：299

思路：

题目要求数字中每一位都是按照递增，且最后这个数需要是最大的，因此我们可以想到找到第一个导致不递增的数的位置，将此位的前一位的数减1，此位以及之后位全部变为9就是最大且递增的。

局部最优解：前一位 > 这一位时：前一位-1，后面全部置为9

代码：

class Solution {
public:
    int monotoneIncreasingDigits(int n) 
    {
	    string str = to_string(n);
	    int flg = str.size();
	    for (int i = str.size() - 1; i > 0; i--)
	    {
		    if (str[i - 1] > str[i])
		    {
			    str[i - 1]--;
			    flg = i;
		    }
	    }
	    for (int i = flg; i < str.size(); i++)
	    {
		    str[i] = '9';
	    }
	    return stoi(str);
    }
};

18.监控二叉树（力扣968）

题目描述：

给定一个二叉树，我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

思路：

我们看到这道题时为了让监控的个数最少，因此每个监控最好能够监视3个节点，因此我们能够想到让叶子节点的父节点为监控，并且隔一个为一个监控，此时可以确定需要从下往上遍历二叉树，也就需要后序遍历，这就是这道题的大体思路，如何判断这个节点是否需要放监控呢？我们就需要根据它两个孩子的状态来决定是否需要放监控。

我们画图说明：

局部最优解：叶子节点的父节点一定为摄像头，并从叶子的父节点向上每隔一个节点为一个摄像头

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */

class Solution {
public:
    int outcome = 0;
    //状态 0:无覆盖  1:有覆盖  2:有摄像头
    int getstate(TreeNode* root)
    {
        if (root == nullptr) //空节点
        {
            return 1;
        }

        //左
        int left = getstate(root->left);

        //右
        int right = getstate(root->right);

        //根
        if (left == 0 || right == 0) //左右孩子有一个无覆盖
        {
            outcome++;
            return 2; //父节点需要有摄像头
        }
        if (left == 1 && right == 1) //左右孩子都被覆盖
        {
            return 0; //父节点一定没有被覆盖
        }
        if (left == 2 || right == 2) //左右孩子有一个摄像头
        {
            return 1; //父节点一定被覆盖
        }
        return -1; //运行不到此处，只是为了编译通过
    }

    int minCameraCover(TreeNode* root)
    {
        if (getstate(root) == 0) //由于遍历到根节点就退出了，如果此时根节点没有被覆盖，我们需要在根节点安装摄像头
        {
            outcome++;
        }
        return outcome;
    }
};