Day27
贪心算法part05
LeetCode 56. 合并区间
题目描述
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
题目链接
https://leetcode.cn/problems/merge-intervals/
思路
和前面的题一样先排序, 依旧根据左边界升序。用now[2]表示当前的区间, 每次用当前遍历到的左边界和now[1](即当前区间的右边界)进行比较
- 小于等于右边界, 合并区间,
now[1] = Math.max(now[1], intervals[i][1]) - 大于右边界, 把
now数组存入result结果集, 并令now为当前遍历的区间
解决代码
class Solution {public int[][] merge(int[][] intervals) {List<int[]> result = new ArrayList<>();//按照左边界升序排序Arrays.sort(intervals, (a,b) ->{return a[0] - b[0];});int[] now = {intervals[0][0], intervals[0][1]};for (int i = 1; i < intervals.length; i++) {if (intervals[i][0] <= now[1]) {now[1] = Math.max(now[1], intervals[i][1]);}else{result.add(new int[]{now[0], now[1]});now[0] = intervals[i][0];now[1] = intervals[i][1];}}//处理末尾区间if (!result.contains(now)) {result.add(now);}return result.toArray(new int[result.size()][]);}
}
LeetCode 738.单调递增的数字
题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例
输入: n = 332
输出: 299
题目链接
https://leetcode.cn/problems/monotone-increasing-digits/description/
思路
首先为了方便操作需要将整型转换为字符串。从个位开始，如果上一位比当前位数的小，则上一位减一，当前位数变为9
注意：这里不能直接写
for (int i = ch.length - 1; i > 0; i--) {if (ch[i - 1] > ch[i]) {ch[i - 1]--;ch[i] = '9';}}
如果遇到两个数相同，例如100，则最后结果是90，因为个位的和十位相同，不会进入到if里。所以需要使用start记录开始置为9的起始下标, 然后再对字符串操作
解决代码
class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] ch = s.toCharArray();int start = s.length();//记录需要变为9的在字符串的下标起点for (int i = ch.length - 2; i >= 0; i--) {if (ch[i] > ch[i + 1]) {ch[i]--;start = i + 1;}}//转换为9for (int i = start; i < ch.length; i++) {ch[i] ='9';}//parseInt() 方法用于将字符串参数作为有符号的十进制整数进行解析//String.valueOf(paramType param); paramType可以是int, boolean, char, double, floatreturn Integer.parseInt(String.valueOf(ch));}
}
LeetCode 968.监控二叉树
题目描述
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例
输入：[0,0,null,0,null,0,null,null,0]
输出：2
解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
题目链接
https://leetcode.cn/problems/binary-tree-cameras/
思路
本题关键在于, 找到 叶子节点不放置摄像机 这个局部最优, 即从下往上遍历, 如果孩子节点没有覆盖到, 再给父节点放置摄像机
在实际中有四种可能
- 孩子节点有一个没被覆盖到
- 孩子节点有一个有摄像机
- 孩子节点均被覆盖到
- 根节点没有被覆盖到 (这一步比较难想到)
解决代码
class Solution {/* val值说明0 没有覆盖1 放置摄像头2 能够被监控到*/int result = 0;public int minCameraCover(TreeNode root) {/*后序遍历当前节点为叶子节点，不放置，并给父节点放摄像头*///根节点没被覆盖到，需要给根节点安放摄像机if (minCamera(root) == 0) {result++;}return result;}public int minCamera(TreeNode root) {if (root == null) {return 2;}int left = minCamera(root.left);int right = minCamera(root.right);//左右孩子有一个没被覆盖if (left == 0 || right == 0) {result++;return 1;}else if (left == 1 || right == 1) {//孩子中有一个有摄像机return 2;}else{//孩子中均被覆盖到return 0;}}}