Day31| 56. 合并区间、738.单调递增的数字、968.监控二叉树

文章链接

56. 合并区间

整体思路：

• 先按照左边界排序

• 遍历集合，如果某元素的左边界大于上一个元素的有边界，没有重叠区间；如果某元素的左边界小于上一个元素的右边界，有重叠区间，更新前一个元素的右边界为当前元素的右边界

1. 排序阶段（关键步骤）

• 首先按照每个区间的起始值（start）升序排序。

• 这样可以保证后一个区间的起点 ≥ 前一个区间的起点，为后续合并做准备。

1. 遍历并合并区间

• 使用一个变量 current 保存正在处理的区间。

• 遍历排序后的区间数组：

• 如果当前遍历到的区间 intervals[i] 的起点 <= current 的终点：

  • 说明两者有重叠或相连，更新当前区间的终点为：

    current[1] = max(current[1], intervals[i][1])

• 否则：

  • 当前区间已经结束，将其加入结果集 res。

  • 然后更新 current = intervals[i]，开始新的合并。

1. 最后加入最后一个区间

• 循环结束后，最后的 current 也要加入结果集。

1. 返回结果

• 将 List<int[]> 转换成 int[][] 返回。

public class Solution {public int[][] Merge(int[][] intervals) {if(intervals.Length==0) return new int[0][];Array.Sort(intervals,(a,b)=>a[0].CompareTo(b[0]));List<int[]> res =new List<int[]>();int[] current=intervals[0];for(int i=1;i<intervals.Length;i++){//区间重叠if(intervals[i][0]<=current[1]){current[1]=Math.Max(current[1],intervals[i][1]);}//区间未重叠else{res.Add(current);current=intervals[i];}}res.Add(current);return res.ToArray();}
}

738.单调递增的数字

思路：

1. 首先将数字n转换称字符数组，逐位处理

2. 设置flag用来标记从哪个位置开始不满足单调增

3. 从flag开始，将所有的位置设置为9，保证是最大的合法数

4. 将字符数组换成整数输出

public class Solution {public int MonotoneIncreasingDigits(int n) {char[] s=n.ToString().ToCharArray();int flag=s.Length;// 从右向左遍历，找第一个不满足单调递增的位置for(int i=s.Length-1;i>0;i--){if(s[i-1]>s[i]){// 找到了下降点：第 i-1 位大于第 i 位flag=i;s[i-1]--;}}// 从 flag 开始将所有位都设置为 '9'，保证是最大的合法数for(int i=flag;i<s.Length;i++){s[i]='9';}return int.Parse(new string(s));}
}

968.监控二叉树 （可跳过）

思路：

1. 从下往上看，让叶子节点的父节点安装摄像头，然后每隔两个安装一个摄像头，直到二叉树的头结点

2. 从下向上需要用到后序遍历 左右中

3. 每个节点有三种状态：

• 该节点无覆盖--0

• 本节点有摄像头--1

• 本节点有覆盖（为了减少摄像头数量，将空节点状态视为有覆盖）--2

1. 递归的四种情况：

• 左右节点都有覆盖→中间节点无覆盖

• 左右节点至少有一个无覆盖的情况→中间节点放摄像头

• 左右节点至少有一个有摄像头→中间节点是已覆盖的状态

• 头结点没有覆盖→头结点安装一个摄像头

public class Solution {public int res=0;public int MinCameraCover(TreeNode root) {if(Traversal(root)==0) res++;return res;}public int Traversal(TreeNode cur){if(cur==null) return 2;// 后序遍历，先处理左右子树int left=Traversal(cur.left);int right=Traversal(cur.right);// 情况 1：左右孩子都被监控（返回 2），但它们自己都没有摄像头（返回 0）if(left==2&&right==2){return 0;}// 情况 2：任一子节点未被监控，当前节点必须放摄像头if(left==0||right==0){res++;return 1;}// 情况 3：子节点有摄像头（left == 1 或 right == 1），自己已被监控else{return 2;}}
}