力扣整理版九：贪默算法

局部最优  全局最优  局部最优可以推出全局最优  而且想不出反例
-----------------------------
(1) 455 分发饼干
(2) 1005 k次取反后最大化的数组和
(3) 860 柠檬水找零
(4) 376 摆动序列
(5) 738 单调递增的数字
(6) 122 交易股票的最佳机遇2
(7) 135 分发糖果
(8) 406 根据身高重修队列
(9) 55 跳跃游戏
(10) 45 跳跃游戏2
(11) 452 用最少的箭引爆气球
(12) 435 无重叠区间
(13) 763 分别字母区间
(14) 56 归并区间
(15) 53 最大子序和
(16) 134 加油站
(17) 968 监控二叉树
-----------------------------
一、简单标题

1、455 分发饼干

455. 分发饼干 - 力扣（LeetCode）
标题形貌：假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 i，都有一个胃口值  g，这是能让孩子们满足胃口的饼干的最小尺寸；而且每块饼干 j，都有一个尺寸 s[j] 。假如 s[j] >= g，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽大概满足越多数目标孩子，并输出这个最大数值。
表面的 for 是里的下标 i 是固定移动的，而 if 内里的下标 index 是符合条件才移动的。
--------------- python ---------------

1. class Solution:
2.     def findContentChildren(self, g, s):
3.         g.sort()  # 将孩子的贪心因子排序
4.         s.sort()  # 将饼干的尺寸排序
5.         index = len(s) - 1  # 饼干数组的下标，从最后一个饼干开始
6.         result = 0  # 满足孩子的数量
7.         for i in range(len(g)-1, -1, -1):  # 遍历胃口，从最后一个孩子开始
8.             if index >= 0 and s[index] >= g[i]:  # 遍历饼干
9.                 result += 1
10.                 index -= 1
11.         return result

复制代码

--------------- c++ ---------------

1. class Solution {
2. public:
3.     int findContentChildren(vector<int>& g, vector<int>& s) {
4.         sort(g.begin(),g.end());
5.         sort(s.begin(),s.end());
6.         int index=s.size()-1;
7.         int c=0;
8.         for(int i=g.size()-1;i>=0;i--){
9.             if(index>=0 && s[index]>=g[i]){
10.                 index--;
11.                 c++;
12.             }
13.         }
14.         return c;
15.     }
16. };

复制代码

 2、1005 k次取反后最大化的数组和 

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）
标题形貌：给定一个整数数组 A，我们只能用以下方法修改该数组：我们选择某个索引 i 并将 A 更换为 -A，然后统共重复这个过程 K 次。（我们可以多次选择同一个索引 i。）以这种方式修改数组后，返回数组大概的最大和。
--------------- python ---------------

1. class Solution:
2.     def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
3.         A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A
5.         for i in range(len(A)):  # 第二步：执行K次取反操作
6.             if A[i] < 0 and K > 0:
7.                 A[i] *= -1
8.                 K -= 1
10.         if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反
11.             A[-1] *= -1
13.         result = sum(A)  # 第四步：计算数组A的元素和
14.         return result

复制代码

 以下代码会报错：须要优先翻转绝对值较大的元素

1. class Solution:
2.     def largestSumAfterKNegations(self, nums: List[int], k: int) -> int:
3.         nums.sort(key=abs)
4.         for i in range(len(nums)):
5.             if nums[i]<0 and k>0:
6.                 nums[i]=-nums[i]
7.                 k-=1
8.         if k%2!=0:
9.             nums[0]=-nums[0]
10.         return sum(nums)

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     static bool cmp(int a,int b){
4.         return abs(a)>abs(b);
5.     }
6.     int largestSumAfterKNegations(vector<int>& nums, int k) {
7.         sort(nums.begin(),nums.end(),cmp); //如果不是静态成员函数就需要通过对象调用，静态函数可以通过类名调用
8.         for(int i=0;i<nums.size()&&k>0;i++){
9.             if(nums[i]<0) {
10.                 nums[i]*=-1;
11.                 k--;
12.             }
13.         }
14.         if(k%2==1) nums[nums.size()-1]*=-1;
15.         int sum=0;
16.         for(int i:nums) sum+=i;
17.         return sum;
18.     }
19. };

