题目一:单调递增的数字
题目描述:
给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。
思路分析:
贪心算法,从高位到低位考虑,如果当前位的数比前一位小,则将前一位减1,同时将后续所有位都变为9,因为后续所有位变为9可以保证数值最大。如果当前位的数比前一位大,则继续向后考虑。
Java代码实现:
```java
class Solution {
public int monotoneIncreasingDigits(int N) {
char[] nums = Integer.toString(N).toCharArray();
int len = nums.length;
int flag = len;
for (int i = len - 1; i > 0; i--) {
if (nums[i] < nums[i - 1]) {
nums[i - 1]--;
flag = i;
}
}
for (int i = flag; i < len; i++) {
nums[i] = '9';
}
return Integer.parseInt(new String(nums));
}
}
```
题目二:监控二叉树
题目描述:
给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。
思路分析:
贪心算法,考虑从叶子节点开始,如果叶子节点的父节点没有被监控,则该叶子节点必须安装摄像头,然后向上递归。如果叶子节点的父节点已经被监控,则该叶子节点不必安装摄像头,向上递归即可。最终的答案为根节点的状态,即根节点是否被监控。
Java代码实现:
```java
class Solution {
int res = 0;
public int minCameraCover(TreeNode root) {
if (dfs(root) == 0) {
res++;
}
return res;
}
private int dfs(TreeNode node) {
if (node == null) {
return 2;
}
int left = dfs(node.left);
int right = dfs(node.right);
if (left == 0 || right == 0) {
res++;
return 1;
} else if (left == 1 || right == 1) {
return 2;
} else {
return 0;
}
}
}
```
技术总结:
贪心算法是一种求解最优化问题的一种方法,它的基本思路是每一步选择最优的解,最终得到全局最优解。贪心算法的优点在于简单、高效,但是它的缺点也很明显,就是无法保证得到全局最优解,有可能会得到局部最优解。
在解决题目时,我们需要仔细分析问题,确定问题的贪心策略,并证明该策略是正确的,然后再根据该策略进行编码实现。在实现过程中,我们需要注意代码的细节,确保程序的正确性和效率。