当前位置：首页 > news >正文

代码随想录算法训练营第三十七天 | 56. 合并区间、738.单调递增的数字、968.监控二叉树、总结

news 来源：原创 2024/9/22 1:08:06

56. 合并区间

题目链接：https://leetcode.cn/problems/merge-intervals/
文档讲解：https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
视频讲解：https://www.bilibili.com/video/BV1wx4y157nD

思路

将当前区间跟结果集中的最后一个区间比较。

代码

class Solution {public int[][] merge(int[][] intervals) {if (intervals.length == 0) return intervals;List<int[]> list = new ArrayList<>();Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));list.add(intervals[0]); // 先把第一个区间放进去for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] <= list.getLast()[1]) {int start = list.getLast()[0];int end = Math.max(list.getLast()[1], intervals[i][1]);list.removeLast();list.add(new int[]{start, end});} else list.add(intervals[i]);}return list.toArray(new int[list.size()][]);}
}

分析：时间复杂度：O(nlogn)，空间复杂度：O(n)。

738.单调递增的数字

题目链接：https://leetcode.cn/problems/monotone-increasing-digits/
文档讲解：https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5…
视频讲解：https://www.bilibili.com/video/BV1Kv4y1x7tP

思路

当遇到前一位比后一位小的时候，将前一位减一，后一位取最大值9。从后往前遍历。
比如：332中先比较32，变为329，接着处理前面的32，变为299。
定义一个参数flag，用于记录从哪个数开始后面都置为9。如果遇到前一位比后一位小的情况就直接变成9，那么在处理1000的时候，就会处理成900，而不是999。

代码

class Solution {public int monotoneIncreasingDigits(int n) {String s = Integer.toString(n); // 先转换为Stringint flag = s.length();char[] c = s.toCharArray(); // 由于String中的值不能改，所以再转换为char数组for (int i = s.length() - 1; i > 0; i--) {if (c[i - 1] > c[i]) {c[i - 1] -= 1;flag = i;}}for (int i = flag; i < s.length(); i++) {c[i] = '9';}return Integer.parseInt(String.valueOf(c)); // 先转换为String，然后转为int}
}

分析：时间复杂度：O(n)，空间复杂度：O(n)。

968.监控二叉树

题目链接：https://leetcode.cn/problems/binary-tree-cameras/
文档讲解：https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
视频讲解：https://www.bilibili.com/video/BV1SA411U75i

思路

二叉树叶子结点众多，所以我们要在叶子结点节约摄像头，即优先从叶子结点的父节点放摄像头，然后往上推。
使用后序遍历，往上传递摄像头数量。
定义节点的三个状态。0：无覆盖。1：有摄像头。2：有覆盖。遇到空节点返回状态2。
四种情况：1、左右孩子都有覆盖，则父节点无覆盖。2、左右孩子至少有一个无覆盖，则父节点为摄像头。3、左右孩子至少有一个有摄像头，则父节点有覆盖。4、最后遍历完根节点无覆盖，则给根节点加摄像头。

代码

class Solution {int res = 0;public int minCameraCover(TreeNode root) {if (traversal(root) == 0) { // 情况4、最后遍历完根节点无覆盖，则给根节点加摄像头res++;}return res;}public int traversal(TreeNode node) {// 三个状态：0：无覆盖 1：有摄像头 2：有覆盖 if (node == null) return 2; // 给空节点状态置为2int left = traversal(node.left); // 左int right = traversal(node.right); // 右// 中if (left == 2 && right == 2) { // 情况1、左右孩子都有覆盖，则父节点无覆盖return 0;}if (left == 0 || right == 0) { // 情况2、左右孩子至少有一个无覆盖，则父节点为摄像头res++;return 1;}if (left == 1 || right == 1) { // 情况3、左右孩子至少有一个有摄像头，则父节点有覆盖return 2;}return -1; // 随便返回，实际不会走到这里来}
}