复制代码

3、860 柠檬水找零 

860. 柠檬水找零 - 力扣（LeetCode）
标题形貌：在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客列队购买你的产物，（按账单 bills 付出的序次）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客精确找零，也就是说净交易业务是每位顾客向你付出 5 美元。留意，一开始你手头没有任何零钱。假如你能给每位顾客精确找零，返回 true ，否则返回 false 。
--------------- python ---------------

1. class Solution:
2.     def lemonadeChange(self, bills: List[int]) -> bool:
3.         five = 0
4.         ten = 0
5.         twenty = 0
6.         
7.         for bill in bills:
8.             # 情况一：收到5美元
9.             if bill == 5:
10.                 five += 1
11.             
12.             # 情况二：收到10美元
13.             if bill == 10:
14.                 if five <= 0:
15.                     return False
16.                 ten += 1
17.                 five -= 1
18.             
19.             # 情况三：收到20美元
20.             if bill == 20:
21.                 # 先尝试使用10美元和5美元找零
22.                 if five > 0 and ten > 0:
23.                     five -= 1
24.                     ten -= 1
25.                     #twenty += 1
26.                 # 如果无法使用10美元找零，则尝试使用三张5美元找零
27.                 elif five >= 3:
28.                     five -= 3
29.                     #twenty += 1
30.                 else:
31.                     return False
32.         
33.         return True

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     bool lemonadeChange(vector<int>& bills) {
4.         int five=0;
5.         int ten=0;
6.         int twenty=0;
7.         for(int i:bills){
8.             if(i==5) five+=1;
9.             if(i==10) {
10.                 if(five==0) return false;
11.                 else{
12.                     five-=1;
13.                     ten+=1;
14.                 }
15.             }
16.             if(i==20){
17.                 if(ten>0&&five>0){
18.                     ten-=1;
19.                     five-=1;
20.                 }
21.                 else if(five>2) five-=3;
22.                 else return false;
23.             }
24.         }
25.         return true;
26.     }
27. };

复制代码

 二、中等标题-序列标题

1、376 摆动序列

376. 摆动序列 - 力扣（LeetCode）
标题形貌：给定一个整数序列，返回作为摆动序列的最宗子序列的长度。 通过从原始序列中删除一些（也可以不删除）元向来得到子序列，剩下的元素保持其原始序次。
这个坡度 摆动变革的时间，更新 prediff。
--------------- python ---------------

1. class Solution:
2.     def wiggleMaxLength(self, nums):
3.         if len(nums) <= 1:
4.             return len(nums)  # 如果数组长度为0或1，则返回数组长度
5.         curDiff = 0  # 当前一对元素的差值
6.         preDiff = 0  # 前一对元素的差值
7.         result = 1  # 记录峰值的个数，初始为1（默认最右边的元素被视为峰值）
8.         for i in range(len(nums) - 1):
9.             curDiff = nums[i + 1] - nums[i]  # 计算下一个元素与当前元素的差值
10.             # 如果遇到一个峰值
11.             if (preDiff <= 0 and curDiff > 0) or (preDiff >= 0 and curDiff < 0):
12.                 result += 1  # 峰值个数加1
13.                 preDiff = curDiff  # 注意这里，只在摆动变化的时候更新preDiff
14.         return result  # 返回最长摆动子序列的长度

复制代码

--------------- c++ ---------------  

1. class Solution {
2. public:
3.     int wiggleMaxLength(vector<int>& nums) {
4.         if(nums.size()<=1) return nums.size();
5.         int pre=0;
6.         int cur=0;
7.         int c=1;
8.         for(int i=0;i<nums.size()-1;i++){
9.             cur=nums[i+1]-nums[i];
10.             if((pre<=0&&cur>0) || (pre>=0&&cur<0)){
11.                 c+=1;
12.                 pre=cur;
13.             }
14.         }
15.         return c;
16.     }
17. };

