56. 合并区间
区间这类问题,不是按照左端点排序就是按照右端点排序,在思考思路的时候,就从这两个方向去下手,然后再去想贪心,以及从左侧开始遍历还是右侧开始遍历。
class Solution {
public int[][] merge(int[][] intervals) {
if(intervals.length == 1) return intervals;
Arrays.sort(intervals, (a, b)->Integer.compare(a[0], b[0]));
int[] pre = intervals[0];
List<int[]> listAns = new ArrayList();
for(int i = 1; i < intervals.length;i ++){
if(intervals[i][0] <= pre[1]) {
pre[1] = Math.max(pre[1], intervals[i][1]);
}
else {
listAns.add(pre);
pre = intervals[i];
}
if(i==intervals.length-1) listAns.add(pre);
}
return listAns.toArray(new int[listAns.size()][]);
}
}
738. 单调递增的数字
思路想到了,但就是做不出来,我是真蠢啊,继续加油吧,可能努力到最后我还是一样笨,但我一定还是不会放弃。
从后向前遍历,遇到后小于前的数字,前面的数字减一(其实就是这里我怎么也绕不过来,一直都在思考,万一是0怎么办,那这里怎么操作,但其实完全不用考虑,即便减成-1,那他一定小于前一个数字,那么这一位也是需要变成9的)。使用start记录第一位要变成9的位置,如果该位置变成9,后面所有位都要变成9。因此,只记录第一位就行。
class Solution {
public int monotoneIncreasingDigits(int n) {
char[] chrs = Integer.valueOf(n).toString().toCharArray();
int start = -1;
for(int i = chrs.length - 1; i > 0; i--){
if(chrs[i] < chrs[i-1]) {
chrs[i-1]--;
start = i;
}
}
if(start == -1) return n;
for(int i = start; i < chrs.length; i++){
chrs[i] = '9';
}
return Integer.valueOf(new String(chrs));
}
}
968. 监控二叉树
这道题更是重量级,根本不会一点。让我背背思路还差不多。贴下题解。讲的不错,但我想不到。后序遍历+贪心。
贪心的思路,从下到上,如果是叶子节点则不安装摄像头,因为只能覆盖自己和上一层,而如果安装在非叶子节点,则可以向上向下都覆盖到。
这道题还有一个非常巧妙的思路就是在于对节点的标识,使用0,1,2分别代表未覆盖,有摄像头以及已覆盖。这个想不到是真做不出来,然后经过这样标识后,根据左右子树的标识再反推根节点的标识。这里还有一个小的点,对于空节点,使用已覆盖来标识,这部分我只能意会了,具体还是看代码随想录的题解,讲的很清楚。
class Solution {
int res;
public int minCameraCover(TreeNode root) {//0,1,2分别代表未覆盖,有摄像头以及已覆盖
int stat = traversal(root);
if(stat == 0) res++;
return res;
}
public int traversal(TreeNode root){
if(root == null) return 2;
int left = traversal(root.left);
int right = traversal(root.right);
if(left == 0 || right == 0){ res++; return 1; }
if(left == 1 || right == 1) { return 2; }
return 0;
}
}
标签:return,int,31,Part05,start,intervals,chrs,root,Day
From: https://www.cnblogs.com/12sleep/p/18338540