【贪心算法5】
力扣738.单调递增的数字
链接: link
思路
遇到c[i]>c[i+1]则c[i]–,然后就是给c[i+1]赋值‘9’;需要注意的是star初值问题,可见注释部分。
class Solution {
public int monotoneIncreasingDigits(int n) {
String s = String.valueOf(n);
char[] c = s.toCharArray();
int star = c.length; // 这里初始化必须是c.length,不能为0,因为遇到1234这个测例会出问题
for (int i = c.length - 2; i >= 0; i--) {
if (c[i] > c[i + 1]) {
c[i]--;
star = i+1; // 记录下一位起始位置
}
}
for(int i = star;i<c.length;i++){
c[i] = '9';
}
return Integer.parseInt(String.valueOf(c));
}
}
相似题型
思路
设计初衷:叶子节点不放摄像头,让其父节点放
三种状态0-无覆盖;1-有摄像头;2-有覆盖;
注意考虑null节点的状态
详细思路
968.监控二叉树
链接: link
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
/*
* 0-无覆盖
* 1-有摄像头
* 2-有覆盖
*/
class Solution {
int res = 0;
public int minCameraCover(TreeNode root) {
if (afterorder(root) == 0) {
res++;
}
return res;
}
public int afterorder(TreeNode root) {
if (root == null) {
return 2;
}
// 左
int left = afterorder(root.left);
int right = afterorder(root.right);
// 如果左右节点都覆盖了的话, 中间节点就该为无覆盖
if (left == 2 && right == 2) {
return 0;
} else if (left == 0 || right == 0) {
// 左右节点都是无覆盖状态,中间节点为有摄像头
res++;
return 1;
} else {
// 左右节点至少有一个摄像头,中间节点有覆盖
return 2;
}
}
}