复制代码

2、738 单调递增的数字

738. 单调递增的数字 - 力扣（LeetCode）
标题形貌：给定一个非负整数 N，找出小于或即是 N 的最大的整数，同时这个整数须要满足其各个位数上的数字是单调递增。（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）
Tips：两位数的环境--十位数减一，个位数变为9。须要从后向前，332，前向后是329，但是又不满足递增了。从后向前，有递减，背面全部为9，前一位减1（包管比原数小）。
--------------- python ---------------

1. class Solution:
2.     def monotoneIncreasingDigits(self, N: int) -> int:
3.         strNum = str(N)        
4.         for i in range(len(strNum) - 1, 0, -1):
5.             # 如果当前字符比前一个字符小，说明需要修改前一个字符
6.             if strNum[i - 1] > strNum[i]:
7.                 # 将前一个字符减1，以保证递增性质
8.                 # 使用字符串切片操作将修改后的前面部分与后面部分进行拼接
9.                 strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + '9' * (len(strNum) - i)      
10.         return int(strNum)

复制代码

附一种错误的，写的时间理所固然感觉只要有递减就最高位-1，背面全部为9，这种环境120输出99，但是现实上是119。须要两位数两位数比力。 

1. class Solution:
2.     def monotoneIncreasingDigits(self, n: int) -> int:
3.         strnum=str(n)
4.         for i in range(len(strnum)-1):
5.             if strnum[i]>strnum[i+1]:
6.                return int(str(int(strnum[0])-1)+'9'*(len(strnum)-1))
7.         return n

复制代码

--------------- c++ ---------------   

1. class Solution {
2. public:
3.     int monotoneIncreasingDigits(int n) {
4.         string strnum=to_string(n);
5.         int flag=strnum.size();
6.         for(int i=strnum.size()-1;i>0;i--){
7.             if(strnum[i-1]>strnum[i]){
8.                 strnum[i-1]--;
9.                 flag=i;
10.             }
11.         }
12.         for(int i=flag;i<strnum.size();i++){
13.             strnum[i]='9';
14.         }
15.         return stoi(strnum);
16.     }
17. };

复制代码

 三、中等标题-贪婪办理股票

1、122 交易股票的最佳机遇2

122. 交易股票的最佳机遇 II - 力扣（LeetCode）
标题形貌：给定一个数组，它的第  i 个元素是一支给定股票第 i 天的代价。计划一个算法来盘算你所能获取的最大利润。你可以尽大概地完成更多的交易业务（多次交易一支股票）。留意：你不能同时参加多笔交易业务（你必须在再次购买前出售掉之前的股票）。
Tips：只网络天天的正利润。

--------------- python ---------------

1. class Solution:
2.     def maxProfit(self, prices: List[int]) -> int:
3.         result = 0
4.         for i in range(1, len(prices)):
5.             result += max(prices[i] - prices[i - 1], 0)
6.         return result

复制代码

--------------- c++ ---------------    

1. class Solution {
2. public:
3.     int maxProfit(vector<int>& prices) {
4.         int sum=0;
5.         for(int i=1;i<prices.size();i++){
6.             sum+=max(prices[i]-prices[i-1],0);
7.         }
8.         return sum;
9.     }
10. };

复制代码

 四、中等标题-两个维度权衡

1、135 分发糖果

135. 分发糖果 - 力扣（LeetCode）
标题形貌：老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。你须要按照以下要求，资助老师给这些孩子分发糖果：

• 每个孩子至少分配到 1 个糖果。
  
• 相邻的孩子中，评分高的孩子必须得到更多的糖果。
  

那么如许下来，老师至少须要准备多少颗糖果呢？
Tips：思量两边的环境肯定要分开遍历。
--------------- python ---------------

