第八章 贪心算法 part05
56. 合并区间
本题也是重叠区间问题，如果昨天三道都吸收的话，本题就容易理解了。
https://programmercarl.com/0056.%E5%90%88%E5%B9%B6%E5%8C%BA%E9%97%B4.html
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> list = new LinkedList<>();
int left = Integer.MAX_VALUE;
int right = 0;
for(int i = 1; i < intervals.length; i ++){
if(intervals[i][0] <= intervals[i - 1][1]){
left = Math.min(intervals[i - 1][0], left);
right = intervals[i][1];
}else{
int[] temp = new int[2];
temp[0] = left;
temp[1] = right;
list.add(temp);
left = intervals[i][0];
}
}
return list.toArray(new int[list.size()][]);
}
}
[[1,3],[2,6],[8,10],[15,18]]
输出
[[1,6],[8,6]]
预期结果
[[1,6],[8,10],[15,18]]
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][];
// 先按每个区间的起始点排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> list = new LinkedList<>();
// 初始化第一个区间
int left = intervals[0][0];
int right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= right) { // 如果当前区间的起点在上一个区间的终点之前，说明重叠
left = Math.min(intervals[i - 1][0], left);
right = Math.max(right, intervals[i][1]); // 更新右边界
} else {
list.add(new int[]{left, right}); // 添加上一个区间到结果列表
left = intervals[i][0]; // 更新左边界为当前区间的起点
right = intervals[i][1]; // 更新右边界为当前区间的终点
}
}
// 添加最后一个区间
list.add(new int[]{left, right});
return list.toArray(new int[list.size()][]);
}
}
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> list = new LinkedList<>();
int left = intervals[0][0];
int right = intervals[0][1];
for(int i = 1; i < intervals.length; i ++){
if(intervals[i][0] <= intervals[i - 1][1]){
left = Math.min(intervals[i - 1][0], left);
right = Math.max(intervals[i][1], right);
}else{
int[] temp = new int[2];
temp[0] = left;
temp[1] = right;
list.add(temp);
left = intervals[i][0];
right = intervals[i][1];
}
}
int[] temp = new int[2];
temp[0] = left;
temp[1] = right;
list.add(temp);
return list.toArray(new int[list.size()][]);
}
}
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
class Solution {
public int[][] merge(int[][] intervals) {
if (intervals.length == 0) return new int[0][];
// 先按每个区间的起始点排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
List<int[]> list = new LinkedList<>();
// 初始化第一个区间
int left = intervals[0][0];
int right = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] <= right) { // 如果当前区间的起点在上一个区间的终点之前，说明重叠
right = Math.max(right, intervals[i][1]); // 更新右边界
} else {
list.add(new int[]{left, right}); // 添加上一个区间到结果列表
left = intervals[i][0]; // 更新左边界为当前区间的起点
right = intervals[i][1]; // 更新右边界为当前区间的终点
}
}
// 添加最后一个区间
list.add(new int[]{left, right});
return list.toArray(new int[list.size()][]);
}
}
738.单调递增的数字
https://programmercarl.com/0738.%E5%8D%95%E8%B0%83%E9%80%92%E5%A2%9E%E7%9A%84%E6%95%B0%E5%AD%97.html
class Solution {
public int monotoneIncreasingDigits(int n) {
String s = n.toString();
int flag = s.length();
for(int i = s.length() - 1; i >= 0; i --){
if(s.charAt(i) < s.charAt(i -1)){
int a = (Integer)s.charAt(i -1);
a --;
s.charAt(i - 1) = (Char)a;
flag = i;
}
}
for(int i = flag; i < s.length(); i ++){
s.charAt(i) = '9';
}
return Integer.valueOf(s);
}
}
报错：
Line 3: error: int cannot be dereferenced
String s = n.toString();
Line 7: error: incompatible types: char cannot be converted to Integer
int a = (Integer)s.charAt(i -1);
Line 9: error: unexpected type
s.charAt(i - 1) = (Char)a;
class Solution {
public int monotoneIncreasingDigits(int n) {
// 将整数 n 转换为字符串
String s = String.valueOf(n);
// 将字符串转换为字符数组，方便修改
char[] charArray = s.toCharArray();
int flag = charArray.length;
// 从右向左遍历字符串
for (int i = charArray.length - 1; i > 0; i--) {
// 如果当前字符小于前一个字符
if (charArray[i] < charArray[i - 1]) {
// 将前一个字符减 1
charArray[i - 1]--;
// 记录需要修改为 '9' 的起始位置
flag = i;
}
}
// 将 flag 之后的所有字符修改为 '9'
for (int i = flag; i < charArray.length; i++) {
charArray[i] = '9';
}
// 将修改后的字符数组转换为整数并返回
return Integer.parseInt(new String(charArray));
}
}
968.监控二叉树 （可跳过）
本题是贪心和二叉树的一个结合，比较难，一刷大家就跳过吧。
https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html
总结
class Solution {
public int minCameraCover(TreeNode root) {
int result = 0;
if(camera(root, result) == 0) result ++;
return result;
}
public int camera(TreeNode root, int result){
if(root == null) return 2;
int left = camera(root.left, result);
int right = camera(root.right, result);
if(left == 2 && right == 2) return 0;
if(left == 1 || right == 1) return 2;
if(left == 0 || right == 0) {
result ++;
return 1;
}
return -1;
}
result 位置
class Solution {
int result = 0;
public int minCameraCover(TreeNode root) {
if(camera(root) == 0) result ++;
return result;
}
public int camera(TreeNode root){
if(root == null) return 2;
int left = camera(root.left);
int right = camera(root.right);
if(left == 2 && right == 2) return 0;
if(left == 1 || right == 1) return 2;
if(left == 0 || right == 0) {
result ++;
return 1;
}
return -1;
}
}
解答错误
126 / 171 个通过的测试用例
root =[0,0,0,null,null,null,0] 输出 1 预期结果 2
总结
class Solution {
int result = 0;
public int minCameraCover(TreeNode root) {
if(camera(root) == 0) result ++;
return result;
}
public int camera(TreeNode root){
if(root == null) return 2;
int left = camera(root.left);
int right = camera(root.right);
if(left == 2 && right == 2) return 0;
if(left == 0 || right == 0) {
result ++;
return 1;
}
if(left == 1 || right == 1) return 2;
return -1;
}
}
顺序！
可以看看贪心算法的总结，贪心本来就没啥规律，能写出个总结篇真的不容易了。
https://programmercarl.com/%E8%B4%AA%E5%BF%83%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93%E7%AF%87.html
