738. 单调递增的数字
当且仅当每个相邻位数上的数字
x和y满足x <= y时，我们称这个整数是单调递增的。给定一个整数
n，返回 小于或等于n的最大数字，且数字呈 单调递增 。示例 1:
输入: n = 10 输出: 9示例 2:
输入: n = 1234 输出: 1234示例 3:
输入: n = 332 输出: 299提示:
0 <= n <= 109
状态：没做出来
思路：贪心思路就是如果前面的数比后面的数字大则把前面的数字减1然后把后面的数字变成9，这样子就可以了，但还有一个问题需要去注意的，就是遍历的顺序问题，如果采用从前到后则会导致值变小导致不符合要求，所以这题采用从后向前，但是从后向前还有一个需要注意的就是什么时候置9，要等所有结束遍历之后再置9，如果在循环中置9会导致有些值赋不上9，比如n=1000时就不行了，要等循环结束之后然后把flag以及后面都置为9。
class Solution {
public int monotoneIncreasingDigits(int n) {
String str=n+"";
char[] arr=str.toCharArray();
int flag=arr.length;
for(int i=arr.length-1;i>0;i--){
if(arr[i]<arr[i-1]){
flag=i;
arr[i-1]-=1;
}
}
for(int i=flag;i<arr.length;i++){
arr[i]='9';
}
return Integer.valueOf(new String(arr));
}
}968. 监控二叉树
给定一个二叉树，我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
示例 1：
输入：[0,0,null,0,0] 输出：1 解释：如图所示，一台摄像头足以监控所有节点。示例 2：
输入：[0,0,null,0,null,0,null,null,0] 输出：2 解释：需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。
提示：
- 给定树的节点数的范围是
[1, 1000]。- 每个节点的值都是 0。
状态：没做出来
思路：直接去看carl就ok了，这题确实巧妙。https://programmercarl.com/0968.%E7%9B%91%E6%8E%A7%E4%BA%8C%E5%8F%89%E6%A0%91.html#%E6%80%9D%E8%B7%AF
class Solution {
int result=0;
public int minCameraCover(TreeNode root) {
int temp = traversal(root);
if(temp==0){
result++;
}
return result;
}
public int traversal(TreeNode root){
/**
* 做一个状态转移 0表示无覆盖 1表示有摄像头 2表示有覆盖
* 贪心在于摄像头如果两个子节点都是有覆盖的那我们才添加摄像头，这样子减少摄像头数量的贪心
*/
if(root==null) return 2;//到空节点的时候需要让父节点添加摄像机
int left=traversal(root.left);
int right=traversal(root.right);
if(left==2&&right==2){
return 0;
}else if(left==0||right==0){
result++;
return 1;
}else if(left==1||right==1){
return 2;
}
return -1;
}
}感想：今天完成贪心的所有内容，明天开始动态规划，keep going on。