1. class Solution:
2.     def candy(self, ratings: List[int]) -> int:
3.         candyVec = [1] * len(ratings)
4.         
5.         # 从前向后遍历，处理右侧比左侧评分高的情况
6.         for i in range(1, len(ratings)):
7.             if ratings[i] > ratings[i - 1]:
8.                 candyVec[i] = candyVec[i - 1] + 1
9.         
10.         # 从后向前遍历，处理左侧比右侧评分高的情况
11.         for i in range(len(ratings) - 2, -1, -1):
12.             if ratings[i] > ratings[i + 1]:
13.                 candyVec[i] = max(candyVec[i], candyVec[i + 1] + 1)
14.         
15.         # 统计结果
16.         result = sum(candyVec)
17.         return result

复制代码

--------------- c++ ---------------     

1. class Solution {
2. public:
3.     int candy(vector<int>& ratings) {
4.         vector<int> v(ratings.size(),1);
5.         for(int i=1;i<ratings.size();i++){
6.             if(ratings[i]>ratings[i-1]) v[i]=v[i-1]+1;
7.         }
8.         for(int i=ratings.size()-2;i>=0;i--){
9.             if(ratings[i]>ratings[i+1]) v[i]=max(v[i],v[i+1]+1);
10.         }
11.         int sum=0;
12.         for(int i=0;i<v.size();i++) sum+=v[i];
13.         return sum;
14.     }
15. };

复制代码

 2、406 根据身高重修队列 

406. 根据身高重修队列 - 力扣（LeetCode）
标题形貌：假设有打乱序次的一群人站成一个队列，数组 people 表现队列中一些人的属性（不愿定按序次）。每个 people = [hi, ki] 表现第 i 个人的身高为 hi ，前面 恰恰 有 ki 个身高大于或即是 hi 的人。请你重新构造并返回输入数组 people 所表现的队列。返回的队列应该格式化为数组 queue ，此中 queue[j] = [hj, kj] 是队列中第 j 个人的属性（queue[0] 是排在队列前面的人）。
--------------- python --------------- 

1. class Solution:
2.     def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
3.             # 先按照h维度的身高顺序从高到低排序。确定第一个维度
4.         # lambda返回的是一个元组：当-x[0](维度h）相同时，再根据x[1]（维度k）从小到大排序
5.         people.sort(key=lambda x: (-x[0], x[1]))
6.         que = []
7.        
8.         # 根据每个元素的第二个维度k，贪心算法，进行插入
9.         # people已经排序过了：同一高度时k值小的排前面。
10.         for p in people:
11.             que.insert(p[1], p)
12.         return que

复制代码

--------------- c++ ---------------     

1. class Solution {
2. public:
3.     static bool cmp(const vector<int>&a,const vector<int>&b){
4.         if(a[0]==b[0]) return a[1]<b[1];
5.         return a[0]>b[0];
6.     }
7.     vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
8.         vector<vector<int>> res;
9.         sort(people.begin(),people.end(),cmp);
10.         for(int i=0;i<people.size();i++){
11.             int p=people[i][1];
12.             res.insert(res.begin()+p,people[i]);
13.         }
14.         return res;
15.     }
16. };

复制代码

五、有点难度-区间标题

1、55 跳跃游戏

55. 跳跃游戏 - 力扣（LeetCode）
标题形貌：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。判定你是否可以大概到达末了一个位置。
Tips：关注的是跳跃覆盖范围。
--------------- python ---------------

1. class Solution:
2.     def canJump(self, nums: List[int]) -> bool:
3.         if len(nums)<2:return True
4.         cover=0
5.         for i in range(len(nums)):
6.             if(i<=cover):
7.                 cover=max(cover,i+nums[i])
8.                 if(cover>=len(nums)): return True
9.             else: return False
10.         return True

复制代码

--------------- c++ ---------------  

1. class Solution {
2. public:
3.     bool canJump(vector<int>& nums) {
4.         if(nums.size()<2) return true;
5.         int cover=0;
6.         for(int i=0;i<nums.size();i++){
7.             if(i<=cover) {
8.                 cover=max(cover,i+nums[i]);
9.                 if(cover>=nums.size()-1) return true;
10.             }
11.             else return false;
12.         }
13.         return false;
14.     }
15. };

复制代码

2、45 跳跃游戏2 

