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].
解题思路
先设置预定的区间，取第一个。
然后依次比较，更新区间即可。如果遇到起点比终点大的，则插入结果集合，并令匹配区间为当前区间。
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> ans = new ArrayList<>();
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int start = intervals[0][0], end = intervals[0][1];
for (int[] interval : intervals) {
if (interval[0] > end) {
ans.add(new int[]{start, end});
start = interval[0];
end = interval[1];
} else {
end = Math.max(interval[1], end);
start = Math.min(interval[0], start);
}
}
ans.add(new int[]{start, end});
return ans.toArray(new int[ans.size()][]);
}
}
738. 单调递增的数字
题目描述
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。
给定一个整数 n ，返回 小于或等于 n 的最大数字，且数字呈 单调递增 。
示例
输入: n = 332
输出: 299
解题思路
从后往前遍历，只要不满足单点递增，则将当前位数字减 1, 并令后续的均为 9
class Solution {
public int monotoneIncreasingDigits(int n) {
char[] ch = String.valueOf(n).toCharArray();
for (int i = ch.length - 1; i >= 0; i--) {
if (i < ch.length - 1 && ch[i] > ch[i + 1]) {
ch[i]--;
for (int j = i + 1; j < ch.length && ch[j] != '9'; j++) {
ch[j] = '9';
}
}
}
int ans = Integer.parseInt(new String(ch));
return ans;
}
}
968. 监控二叉树
题目描述
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例
输入：[0,0,null,0,0]
输出：1
解释：如图所示，一台摄像头足以监控所有节点。
解题思路
自底而上求，叶子结点不设置摄像头，在其根节点设置。当左右孩子均为覆盖状态，则在当前节点安装摄像头。
class Solution {
/*
val:
0: 没被监控
1: 安装监控
2: 能被监控
*/
int ans = 0;
public int minCameraCover(TreeNode root) {
// 对根节点的状态做检验,防止根节点是无覆盖状态
if (putCamera(root) == 0) {
ans++;
}
return ans;
}
public int putCamera(TreeNode root) {
// 叶子节点不放，但能覆盖。放在它的父节点上
if (root == null) {
return 2;
}
int left = putCamera(root.left);
int right = putCamera(root.right);
// 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头
if (left == 2 && right == 2) {
return 0;
} else if (left == 0 || right == 0) {
// 左右孩子有一个没被监控，在当前节点安监控
// (0,0) (0,1) (0,2) (1,0) (2,0)
ans++;
return 1;
} else {
// 左右孩子有一个安了摄像头，所以当前节点能被监控
// 左右节点的 状态为 (1,1) (1,2) (2,1)
return 2;
}
}
}
评论