本文主要是介绍代码随想录算法训练营第三十九天| 738.单调递增的数字 、968.监控二叉树、总结，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
738.单调递增的数字
题目链接：738.单调递增的数字
文档讲解：代码随想录/单调递增的数字
视频讲解：视频讲解-单调递增的数字
状态：已完成（1遍）
解题过程
看到题目的第一想法
这道题我的想法是从后往前遍历，如果此刻遍历的数字比前一位数字要小，那么此位数字及之后的位数的所有数字都得变成9，并且前一位数字要减一（如果是0那就也变9），至于再前一位不用管，遍历到前一位的时候会处理。
/*** @param {number} n* @return {number}*/
var monotoneIncreasingDigits = function(n) {let ans = n.toString().split('').map((num)=>Number(num));//Number--字符串--字符串数组--数组中每个字符串转换为Number方便运算for(let i = ans.length-1;i>0;i--){if(ans[i]<ans[i-1]){//只要出现一个位数的数字比前一位小，这一位和后面所有的都得变成9let index = i;while(index<ans.length){ans[index] = 9;index++;}//且前一位得减1ans[i-1] = ans[i-1] == 0?9:ans[i-1]-1;}}let outPut = Number(ans.map(String).join(''));//每一位Number的数组--字符串数组--单个字符串--Numberreturn outPut;
};提交没有问题。
看完代码随想录之后的想法
大体思路差不多，就是有一处可以优化，只用记住最靠前的比前一位小的数字所在的位数之后再开个for循环把这一位之后的所有数字都改成9就可以了。
讲解代码如下：
/*** @param {number} n* @return {number}*/
var monotoneIncreasingDigits = function(n) {n = n.toString()n = n.split('').map(item => {return +item})let flag = Infinityfor(let i = n.length - 1; i > 0; i--) {if(n [i - 1] > n[i]) {flag = in[i - 1] = n[i - 1] - 1n[i] = 9}}for(let i = flag; i < n.length; i++) {n[i] = 9}n = n.join('')return +n
};总结
感觉这道题相比于前面的抽象问题还是比较容易想到的，看三个例子就可以想出局部最优的思路。
968.监控二叉树
题目链接：968.监控二叉树
文档讲解：代码随想录/监控二叉树
视频讲解：视频讲解-监控二叉树
状态：已完成（1遍）
解题过程
看到题目的第一想法
这题我想不出来局部最优的思路。。感觉情况太多了，这题真挺复杂的感觉。（毕竟卡尔哥也说了一刷跳过）
看完代码随想录之后的想法
叶子结点不放摄像头，在叶子结点的父节点放摄像头。把握住这一个关键点就ok，这就是局部最优，再一步步往上遍历。
讲解代码如下：
/*** Definition for a binary tree node.* function TreeNode(val, left, right) {* this.val = (val===undefined ? 0 : val)* this.left = (left===undefined ? null : left)* this.right = (right===undefined ? null : right)* }*/
/*** @param {TreeNode} root* @return {number}*/
var minCameraCover = function(root) {let result = 0function traversal(cur) {if(cur === null) {return 2}let left = traversal(cur.left)let right = traversal(cur.right)if(left === 2 && right === 2) {return 0}if(left === 0 || right === 0) {result++return 1}if(left === 1 || right === 1) {return 2}return -1}if(traversal(root) === 0) {result++}return result};总结
采用后序遍历（左右中），因为要根据左右孩子的状态确定父节点是否放摄像头。
子节点的状态分为：0无摄像头也无摄像头覆盖覆盖、1有摄像头、2无摄像头但被摄像头覆盖。
贪心算法总结
文档讲解：代码随想录/贪心算法总结
总结
- 贪心的本质就是局部最优解推出全局最优解；
- 贪心无固定套路、固定框架；
这篇关于代码随想录算法训练营第三十九天| 738.单调递增的数字 、968.监控二叉树、总结的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