45. 跳跃游戏 II - 力扣（LeetCode）
标题形貌：给定一个非负整数数组，你最初位于数组的第一个位置。数组中的每个元素代表你在该位置可以跳跃的最大长度。你的目标是利用最少的跳跃次数到达数组的末了一个位置。
Tips：只要i遇到当前最大范围，加+1。
--------------- python ---------------

1. class Solution:
2.     def jump(self, nums):
3.         cur_distance = 0  # 当前覆盖的最远距离下标
4.         ans = 0  # 记录走的最大步数
5.         next_distance = 0  # 下一步覆盖的最远距离下标
6.         
7.         for i in range(len(nums) - 1):  # 注意这里是小于len(nums) - 1，这是关键所在
8.             next_distance = max(nums[i] + i, next_distance)  # 更新下一步覆盖的最远距离下标
9.             if i == cur_distance:  # 遇到当前覆盖的最远距离下标
10.                 cur_distance = next_distance  # 更新当前覆盖的最远距离下标
11.                 ans += 1
12.         
13.         return ans

复制代码

--------------- c++ ---------------  

1. class Solution {
2. public:
3.     int jump(vector<int>& nums) {
4.         int c=0;
5.         int cover=0;
6.         int next_cover=0;
7.         for(int i=0;i<nums.size()-1;i++){
8.             next_cover=max(next_cover,i+nums[i]);
9.             if(i==cover){
10.                 cover=next_cover;
11.                 c+=1;
12.             }
13.         }
14.         return c;
15.     }
16. };

复制代码

 3、452 用最少数目标箭引爆气球 

452. 用最少数目标箭引爆气球 - 力扣（LeetCode）
标题形貌：在二维空间中有许多球形的气球。对于每个气球，提供的输入是程度方向上，气球直径的开始和竣事坐标。由于它是程度的，以是纵坐标并不告急，因此只要知道开始和竣事的横坐标就富足了。开始坐标总是小于竣事坐标。一支弓箭可以沿着 x 轴从差别点完全垂直地射出。在坐标 x 处射出一支箭，如有一个气球的直径的开始和竣事坐标为 xstart，xend， 且满足  xstart ≤ x ≤ xend，则该气球会被引爆。可以射出的弓箭的数目没有限定。 弓箭一旦被射出之后，可以无穷地进步。我们想找到使得全部气球全部被引爆，所需的弓箭的最小数目。给你一个数组 points ，此中 points = [xstart,xend] ，返回引爆全部气球所必须射出的最小弓箭数。
--------------- python ---------------

1. class Solution:
2.     def findMinArrowShots(self, points: List[List[int]]) -> int:
3.         if len(points) == 0: return 0
4.         points.sort(key=lambda x: x[0])
5.         result = 1
6.         for i in range(1, len(points)):
7.             if points[i][0] > points[i - 1][1]: # 气球i和气球i-1不挨着，注意这里不是>=
8.                 result += 1     
9.             else:
10.                 points[i][1] = min(points[i - 1][1], points[i][1]) # 更新重叠气球最小右边界
11.         return result

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     static bool dfs(vector<int>&a,vector<int>&b){
4.         if(a[0]==b[0]) return a[1]<b[1];
5.         else return a[0]<b[0];
6.     }
7.     int findMinArrowShots(vector<vector<int>>& points) {
8.         if(points.size()<2) return points.size();
9.         int n=1;
10.         sort(points.begin(),points.end(),dfs);
11.         for(int i=1;i<points.size();i++){
12.             if(points[i][0]>points[i-1][1]) n++;
13.             else points[i][1]=min(points[i][1],points[i-1][1]);
14.         }
15.         return n;
16.     }
17. };

复制代码

 4、435 无重叠区间 

435. 无重叠区间 - 力扣（LeetCode）
标题形貌：给定一个区间的聚集，找到须要移除区间的最小数目，使剩余区间互不重叠。留意: 可以以为区间的止境总是大于它的出发点。 区间 [1,2] 和 [2,3] 的边界相互“打仗”，但没有相互重叠。
--------------- python ---------------

