leetcode算法刷题的第二十七天
1.leetcode 56.合并区间
题目链接
class Solution {
public:static bool cmp(const vector<int>& a,const vector<int>& b){return a[0]<b[0];}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上直接合并result.push_back(intervals[0]);for(int i=1;i<intervals.size();i++){if(intervals[i][0]<=result.back()[1]){// 发现重叠区间// 合并区间，只更新右边界就好，因为result.back()的左边界一定是最小值，因为我们按照左边界排序的result.back()[1]=max(result.back()[1],intervals[i][1]);}else{result.push_back(intervals[i]);// 区间不重叠,直接放进去就可以了}}return result;}
};思路总结:本题的本质还是判断重叠区间的问题
一样的套路，先排序，让所有的相邻区间尽可能的重叠在一起，按左边界，或者右边界排序都可以，处理逻辑稍有不同。
按照左边界从小到大排序之后，如果 intervals[i][0] <= intervals[i - 1][1] 即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）
其实就是用合并区间后左边界和右边界，作为一个新的区间，加入到result数组里就可以了。如果没有合并就把原区间加入到result数组。
2.leetcode 738.单调递增的数字
题目链接
class Solution {
public:int monotoneIncreasingDigits(int n) {//把数字n转化成字符串类型string strNum=to_string(n);// flag用来标记赋值9从哪里开始// 设置为这个默认值，为了防止第二个for循环在flag没有被赋值的情况下执行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';}//把字符串类型转化成整型int result=stoi(strNum);return result;}
};思路总结:
题目要求小于等于N的最大单调递增的整数，那么拿一个两位的数字来举例。
例如：98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]--，然后strNum[i]给为9，这样这个整数就是89，即小于98的最大的单调递增整数。
这一点如果想清楚了，这道题就好办了。
此时是从前向后遍历还是从后向前遍历呢？
从前向后遍历的话，遇到strNum[i - 1] > strNum[i]的情况，让strNum[i - 1]减一，但此时如果strNum[i - 1]减一了，可能又小于strNum[i - 2]。
这么说有点抽象，举个例子，数字：332，从前向后遍历的话，那么就把变成了329，此时2又小于了第一位的3了，真正的结果应该是299。
那么从后向前遍历，就可以重复利用上次比较得出的结果了，从后向前遍历332的数值变化为：332 -> 329 -> 299
确定了遍历顺序之后，那么此时局部最优就可以推出全局，找不出反例，试试贪心。
本题只要想清楚个例，例如98，一旦出现strNum[i - 1] > strNum[i]的情况（非单调递增），首先想让strNum[i - 1]减一，strNum[i]赋值9，这样这个整数就是89。就可以很自然想到对应的贪心解法了。
想到了贪心，还要考虑遍历顺序，只有从后向前遍历才能重复利用上次比较的结果。
最后代码实现的时候，也需要一些技巧，例如用一个flag来标记从哪里开始赋值9。
这里解释一下两个特殊的函数,分别是to_string和stoi函数
to_string函数就是将一个整型变量转化为一个字符串变量,这样方便我们进行计算统计处理
stoi函数就是to_string函数的反向操作,将一个字符串变量转化为一个整型变量
一般都是这两个函数相互使用,这样容易我们写出一些题目
3.leetcode 968.监控二叉树
题目链接
这道题是力扣里面名副其实的hard题目,大家可以感受感受,这里就直接给出题解了,就不总结了
/*** 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 result;int traversal(TreeNode* current){// 空节点，该节点有覆盖if(current==NULL) return 2;int left=traversal(current->left);//左int right=traversal(current->right);//右// 情况1// 左右节点都有覆盖if(left==2&&right==2) return 0;// 情况2// left == 0 && right == 0 左右节点无覆盖// left == 1 && right == 0 左节点有摄像头，右节点无覆盖// left == 0 && right == 1 左节点有无覆盖，右节点摄像头// left == 0 && right == 2 左节点无覆盖，右节点覆盖// left == 2 && right == 0 左节点覆盖，右节点无覆盖if(left==0||right==0){result++;return 1;}// 情况3// left == 1 && right == 2 左节点有摄像头，右节点有覆盖// left == 2 && right == 1 左节点有覆盖，右节点有摄像头// left == 1 && right == 1 左右节点都有摄像头// 其他情况前段代码均已覆盖if(left==1||right==1) return 2;// 以上代码我没有使用else，主要是为了把各个分支条件展现出来，这样代码有助于读者理解// 这个 return -1 逻辑不会走到这里。return -1;}int minCameraCover(TreeNode* root) {result=0;//情况4if(traversal(root)==0){//root无覆盖result++;}return result;}
};4.贪心算法总结
贪心算法本身没有什么规律,能写的出来真的很不容易
贪心算法的简单题可能往往过于简单甚至感觉不到贪心,但是贪心的难题又真的有点难,而且贪心也没有什么框架和套路,所以对刷题的顺序没有什么要求
1.贪心很简单,就是常识?
跟着刷题的同学们就会发现,贪心思路往往很巧妙,并不简单
2.贪心有没有固定的套路?
贪心无套路，也没有框架之类的，需要多看多练培养感觉才能想到贪心的思路。
3.究竟什么题目是贪心呢？
个人认为：如果找出局部最优并可以推出全局最优，就是贪心，如果局部最优都没找出来，就不是贪心，可能是单纯的模拟。（并不是权威解读，一家之辞哈）
但我们也不用过于强调什么题目是贪心，什么不是贪心，那就太学术了，毕竟学会解题就行了。
4.如何知道局部最优推出全局最优,有数学证明吗?
在做贪心题的过程中，如果再来一个数据证明，其实没有必要，手动模拟一下，如果找不出反例，就试试贪心。面试中，代码写出来跑过测试用例即可，或者自己能自圆其说理由就行了
就像是 要用一下 1 + 1 = 2，没有必要再证明一下 1 + 1 究竟为什么等于 2。（例子极端了点，但是这个道理）
很多没有接触过贪心的同学都会感觉贪心有啥可学的,但只要跟着这个博客坚持下来可以发现,贪心是一种很重要的算法思维而且并不简单,贪心往往妙的出其不意,猝不及防
这也是我认为判断这是一道贪心题目的依据，如果找不出局部最优，那可能就是一道模拟题。