做门户网站用什么服务器,平面设计要什么学历,免费网站建设范例,住房和城乡建设部网站防烟排烟第31天#xff0c;贪心最后一节(ง •_•)ง#x1f4aa;#xff0c;编程语言#xff1a;C
目录
56.合并区间
738.单调递增的数字
968.监控二叉树
贪心算法总结 56.合并区间 文档讲解#xff1a;代码随想录合并区间 视频讲解#xff1a;手撕合并区间 题目#xf…第31天贪心最后一节(ง •_•)ง编程语言C
目录
56.合并区间
738.单调递增的数字
968.监控二叉树
贪心算法总结 56.合并区间 文档讲解代码随想录合并区间 视频讲解手撕合并区间 题目 学习本题属于区间问题同样是找到重合的区间与用最少数量的箭引爆气球和无重叠区间问题解法是相同的。
本题可以先对区间进行排序便于找到重叠区间可以依照每个区间的左边界从小到大排序。之后比较后续区间的左边界与前一个区间的右边界的关系判断是否重叠。如果不重叠则加入答案数组中如果重叠则更新最大右边界。
代码
//时间复杂度O(nlogn)快速排序时间复杂度
//空间复杂度O(logn)快速排序空间复杂度
class Solution {
public:static bool camp(vectorint a, vectorint b) {return a[0] b[0];}vectorvectorint merge(vectorvectorint intervals) {//先进行排序按照开始节点进行排序sort(intervals.begin(), intervals.end());vectorvectorint result; //返回数组//初始化左右边界int left intervals[0][0];int right intervals[0][1];for(int i 1; i intervals.size(); i) {if(intervals[i][0] right) {right max(right, intervals[i][1]);}else {result.push_back({left, right});right intervals[i][1];left intervals[i][0];}}//把最后一个点加入result.push_back({left, right});return result;}
};
本题还可以不设置单独的leftright来作为左边边界而是使用back()来作为右边界进行更新。同时由于我们提前进行了排序左边界又能够保证是按从小到大顺序进入的。
代码
class Solution {
public:vectorvectorint merge(vectorvectorint intervals) {//使用lambda表达式sort(intervals.begin(), intervals.end(), [](const vectorint a, const vectorint b){return a[0] b[0];});vectorvectorint result; //返回数组//使用back()来确定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.单调递增的数字 文档讲解代码随想录单调递增的数字 视频讲解手撕单调递增的数字 题目 学习本题重点在于需要比较每个位上的大小来判断是否是单调递增的。贪心的方法就在于如果数不是单调递增的该如何处理。假设出现 num[i - 1] num[i] 的情况也就是前一位比后一位大的情况。由于需要单调递增且不允许增大数因此我们的贪心逻辑是一旦出现num[i - 1] num[i]的情况我们就将前一位num[i - 1]--同时将num[i]及以后的位变为9这样就既能保证单调递增数又是最大的。
本题我们需要从后往前遍历我们需要利用后面比较的结果。以332为例子如果从前往后遍历将得到329显然答案不对。如果从后往前遍历则是299显然最终答案应该是这个。
写代码的时候可以注意两个关键点
可以利用to_string()函数将数字变换为字符串方便进行遍历处理。最后可以通过stoi()函数将字符串重新转变为int型变量。可以设置一个flag位确定后续要变9的位置显然我们只要找到最后一个需要减1的位置后面的位就是需要置为9的。
代码
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int monotoneIncreasingDigits(int n) {//从后往前遍历遇到前面的数大的情况进行“前减一后置9”的操作string str to_string(n); //为了方便遍历将int型变量转换为字符串★int flag str.size(); //记录需要后置为9的位置//找到最后一个不单调的位置for(int i str.size() - 1; i 0; i--) {if(str[i] str[i - 1]) {flag i; //记录需要变9的位置str[i - 1]--; //进行减1} }for(int i flag; i str.size(); i) {str[i] 9; //进行变9}return stoi(str);}
}; 968.监控二叉树 文档讲解代码随想录监控二叉树 视频讲解手撕监控二叉树 题目 学习本题的关键在于思考如何放置摄像头才能使得摄像头的数量最小。从例子中我们可以发现摄像头均没有放在叶子节点上。我们知道摄像头能够覆盖上中下三层如果摄像头放在叶子节点上就必然会使得有一层是浪费的。虽然头节点放摄像头也会使得浪费一层但是相较于头节点叶子节点显然更多因此叶子节点不放摄像头数量节省下来的是指数阶的。
本题的贪心就在于局部最优让叶子节点的父节点安装摄像头摄像头数量最少整体最优全部摄像头数量所用最少。
理解了上述的贪心逻辑我们还需要解决如下两个问题1.二叉树的遍历2.如何隔两个节点放一个摄像头。
1.二叉树的遍历顺序显然我们要保证叶子节点的父节点有摄像头且要尽可能的少放摄像头我们需要从底往上判断当前位置是否被覆盖是否放置摄像头。因此需要采用后序遍历的方式。
2.如何隔两个节点放一个摄像头对于一个节点来说可能存在3种状态没有被覆盖该处有摄像头该处没有摄像头但是被覆盖。而对于一个节点是否要安装一个摄像头我们就需要判断左右孩子处于什么状态如果左右孩子有一个处于没有被覆盖的状态我们就需要在当前节点安装一个摄像头并告诉其父节点自身有摄像头。
基于以上需求我们可以设置3个数字来表示当前节点的状态
0该节点无覆盖1本节点有摄像头2本节点有覆盖。
然后通过递推关系来判断当前节点应该处于什么状态。如果处于1状态我们就需要记录一个摄像头。
接下来我们就需要进行遍历过程中递归三部曲的设置了
1.确定返回值和参数列表由于我们需要使用三个数字来表示当前节点的状态因此我们返回值需设置为int型参数列表传入root。
2.确定终止条件由于我们需要左右孩子的情况来判断当前节点处于的状态因此我们需要遍历到最后的空节点解决只有左右一个孩子的情况而对于空节点应该处于什么状态我们需要进行确定。为了让叶子节点不放摄像头而叶子节点的父节点放摄像头则叶子节点应该处于无覆盖的情况且不能放置摄像头因此空节点应该处于的是有覆盖的情况这样才能推出叶子节点是无覆盖的。
3.单层递归逻辑采用的是后序遍历而后我们需要处理的“中”逻辑有四种情况
左右节点都有覆盖则此时中间节点就应该是无覆盖的情况左右节点至少有一个无覆盖的情况则中间节点应该安装一个摄像头。左右节点至少有一个有摄像头则中间节点处于有覆盖的情况。头结点没有覆盖头节点我们需要单独进行处理因为头节点可能处于没有覆盖的情况。
基于以上我们可以写出代码
//时间复杂度O(n)
//空间复杂度O(n)
class Solution {
public:int result 0; //定义全局变量记录摄像头的个数//遍历树1.确定返回值和参数列表//我们使用012来表示当前节点的三种状态无覆盖(0)、有摄像头(1)、有覆盖(2);int traversal(TreeNode* root) {//确定终止条件if(root nullptr) {return 2; //为了让叶子节点的父节点安装摄像头空节点应设置为有覆盖这样遍历到叶子节点默认左右孩子为有覆盖自身为无覆盖。}//采用后续遍历的方式进行单层递归逻辑int left traversal(root-left); //左int right traversal(root-right); //右//中分为三种情况//1.左右孩子均为有覆盖if(left 2 right 2) {return 0; //则当前节点返回无覆盖}//2.左右孩子有一个是无覆盖(包含了5种情况)// 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.在上一个情况筛选的基础上左右孩子有一个是有摄像头的if(left 1 || right 1) {return 2; //返回有覆盖}return -1; //在没有写else的情况下需要加一个return但实际上该return不会运行到}int minCameraCover(TreeNode* root) {//头节点单独处理判断if(traversal(root) 0) { //如果头节点没有被覆盖result;}return result;}
}; 贪心算法总结 文档讲解代码随想录贪心算法总结 贪心算法一句话没有套路多加练习手动模拟。
贪心算法的题目可以分为 题目之间并没有明显的顺序关系重点还是要多加联系。
一个系列的结束标志着另一个系列的开始动态规划继续加油