1. class Solution:
2.     def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
3.         if not intervals:
4.             return 0
5.         
6.         intervals.sort(key=lambda x: x[0])  # 按照左边界升序排序
7.         count = 0  # 记录重叠区间数量
8.         
9.         for i in range(1, len(intervals)):
10.             if intervals[i][0] < intervals[i - 1][1]:  # 存在重叠区间
11.                 intervals[i][1] = min(intervals[i - 1][1], intervals[i][1])  # 更新重叠区间的右边界
12.                 count += 1
13.         
14.         return count

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     static bool cmp(vector<int>&a,vector<int>&b){
4.         if(a[0]==b[0]) return a[1]<b[1];
5.         else return a[0]<b[0];
6.     }
7.     int eraseOverlapIntervals(vector<vector<int>>& intervals) {
8.         if(intervals.size()<2) return 0;
9.         int n=0;
10.         sort(intervals.begin(),intervals.end(),cmp);
11.         for(int i=1;i<intervals.size();i++){
12.             if(intervals[i][0]<intervals[i-1][1]){
13.                 n++;
14.                 intervals[i][1]=min(intervals[i][1],intervals[i-1][1]);
15.             }
16.         }
17.         return n;
18.     }
19. };

复制代码

 5、763 分别字母区间

763. 分别字母区间 - 力扣（LeetCode）
标题形貌：字符串 S 由小写字母构成。我们要把这个字符串分别为尽大概多的片断，同一字母最多出现在一个片断中。返回一个表现每个字符串片断的长度的列表。
Tips：这道题不是很像贪婪，没有局部最优推出全局最优的过程。(用最远间隔模仿圈字符）

• 统计每一个字符末了出现的位置
  
• 重新遍历字符，并更新字符的最远出现下标，假如找到字符最远出现位置下标和当前下标相称了，则找到了分割点
  

--------------- python ---------------

1. class Solution:
2.     def partitionLabels(self, s: str) -> List[int]:
3.         last_occurrence = {}  # 存储每个字符最后出现的位置
4.         for i, ch in enumerate(s):
5.             last_occurrence[ch] = i
6.             # 赋值是写的操作不会报错，但是如果是访问是读的操作不存在的键会报错
8.         result = []
9.         start = 0
10.         end = 0
11.         for i, ch in enumerate(s):
12.             end = max(end, last_occurrence[ch])  # 找到当前字符出现的最远位置
13.             if i == end:  # 如果当前位置是最远位置，表示可以分割出一个区间
14.                 result.append(end - start + 1)
15.                 start = i + 1
17.         return result

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     vector<int> partitionLabels(string s) {
4.         unordered_map<int,int> m;
5.         for(int i=0;i<s.size();i++){
6.             m[s[i]]=i;
7.         }
8.         vector<int> v;
9.         int dis=0;
10.         int max_dis=0;
11.         for(int i=0;i<s.size();i++){
12.             max_dis=max(max_dis,m[s[i]]);
13.             if(i==max_dis) {
14.                 v.push_back(i-dis+1);
15.                 dis=i+1;
16.             }
17.         }
18.         return v;
19.     }
20. };

复制代码

 6、56 归并区间 

56. 归并区间 - 力扣（LeetCode）
标题形貌：给出一个区间的聚集，请归并全部重叠的区间。
--------------- python ---------------

