代码随想录算法训练营第三十七天|738.单调递增的数字,968.监控二叉树

本文主要是介绍代码随想录算法训练营第三十七天|738.单调递增的数字,968.监控二叉树,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

目录

  • 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型,返回012,其中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;}
};

这篇关于代码随想录算法训练营第三十七天|738.单调递增的数字,968.监控二叉树的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/936770

相关文章

Java的栈与队列实现代码解析

《Java的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

Python实现特殊字符判断并去掉非字母和数字的特殊字符

《Python实现特殊字符判断并去掉非字母和数字的特殊字符》在Python中,可以通过多种方法来判断字符串中是否包含非字母、数字的特殊字符,并将这些特殊字符去掉,本文为大家整理了一些常用的,希望对大家... 目录1. 使用正则表达式判断字符串中是否包含特殊字符去掉字符串中的特殊字符2. 使用 str.isa

使用Java将DOCX文档解析为Markdown文档的代码实现

《使用Java将DOCX文档解析为Markdown文档的代码实现》在现代文档处理中,Markdown(MD)因其简洁的语法和良好的可读性,逐渐成为开发者、技术写作者和内容创作者的首选格式,然而,许多文... 目录引言1. 工具和库介绍2. 安装依赖库3. 使用Apache POI解析DOCX文档4. 将解析

C++使用printf语句实现进制转换的示例代码

《C++使用printf语句实现进制转换的示例代码》在C语言中,printf函数可以直接实现部分进制转换功能,通过格式说明符(formatspecifier)快速输出不同进制的数值,下面给大家分享C+... 目录一、printf 原生支持的进制转换1. 十进制、八进制、十六进制转换2. 显示进制前缀3. 指

openCV中KNN算法的实现

《openCV中KNN算法的实现》KNN算法是一种简单且常用的分类算法,本文主要介绍了openCV中KNN算法的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的... 目录KNN算法流程使用OpenCV实现KNNOpenCV 是一个开源的跨平台计算机视觉库,它提供了各

使用Python实现全能手机虚拟键盘的示例代码

《使用Python实现全能手机虚拟键盘的示例代码》在数字化办公时代,你是否遇到过这样的场景:会议室投影电脑突然键盘失灵、躺在沙发上想远程控制书房电脑、或者需要给长辈远程协助操作?今天我要分享的Pyth... 目录一、项目概述:不止于键盘的远程控制方案1.1 创新价值1.2 技术栈全景二、需求实现步骤一、需求

Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码

《Java中Date、LocalDate、LocalDateTime、LocalTime、时间戳之间的相互转换代码》:本文主要介绍Java中日期时间转换的多种方法,包括将Date转换为LocalD... 目录一、Date转LocalDateTime二、Date转LocalDate三、LocalDateTim

jupyter代码块没有运行图标的解决方案

《jupyter代码块没有运行图标的解决方案》:本文主要介绍jupyter代码块没有运行图标的解决方案,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录jupyter代码块没有运行图标的解决1.找到Jupyter notebook的系统配置文件2.这时候一般会搜索到

Python通过模块化开发优化代码的技巧分享

《Python通过模块化开发优化代码的技巧分享》模块化开发就是把代码拆成一个个“零件”,该封装封装,该拆分拆分,下面小编就来和大家简单聊聊python如何用模块化开发进行代码优化吧... 目录什么是模块化开发如何拆分代码改进版:拆分成模块让模块更强大:使用 __init__.py你一定会遇到的问题模www.

AJAX请求上传下载进度监控实现方式

《AJAX请求上传下载进度监控实现方式》在日常Web开发中,AJAX(AsynchronousJavaScriptandXML)被广泛用于异步请求数据,而无需刷新整个页面,:本文主要介绍AJAX请... 目录1. 前言2. 基于XMLHttpRequest的进度监控2.1 基础版文件上传监控2.2 增强版多