推文最好的网站是哪个,世界500强企业招聘网站,页面简洁的网站,尚层装饰目录 738.单调递增的数字思路代码 968.监控二叉树思路代码 738.单调递增的数字 题目链接#xff1a;704. 二分查找 文档讲解#xff1a;代码随想录 视频讲解#xff1a;贪心算法#xff0c;思路不难想#xff0c;但代码不好写#xff01;LeetCode:738.单调自增的数字 思路… 目录 738.单调递增的数字思路代码 968.监控二叉树思路代码 738.单调递增的数字 题目链接704. 二分查找 文档讲解代码随想录 视频讲解贪心算法思路不难想但代码不好写LeetCode:738.单调自增的数字 思路
数要尽可能的大高位开始尽量不变从低位开始找到不满足递减的第一个位置当前位置减1后面的全都变成9即可。
代码
class Solution {
public:int monotoneIncreasingDigits(int n) {string strNum to_string(n);int idx;for (int i strNum.size() - 1; i 0; i--) {if (strNum[i - 1] strNum[i]) {strNum[i] 9;strNum[i - 1]--;}}return stoi(strNum);}
};968.监控二叉树 题目链接968.监控二叉树 文档讲解代码随想录 视频讲解贪心算法二叉树与贪心的结合有点难… LeetCode:968.监督二叉树 思路
很容易想到要从叶子结点的父节点开始每隔两个结点放一个摄像头为局部最优但是怎样表示一个结点的状态有摄像头没有摄像头但被摄像头覆盖没有摄像头也没有被摄像头覆盖是个难点。
后序遍历递归返回值选择int型返回0、1、2其中0表示没有摄像头也没有被摄像头覆盖1表示有摄像头2表示没有摄像头但被摄像头覆盖。
空结点处理
如果空结点是未被覆盖状态这时叶子结点就需要放摄像头不是局部最优如果空结点是有摄像头状态这时叶子结点被覆盖叶子结点的父节点不用放置摄像头而父节点的父节点放置摄像头这时叶子结点没有被覆盖如果空结点是被覆盖状态则叶子结点不用放置摄像头叶子结点的父节点放置摄像头即可是局部最优。
分四种情况
情况一左右结点都有覆盖这时当前结点不用放置摄像头当前节点的父结点放置摄像头返回0情况二左右结点至少有一个未被覆盖这时当前结点需要放置摄像头返回1情况三左右结点至少有一个摄像头且另一个结点被覆盖这时当前结点不需要放置摄像头且被左右结点覆盖返回2情况四如果递归完后根结点没有被覆盖则根结点也需要放置一个摄像头
代码
class Solution {
public:int minCameraCover(TreeNode *root) {// 情况4if (traversal(root) 0)// root无覆盖result;return result;}private:int result 0;int traversal(TreeNode *node) {// 空结点该结点有覆盖if (node NULL)return 2;int left traversal(node-left);int right traversal(node-right);// 情况1// 左右结点都有覆盖则该节点放置摄像头if (left 2 right 2)return 0;// 情况2// 左右结点至少有一个没有覆盖// left 0 right 0 左右节点无覆盖// left 1 right 0 左节点有摄像头右节点无覆盖// left 0 right 1 左节点有无覆盖右节点摄像头// left 0 right 2 左节点无覆盖右节点覆盖// left 2 right 0 左节点覆盖右节点无覆盖if (left 0 || right 0) {result;return 1;}// 情况3// left 1 right 2 左节点有摄像头右节点有覆盖// left 2 right 1 左节点有覆盖右节点有摄像头// left 1 right 1 左右节点都有摄像头// 其他情况前段代码均已覆盖if (left 1 || right 1)return 2;return -1;}
};