1. class Solution:
2.     def merge(self, intervals):
3.         result = []
4.         if len(intervals) == 0:
5.             return result  # 区间集合为空直接返回
7.         intervals.sort(key=lambda x: x[0])  # 按照区间的左边界进行排序
9.         result.append(intervals[0])  # 第一个区间可以直接放入结果集中
11.         for i in range(1, len(intervals)):
12.             if result[-1][1] >= intervals[i][0]:  # 发现重叠区间
13.                 # 合并区间，只需要更新结果集最后一个区间的右边界，因为根据排序，左边界已经是最小的
14.                 result[-1][1] = max(result[-1][1], intervals[i][1])
15.             else:
16.                 result.append(intervals[i])  # 区间不重叠
18.         return result

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     static bool cmp(vector<int>&a,vector<int>&b){
4.         if(a[0]==b[0]) return a[1]<b[1];
5.         else return a[0]<b[0];
6.     }
7.     vector<vector<int>> merge(vector<vector<int>>& intervals) {
8.         vector<vector<int>> res;
9.         if(intervals.size()<2) return intervals;
10.         sort(intervals.begin(),intervals.end(),cmp);
11.         for(int i=1;i<intervals.size();i++){
12.             if(intervals[i][0]<=intervals[i-1][1]){
13.                 intervals[i][0]=min(intervals[i][0],intervals[i-1][0]);
14.                 intervals[i][1]=max(intervals[i][1],intervals[i-1][1]);
15.             }
16.             else res.push_back(intervals[i-1]);
17.         }
18.         res.push_back(intervals[intervals.size()-1]);
19.         return res;
20.     }
21. };

复制代码

 六、有点难度-其他

1、53 最大子序和

53. 最大子数组和 - 力扣（LeetCode）
标题形貌：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包罗一个元素），返回其最大和。
--------------- python ---------------

1. class Solution:
2.     def maxSubArray(self, nums):
3.         result = float('-inf')  # 初始化结果为负无穷大
4.         count = 0
5.         for i in range(len(nums)):
6.             count += nums[i]
7.             if count > result:  # 取区间累计的最大值（相当于不断确定最大子序终止位置）
8.                 result = count
9.             if count <= 0:  # 相当于重置最大子序起始位置，因为遇到负数一定是拉低总和
10.                 count = 0
11.         return result

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     int maxSubArray(vector<int>& nums) {
4.         int res=INT_MIN;
5.         int c=0;
6.         for(int i:nums){
7.             c+=i;
8.             if(c>res) res=c;
9.             if(c<0) c=0;
10.         }
11.         return res;
12.     }
13. };

复制代码

 2、134 加油站

134. 加油站 - 力扣（LeetCode）
标题形貌：在一条环路上有 N 个加油站，此中第 i 个加油站有汽油 gas 升。你有一辆油箱容量无穷的的汽车，从第 i 个加油站开往第 i+1 个加油站须要斲丧汽油 cost 升。你以后中的一个加油站出发，开始时油箱为空。假如你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
Tips：假如总油量减去总斲丧大于即是零那么肯定可以跑完一圈，阐明 各个站点的加油站 剩油量rest相加肯定是大于即是零的。
--------------- python ---------------

1. class Solution:
2.     def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
3.         curSum = 0  # 当前累计的剩余油量
4.         totalSum = 0  # 总剩余油量
5.         start = 0  # 起始位置
6.         
7.         for i in range(len(gas)):
8.             curSum += gas[i] - cost[i]
9.             totalSum += gas[i] - cost[i]
10.             
11.             if curSum < 0:  # 当前累计剩余油量curSum小于0
12.                 start = i + 1  # 起始位置更新为i+1
13.                 curSum = 0  # curSum重新从0开始累计
14.         
15.         if totalSum < 0:
16.             return -1  # 总剩余油量totalSum小于0，说明无法环绕一圈
17.         return start

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
4.         int start=0;
5.         int cur=0;
6.         int total=0;
7.         for(int i=0;i<gas.size();i++){
8.             cur+=gas[i]-cost[i];
9.             total+=gas[i]-cost[i];
10.             if(cur<0){
11.                 cur=0;
12.                 start=i+1;
13.             }
14.         }
15.         if(total<0) return -1;
16.         return start;
17.     }
18. };

复制代码

3、968 监控二叉树

968. 监控二叉树 - 力扣（LeetCode）
标题形貌：给定一个二叉树，我们在树的节点上安装摄像头。节点上的每个拍照头都可以监视其父对象、自身及其直接子对象。盘算监控树的全部节点所需的最小摄像头数目。
Tips：局部最优--叶子节点的父节点有摄像头；团体最优--全部摄像头数目最少。
--------------- python ---------------

