day37 ● 738.单调递增的数字 ● 968.监控二叉树

题目一:单调递增的数字

题目描述:

给定一个非负整数 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;

        }

    }

}

```

技术总结:

贪心算法是一种求解最优化问题的一种方法,它的基本思路是每一步选择最优的解,最终得到全局最优解。贪心算法的优点在于简单、高效,但是它的缺点也很明显,就是无法保证得到全局最优解,有可能会得到局部最优解。

在解决题目时,我们需要仔细分析问题,确定问题的贪心策略,并证明该策略是正确的,然后再根据该策略进行编码实现。在实现过程中,我们需要注意代码的细节,确保程序的正确性和效率。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容