【算法刷题day37】Leetcode：738. 单调递增的数字、968. 监控二叉树

本文主要是介绍【算法刷题day37】Leetcode：738. 单调递增的数字、968. 监控二叉树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

草稿图网站
java的Deque

Leetcode 738. 单调递增的数字

题目：738. 单调递增的数字
解析：代码随想录解析

解题思路

这贪心有点巧，自己没想出来。从后往前遍历，如果遇到了比后面小的，就让当前数减一。遍历结束后，让修改的数字的后面所有都变成9

代码

class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] chars = s.toCharArray();int start = chars.length;for (int i = chars.length - 2; i >= 0; i--) {if (chars[i] > chars[i+1]) {chars[i]--;start = i+1;}}for (int i = start; i < chars.length; i++) {chars[i] = '9';}return Integer.parseInt(String.valueOf(chars));}
}

总结

暂无

Leetcode 968. 监控二叉树

题目：968. 监控二叉树
解析：代码随想录解析

解题思路

自己根本想不到，这题的贪心算法需要把问题抽象化。
把空节点当作已覆盖（2）。
如果左孩子、右孩子都为已覆盖（2），则当前节点为未覆盖（0）
如果左孩子或右孩子存在未覆盖（0），则当前节点加一个监控（1）
如果左孩子或右孩子有监控（1），则当前节点为已覆盖（2）

代码

/*** 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;*     }* }*/
class Solution {int res;public int minCameraCover(TreeNode root) {//0表示没覆盖//1表示安装监控//2表示被覆盖res = 0;if (traversal(root) == 0)res++;return res;}private int traversal(TreeNode node) {if (node == null)return 2;int left = traversal(node.left);int right = traversal(node.right);if (left == 2 && right == 2)return 0;if (left == 0 || right == 0){res++;return 1;}if (left == 1 || right == 1)return 2;return -1;}
}

总结

这篇关于【算法刷题day37】Leetcode：738. 单调递增的数字、968. 监控二叉树的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---