56. 合并区间
思路：这道题目跟前面的重叠区间很像，还要简单一点，首先最简单的，如果没有重叠，那么直接将这个区间加入结果数组就可以了，如果重叠了，就更新结果数组结尾区间的有边界，取两个有边界的最大值，最后返回这个结果数组即可。
我的代码：
class Solution {
private:
static bool cmp(const vector<int>& a,const vector<int>& b) {
return a[0]<b[0];
}
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
if(intervals.size()==0) return result;
sort(intervals.begin(),intervals.end(),cmp);
result.push_back(intervals[0]);
for(int i=1;i<intervals.size();i++) {
if(intervals[i][0]<=result.back()[1]) {
result.back()[1]=max(result.back()[1],intervals[i][1]);
}
else {
result.push_back(intervals[i]);
}
}
return result;
}
};
738. 单调递增的数字
思路：这道题目乍一看挺好理解，其实暗藏玄机。我们可以发现，当从左到右发现这相邻两个数没有递增，那么左边的数字数量级就要减1，同时右边的数字需要都取9。大概思路确定，实操的时候发现从左到右不对，实际上要从右到左操作，同时，最大的坑是需要一个flag，记录从什么位置开始数量级减1，这个时候这个数之后的所有数都要变成9，才能找到最大，不用flag记录就会发现比如1000，遍历之后变为0900的现象，最后返回这个数就行。注意，在这个过程中需要用到字符串函数to_string和stoi（string to int)。
我的代码：
class Solution {
public:
int monotoneIncreasingDigits(int n) {
string strNum=to_string(n);
int flag=strNum.size();
for(int i=strNum.size()-1;i>0;i–) {
if(strNum[i-1]>strNum[i]) {
strNum[i-1]–;
flag=i;
}
}
for(int i=flag;i<strNum.size();i++) {
strNum[i]='9';
}
return stoi(strNum);
}
};
968. 监控二叉树
思路：这道题目是真的很难，第一次在力扣看到算术评级是9级的题目。摄像头可以覆盖上中下三层，如果把摄像头放在叶子节点上，就浪费的一层的覆盖。所以把摄像头放在叶子节点的父节点位置，才能充分利用摄像头的覆盖面积。首先开始要确定遍历顺序，因为要从下往上遍历，所以要用后序遍历（左右中）。然后讨论节点情况，
每个节点可能有几种状态：
- 该节点无覆盖
- 本节点有摄像头
- 本节点有覆盖
我们分别有三个数字来表示：
- 0：该节点无覆盖
- 1：本节点有摄像头
- 2：本节点有覆盖
主要有如下四类情况：
情况1：左右节点都有覆盖。
左孩子有覆盖，右孩子有覆盖，那么此时中间节点应该就是无覆盖的状态了。
情况2：左右节点至少有一个无覆盖的情况。
此时不管怎样得把那个没有覆盖的节点覆盖了，则中间节点（父节点）应该放摄像头。
情况3：左右节点至少有一个有摄像头。
其实就是 左右孩子节点有一个有摄像头了，那么其父节点就应该是2（覆盖的状态）。
情况4：头结点没有覆盖如果没有覆盖，result++。
这里有一个我踩过的坑，就是情况2和情况3一定是2先判断，必须先把没覆盖的节点覆盖了，再去判断情况3，不然就会有样例过不了，因为可能先判断一个节点有摄像头，一个节点没覆盖，就给父节点状态2，这样那个没覆盖的节点就一直不会被覆盖，造成结果错误。
这里放一张我自己画的一个示意图：
画的有点丑，本来只是方便自己理解，但是想了想放上来分享一下也没事（）。
我的代码：
class Solution {
private:
int result;
int tranversal(TreeNode* cur) {
if(cur==NULL) return 2;
int left=tranversal(cur->left);
int right=tranversal(cur->right);
if(left==2&&right==2) return 0;
if(left==0||right==0)
{
result++;
return 1;
}
if(left==1||right==1) return 2;
return -1;
}
public:
int minCameraCover(TreeNode* root) {
result=0;
if(tranversal(root)==0) result++;
return result;
}
};
今日总结
今天贪心算法就完结了，虽然下次碰到新的贪心题不一定会，但是主要是知道了贪心的一些常见思路，思考的方式等等。这个专题还是多做多总结吧，是个锻炼思维能力的好专题，加油！接下来就是动态规划了。
