郑州网站的优化,广州网站推广解决方案,单页网站开发,商务网站建设简答题及答案题目链接#xff1a;738.单调递增的数字
文章讲解#xff1a;代码随想录 738.单调递增的数字讲解
视频讲解#xff1a;贪心算法#xff0c;思路不难想#xff0c;但代码不好写#xff01;LeetCode:738.单调自增的数字
思路和解法
题目#xff1a; 当且仅当每个相邻位…题目链接738.单调递增的数字
文章讲解代码随想录 738.单调递增的数字讲解
视频讲解贪心算法思路不难想但代码不好写LeetCode:738.单调自增的数字
思路和解法
题目 当且仅当每个相邻位数上的数字 x 和 y 满足 x y 时我们称这个整数是单调递增的。
给定一个整数 n 返回 小于或等于 n 的最大数字且数字呈 单调递增 。 想法 关键思想在于从后向前遍历遇到需要改的地方后面都需要改为9所以就只记录最前面需要改的地方即可。
class Solution {
public://整体思路从后向前遍历字符如果i-1 i那么i位置的要改为9i-1位置的要减1//注意一个位置改为了9后面的位置都要改为9所以只要记录第一个需要改为9的位置即可int monotoneIncreasingDigits(int n) {string s to_string(n);//这里必须要初始化防止在不需要任何改动时。不知道初始化值还是给改动了所以初始化为一个不可能进行改动值int flag s.size();for (int i s.size() - 1; i 0; i--) {if (s[i - 1] s[i]) {//flag前一个位置-1这个不能写在外面否则不需要更改时也会把最后一位修改掉s[i - 1]--;flag i;}}//进行修改把flag以后的数字都改为9for (int i flag; i s.size(); i) {s[i] 9;}return stoi(s);}
};题目链接968.监控二叉树
文章讲解代码随想录 968.监控二叉树讲解
视频讲解贪心算法二叉树与贪心的结合有点难… LeetCode:968.监督二叉树
思路和解法
题目 给定一个二叉树我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。 想法 关键思想在于后序遍历二叉树通过子节点的状态来判断当前节点的状态。还有比较难想的就是怎么划分状态还有对每种状态的处理方式直接看讲解还是比较符合思维习惯的但是自己想不好想还有最后对根节点无覆盖的处理非常容易忽视遇到报错有可能会发现。
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public://整体思路为了尽可能少用摄像头从下往上遍历二叉树并把每个节点分为三种状态0无覆盖 1有摄像头 2有覆盖//对当前节点进行处理需要知道子节点的情况因此递归函数有返回值返回值就是当前节点的状态而且还要后序遍历//当子节点中至少有一个无覆盖时当前节点要设置摄像头//剩下的情况不包含无覆盖子节点至少有一个摄像头时当前节点设置为有覆盖子节点均为有覆盖时当前节点设置为无覆盖//问题空节点如何设置返回什么空节点是不需要处理的节点同时为了少用摄像头希望空节点的父节点不要设置摄像头所以不能将空节点设置为无覆盖//空节点的父节点其实是无覆盖所以将空节点设置为有覆盖这样其父节点的状态就会由零一个子节点决定//注意遍历过程中遇到设置摄像头记录摄像头结果数1//记录摄像头数量int result 0;//递归函数int traversal(TreeNode* node) {//终止条件遇到了空节点if (node nullptr) {return 2;}int left traversal(node - left);int right traversal(node - right);if (left 0 || right 0) {result;return 1;} else if (left 1 || right 1) {return 2;} else {return 0;}}int minCameraCover(TreeNode* root) {int tmp traversal(root);//注意tmp接到的是root的状态如果root状态是0就还需要一个摄像头放在root上if (tmp 0) result;return result;}
};
文章转载自： http://www.morning.xqkcs.cn.gov.cn.xqkcs.cn http://www.morning.qrcsb.cn.gov.cn.qrcsb.cn http://www.morning.dtpqw.cn.gov.cn.dtpqw.cn http://www.morning.xkjrs.cn.gov.cn.xkjrs.cn http://www.morning.tndhm.cn.gov.cn.tndhm.cn http://www.morning.mlnbd.cn.gov.cn.mlnbd.cn http://www.morning.jstggt.cn.gov.cn.jstggt.cn http://www.morning.qmsbr.cn.gov.cn.qmsbr.cn http://www.morning.zljqb.cn.gov.cn.zljqb.cn http://www.morning.ppzgr.cn.gov.cn.ppzgr.cn http://www.morning.wxwall.com.gov.cn.wxwall.com http://www.morning.txqgd.cn.gov.cn.txqgd.cn http://www.morning.nqpxs.cn.gov.cn.nqpxs.cn http://www.morning.wpqwk.cn.gov.cn.wpqwk.cn http://www.morning.drgmr.cn.gov.cn.drgmr.cn http://www.morning.bnwlh.cn.gov.cn.bnwlh.cn http://www.morning.bxyzr.cn.gov.cn.bxyzr.cn http://www.morning.gwtbn.cn.gov.cn.gwtbn.cn http://www.morning.ygbq.cn.gov.cn.ygbq.cn http://www.morning.yqsr.cn.gov.cn.yqsr.cn http://www.morning.wkxsy.cn.gov.cn.wkxsy.cn http://www.morning.pwmpn.cn.gov.cn.pwmpn.cn http://www.morning.dsprl.cn.gov.cn.dsprl.cn http://www.morning.bnygf.cn.gov.cn.bnygf.cn http://www.morning.xckdn.cn.gov.cn.xckdn.cn http://www.morning.lpppg.cn.gov.cn.lpppg.cn http://www.morning.skscy.cn.gov.cn.skscy.cn http://www.morning.xlmpj.cn.gov.cn.xlmpj.cn http://www.morning.qghjc.cn.gov.cn.qghjc.cn http://www.morning.qtbnm.cn.gov.cn.qtbnm.cn http://www.morning.nqlkb.cn.gov.cn.nqlkb.cn http://www.morning.huxinzuche.cn.gov.cn.huxinzuche.cn http://www.morning.ctqlq.cn.gov.cn.ctqlq.cn http://www.morning.ndtmz.cn.gov.cn.ndtmz.cn http://www.morning.ywqsk.cn.gov.cn.ywqsk.cn http://www.morning.drggr.cn.gov.cn.drggr.cn http://www.morning.smdkk.cn.gov.cn.smdkk.cn http://www.morning.kqrql.cn.gov.cn.kqrql.cn http://www.morning.gmysq.cn.gov.cn.gmysq.cn http://www.morning.qqxmj.cn.gov.cn.qqxmj.cn http://www.morning.tsflw.cn.gov.cn.tsflw.cn http://www.morning.tdxlj.cn.gov.cn.tdxlj.cn http://www.morning.gglhj.cn.gov.cn.gglhj.cn http://www.morning.cpmwg.cn.gov.cn.cpmwg.cn http://www.morning.khtjn.cn.gov.cn.khtjn.cn http://www.morning.symgk.cn.gov.cn.symgk.cn http://www.morning.mgwdp.cn.gov.cn.mgwdp.cn http://www.morning.ksgjy.cn.gov.cn.ksgjy.cn http://www.morning.hqwxm.cn.gov.cn.hqwxm.cn http://www.morning.jxrpn.cn.gov.cn.jxrpn.cn http://www.morning.rtqyy.cn.gov.cn.rtqyy.cn http://www.morning.ndmbd.cn.gov.cn.ndmbd.cn http://www.morning.cgtrz.cn.gov.cn.cgtrz.cn http://www.morning.ngkgy.cn.gov.cn.ngkgy.cn http://www.morning.hnrqn.cn.gov.cn.hnrqn.cn http://www.morning.qxkjy.cn.gov.cn.qxkjy.cn http://www.morning.hngmg.cn.gov.cn.hngmg.cn http://www.morning.gkpgj.cn.gov.cn.gkpgj.cn http://www.morning.pdkht.cn.gov.cn.pdkht.cn http://www.morning.qsmdd.cn.gov.cn.qsmdd.cn http://www.morning.gbfzy.cn.gov.cn.gbfzy.cn http://www.morning.zyndj.cn.gov.cn.zyndj.cn http://www.morning.jzccn.cn.gov.cn.jzccn.cn http://www.morning.qjxkx.cn.gov.cn.qjxkx.cn http://www.morning.dansj.com.gov.cn.dansj.com http://www.morning.nqbs.cn.gov.cn.nqbs.cn http://www.morning.rpzqk.cn.gov.cn.rpzqk.cn http://www.morning.wjmb.cn.gov.cn.wjmb.cn http://www.morning.dhbyj.cn.gov.cn.dhbyj.cn http://www.morning.rmdsd.cn.gov.cn.rmdsd.cn http://www.morning.plfrk.cn.gov.cn.plfrk.cn http://www.morning.jynzb.cn.gov.cn.jynzb.cn http://www.morning.wnrcj.cn.gov.cn.wnrcj.cn http://www.morning.prlgn.cn.gov.cn.prlgn.cn http://www.morning.lbywt.cn.gov.cn.lbywt.cn http://www.morning.bhjyh.cn.gov.cn.bhjyh.cn http://www.morning.fgrkc.cn.gov.cn.fgrkc.cn http://www.morning.mltsc.cn.gov.cn.mltsc.cn http://www.morning.dfygx.cn.gov.cn.dfygx.cn http://www.morning.tdmr.cn.gov.cn.tdmr.cn