1. class Solution:
2.          # Greedy Algo:
3.         # 从下往上安装摄像头：跳过leaves这样安装数量最少，局部最优 -> 全局最优
4.         # 先给leaves的父节点安装，然后每隔两层节点安装一个摄像头，直到Head
5.         # 0: 该节点未覆盖
6.         # 1: 该节点有摄像头
7.         # 2: 该节点有覆盖
8.     def minCameraCover(self, root: TreeNode) -> int:
9.         # 定义递归函数
10.         result = [0]  # 用于记录摄像头的安装数量
11.         # 对根节点状态检验，防止根节点无覆盖
12.         if self.traversal(root, result) == 0:
13.             result[0] += 1
15.         return result[0]
17.         
18.     def traversal(self, cur: TreeNode, result: List[int]) -> int:
19.         if not cur:
20.         # 空节点默认为 有覆盖状态，避免在叶子节点上放摄像头
21.             return 2
23.         left = self.traversal(cur.left, result)
24.         right = self.traversal(cur.right, result)
26.         # 情况1: 左右节点都有覆盖
27.         if left == 2 and right == 2:
28.             return 0
30.         # 情况2:
31.         # left == 0 && right == 0 左右节点无覆盖
32.         # left == 1 && right == 0 左节点有摄像头，右节点无覆盖
33.         # left == 0 && right == 1 左节点无覆盖，右节点有摄像头
34.         # left == 0 && right == 2 左节点无覆盖，右节点覆盖
35.         # left == 2 && right == 0 左节点覆盖，右节点无覆盖
36.         elif left == 0 or right == 0:
37.             result[0] += 1
38.             return 1
40.         # 情况3:
41.         # left == 1 && right == 2 左节点有摄像头，右节点有覆盖
42.         # left == 2 && right == 1 左节点有覆盖，右节点有摄像头
43.         # left == 1 && right == 1 左右节点都有摄像头
44.         else:
45.             return 2

复制代码

附一个报错代码：（直接利用result作为一个值）

1. class Solution:
2.     def minCameraCover(self, root: Optional[TreeNode]) -> int:
3.         result=0
4.         if traversal(root)==0:
5.             result+=1
6.    
7.         def traversal(cur):
8.             #nonlocal result  需要nonlocal 修饰
9.             if not cur:
10.                 return 2
11.             left=traversal(cur.left)
12.             right=traversal(cur.right)
13.             if left==2 and right==2:
14.                 return 0
15.             elif left==0 or right==0:
16.                 result+=1
17.                 return 1
18.             else:
19.                 return 2
21.         return result
23. -----------------
24. 1、这样子函数定义需要在函数调用前
25. 2、在traversal函数内，你尝试修改result（result+=1）.
26. 但是result在traversal函数的作用域外部定义.
27. 因此在traversal函数内部直接修改它会导致错误。

复制代码

再附一个错误：

1. class Solution:
2.     def minCameraCover(self, root: Optional[TreeNode]) -> int:
3.         result=0
4.         
5.         def traversal(cur,result):
6.             if not cur:
7.                 return 2
8.             left=traversal(cur.left,result)
9.             right=traversal(cur.right,result)
10.             if left==2 and right==2:
11.                 return 0
12.             elif left==0 or right==0:
13.                 result+=1
14.                 return 1
15.             else:
16.                 return 2
18.         if traversal(root,result)==0:
19.             result+=1
21.         return result
23. ------------------
24. 将result作为参数传递给traversal函数。
25. 在递归过程中，即使修改了result，这个修改不会反映到外部作用域中。
26. 最后输出就是0。

复制代码

--------------- c++ --------------- 

1. class Solution {
2. public:
3.     int res=0;
4.     int dfs(TreeNode*root){
5.         if(!root) return 2;
6.         int l=dfs(root->left);
7.         int r=dfs(root->right);
8.         if(l==2&&r==2) return 0;
9.         else if(l==0 || r==0) {
10.             res+=1;
11.             return 1;
12.         }
13.         else return 2;
14.     }
15.     int minCameraCover(TreeNode* root) {
16.         if(dfs(root)==0) res+=1;
17.         return res;
19.     }
20. };

复制代码