网站如何创建首页,网络营销代理,做网络营销如何建立自己的网站,建设局目录
56. 合并区间
方法1#xff1a;fff
看方法2#xff1a;fff优化版
方法3#xff1a;
738.单调递增的数字
968.监控二叉树#xff08;贪心二叉树#xff09; 56. 合并区间
判断重叠区间问题#xff0c;与452和435是一个套路
方法1#xff1a;fff
看方法2fff
看方法2fff优化版
方法3
738.单调递增的数字
968.监控二叉树贪心二叉树 56. 合并区间
判断重叠区间问题与452和435是一个套路
方法1fff
看方法2fff优化版
使用currentInterval来追踪当前合并的区间而不是在原数组上修改值。每当找到一个不重叠的区间时将currentInterval添加到result并开始一个新的currentInterval。
class Solution {public int[][] merge(int[][] intervals) {// 方法1fff
// if (intervals.length 1){
// return intervals;
// }
// Arrays.sort(intervals,(a,b)-Integer.compare(a[0],b[0]));
// int[][] result new int[intervals.length][];
// int row 0;
// for (int i 0; i intervals.length - 1; i) {
// if (intervals[i 1][0] intervals[i][1]){
// intervals[i 1][0] Math.min(intervals[i][0],intervals[i 1][0]);
// intervals[i 1][1] Math.max(intervals[i][1],intervals[i 1][1]);
// } else {
// result[row] intervals[i];
// }
// }
// result[row] intervals[intervals.length - 1];
// int[][] res new int[row1][];
// int i 0;
// for (int[] r : result){
// if (r null){
// break;
// }
// res[i] r;
// }
// return res;// 方法2fff优化版if (intervals.length 1){return intervals;}// 排序的时间复杂度是O(n log n), n是intervals数组的长度。Arrays.sort(intervals,(a,b)-Integer.compare(a[0],b[0]));Listint[] result new LinkedList();int[] currentInterval intervals[0]; // 使用currentInterval来追踪当前合并的区间而不是在原数组上修改值。for (int i 1; i intervals.length ; i) {if (intervals[i][0] currentInterval[1]){// 合并currentInterval[1] Math.max(currentInterval[1], intervals[i][1]);} else {result.add(currentInterval);currentInterval intervals[i];}}result.add(currentInterval);return result.toArray(new int[result.size()][]);}
}
方法3
看方法2或者3都可以复杂度是一样的。都挺好的。
代码结构方法3实现直接使用LinkedListint[]的getLast()和removeLast()来获取和更新最后一个合并区间代码更加简洁且避免了在原数组上修改数据。操作顺序方法3实现中每次更新最后一个区间的值时先移除再添加这样减少了代码复杂性而方法2实现会在原数组上更新代码稍显繁琐。 class Solution {public int[][] merge(int[][] intervals) {//方法3LinkedListint[] res new LinkedList();Arrays.sort(intervals, (a, b) - Integer.compare(a[0], b[0]));res.add(intervals[0]);for (int i 1; i intervals.length; i) {if (intervals[i][0] res.getLast()[1]) {int start res.getLast()[0];int end Math.max(intervals[i][1], res.getLast()[1]);res.removeLast();res.add(new int[]{start, end});} else {res.add(intervals[i]);}}return res.toArray(new int[res.size()][]);}}
738.单调递增的数字
思路
例如98一旦出现strNum[i - 1] strNum[i]的情况非单调递增首先想让strNum[i - 1]减一strNum[i]赋值9这样这个整数就是89。
并且需要注意用一个flag来标记从哪里开始赋值9。后面的都要赋值9。
遍历顺序从后向前遍历
从前向后遍历的话遇到strNum[i - 1] strNum[i]的情况让strNum[i - 1]减一但此时如果strNum[i - 1]减一了可能又小于strNum[i - 2]。
这么说有点抽象举个例子数字332从前向后遍历的话那么就把变成了329此时2又小于了第一位的3了真正的结果应该是299。
那么从后向前遍历就可以重复利用上次比较得出的结果了从后向前遍历332的数值变化为332 - 329 - 299 class Solution {public int monotoneIncreasingDigits(int n) {if (n 10) {return n;}String str n ;char[] ch str.toCharArray();int index ch.length;for (int i ch.length - 1; i 0; i--) {if (ch[i] ch[i-1]) {index i;ch[index-1]--;}}for (int i index; i ch.length; i) {ch[i] 9;}String res new String(ch);return Integer.parseInt(res);}}
968.监控二叉树贪心二叉树
思路
摄像头可以覆盖上中下三层如果把摄像头放在叶子节点上就浪费的一层的覆盖。
所以把摄像头放在叶子节点的父节点位置才能充分利用摄像头的覆盖面积。
那么有同学可能问了为什么不从头结点开始看起呢为啥要从叶子节点看呢
因为头结点放不放摄像头也就省下一个摄像头 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。
所以我们要从下往上看局部最优让叶子节点的父节点安摄像头所用摄像头最少整体最优全部摄像头数量所用最少
大体思路就是从低到上先给叶子节点父节点放个摄像头然后隔两个节点放一个摄像头直至到二叉树头结点。
此时这道题目还有两个难点
二叉树的遍历 后序遍历如何隔两个节点放一个摄像头
如何隔两个节点放一个摄像头
此时需要状态转移的公式大家不要和动态的状态转移公式混到一起本题状态转移没有择优的过程就是单纯的状态转移
来看看这个状态应该如何转移先来看看每个节点可能有几种状态分别有三个数字来表示
0该节点无覆盖1本节点有摄像头2本节点有覆盖
空节点的状态只能是有覆盖这样就可以在叶子节点的父节点放摄像头了
单层逻辑处理。
主要有如下四类情况
情况1左右节点都有覆盖
左孩子有覆盖右孩子有覆盖那么此时中间节点应该就是无覆盖的状态了。 情况2左右节点至少有一个无覆盖的情况
此时摄像头的数量要加一并且return 1代表中间节点放摄像头。
情况3左右节点至少有一个有摄像头
如果是以下情况其实就是 左右孩子节点有一个有摄像头了那么其父节点就应该是2覆盖的状态
left 1 right 2 左节点有摄像头右节点有覆盖left 2 right 1 左节点有覆盖右节点有摄像头left 1 right 1 左右节点都有摄像头 情况4头结点没有覆盖
以上都处理完了递归结束之后可能头结点 还有一个无覆盖的情况如图 所以递归结束之后还要判断根节点如果没有覆盖result class Solution {int res 0;public int minCameraCover(TreeNode root) {// 对根节点的状态做检验,防止根节点是无覆盖状态if (minCame2(root) 0) {res;}return res;}/*** 节点的状态值* 0 表示 无覆盖* 1 表示 有摄像头* 2 表示 有覆盖* 后序遍历根据左右节点的情况,来判读 自己的状态*/// 流程清晰版public int minCame(TreeNode root) {if (root null) {// 空节点默认为 有覆盖状态避免在叶子节点上放摄像头return 2;}int left minCame(root.left);int right minCame(root.right);//中逻辑处理// 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头if (left 2 right 2) {return 0;} else if (left 0 || right 0) {// 左右节点是无覆盖状态,那 根节点此时应该放一个摄像头res;return 1;} else {//左右节点至少存在 1个摄像头,那么本节点就是处于被覆盖状态return 2;}}// 简化分支版本public int minCame2(TreeNode root) {if (root null) {return 2;}int left minCame2(root.left);int right minCame2(root.right);// 有任意一个子节点为无覆盖就需要当前节点放相机if (left 0 || right 0) {res;return 1;}if (left 2 right 2) { // 左右子树都是有覆盖那么此时返回无覆盖return 0;}return 2; // 剩下情况就是左右子树有可能为 1 有摄像头即当前节点被监控}}
第三十一天的总算是结束了直冲Day32
