当前位置: 首页 > news >正文

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

题目链接:738.单调递增的数字

文章讲解:代码随想录 738.单调递增的数字讲解

视频讲解:贪心算法,思路不难想,但代码不好写!LeetCode:738.单调自增的数字

思路和解法

题目:
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。
想法:
关键思想在于从后向前遍历,遇到需要改的地方后面都需要改为9,所以就只记录最前面需要改的地方即可。

class Solution {
public://整体思路:从后向前遍历字符,如果i-1 < i那么i位置的要改为9,i-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;}
};

相关文章:

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

题目链接&#xff1a;738.单调递增的数字 文章讲解&#xff1a;代码随想录 738.单调递增的数字讲解 视频讲解&#xff1a;贪心算法&#xff0c;思路不难想&#xff0c;但代码不好写&#xff01;LeetCode:738.单调自增的数字 思路和解法 题目&#xff1a; 当且仅当每个相邻位…...

【Django-ninja】django-ninja的hello world

django-ninja简介 Django Ninja是一个用于使用Django和Python 3.6类型提示构建API的Web框架。 主要特点&#xff1a; 易用性&#xff1a;旨在易于使用和直观。 高性能执行&#xff1a;由于Pydantic和异步支持&#xff0c;具有非常高的性能。 编码效率高&#xff1a;类型提…...

ArrayList集合初始化长度是多少,初始化的时候分配内存空间吗

ArrayList一旦初始化&#xff0c;在内存中就会分配空间吗 是的&#xff0c;当ArrayList在Java中初始化时&#xff0c;即使它没有添加任何元素&#xff0c;也会立即分配内存空间。具体来说&#xff0c;对于默认构造函数创建的ArrayList&#xff08;即不指定初始容量&#xff09…...

C语言数组:从入门到进阶

前言&#xff1a; 在这篇博客中&#xff0c;我们将学习如何使用C语言数组的基本知识。数组是C语言中的一种重要数据结构&#xff0c;它允许我们存储一系列相同类型的数据。我们将讨论数组的定义、初始化、访问元素、遍历数组以及数组的应用场景。此外&#xff0c;我们还将通过…...

9.回文数

回文数 将整型转换为字符型反转前一半是否等于后一半将数字本身反转输入一个整数 x,如果 x是一个回文整数,返回 true;否则,返回 false 。 回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 例如,121 是回文,而 123 不是。 将整型转换为字符型 反转…...

一分钟在SpringBoot项目中使用EMQ

先展示最终的结果: 生产者端: RestController RequiredArgsConstructor public class TestController {private final MqttProducer mqttProducer;GetMapping("/test")public String test() {User build User.builder().age(100).sex(1).address("世界潍坊渤…...

SOME/IP 协议介绍(七)传输 CAN 和 FlexRay 帧

SOME/IP 不应仅用于传输 CAN 或 FlexRay 帧。但是&#xff0c;消息 ID 空间需要在两种用例之间进行协调。 传输 CAN/FlexRay 应使用完整的 SOME/IP 标头。 AUTOSAR Socket-Adapter 使用消息 ID 和长度来构建所需的内部 PDU&#xff0c;但不会查看其他字段。因此&#xff0c;必…...

与数组相关经典面试题

&#x1d649;&#x1d65e;&#x1d658;&#x1d65a;!!&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦&#x1f44f;&#x1f3fb;‧✧̣̥̇‧✦ &#x1f44f;&#x1f3fb;‧✧̣̥̇:Solitary-walk ⸝⋆ ━━━┓ - 个性标签 - &#xff1a;来于“云”的“羽球人”。…...

数据结构与算法面试系列-02

1. 一个整数,它加上100后是一个完全平方数,加上168又是一个完全平方数,请问该数是多少? 程序分析:在10万以内判断,先将该数加上100后再开方,再将该数加上168后再开方,如果开方后的结果满足如下条件,即是结果。请看具体分析: 程序代码如下: package com.yoodb.uti…...

CMake 完整入门教程(五)

CMake 使用实例 13.1 例子一 一个经典的 C 程序&#xff0c;如何用 cmake 来进行构建程序呢&#xff1f; //main.c #include <stdio.h> int main() { printf("Hello World!/n"); return 0; } 编写一个 CMakeList.txt 文件 ( 可看做 cmake 的…...

pgsql中with子句和直接查询差别

1、代码的可读性和维护性&#xff1a; 当查询较为复杂时&#xff0c;WITH子句可以将复杂的查询分解成多个简单的步骤&#xff0c;每个步骤都可以有一个易于理解的名字。这样做提高了代码的可读性&#xff0c;也便于后期维护。 2、代码的重用性&#xff1a; 在WITH子句中定义…...

Day 31 | 贪心算法 理论基础 、455.分发饼干 、 376. 摆动序列 、 53. 最大子序和

理论基础 文章讲解 455.分发饼干 题目 文章讲解 视频讲解 思路&#xff1a;从小饼干开始喂小胃口 class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int start 0;int count 0;for (int i 0; i < s.length &&a…...

vue3使用is动态切换组件报错Vue received a Component which was made a reactive object.

vue3使用is动态切换组件&#xff0c;activeComponent用ref定义报错 Vue received a Component which was made a reactive object. This can lead to unnecessary performance overhead, and should be avoided by marking the component with markRaw or using shallowRef ins…...

React16源码: React中LegacyContext的源码实现

LegacyContext 老的 contextAPI 也就是我们使用 childContextTypes 这种声明方式来从父节点为它的子树提供 context 内容的这么一种方式遗留的contextAPI 在 react 17 被彻底移除了&#xff0c;就无法使用了那么为什么要彻底移除这个contextAPI的使用方式呢&#xff1f;因为它…...

Gin 框架之jwt 介绍与基本使用

文章目录 一.JWT 介绍二.JWT认证与session认证的区别2.1 基于session认证流程图2.2 基于jwt认证流程图 三. JWT 的构成3.1 header : 头部3.2 payload : 负载3.2.1 标准中注册的声明 (建议但不强制使用)3.2.2 公共的声明3.2.3 私有的声明3.2.4 定义一个payload 3.3 signatrue : …...

从[redis:LinkedList]中学习链表

文章目录 adlistlistNodelistmacros[宏定义]listCreatelistInitNodelistEmptylistReleaselistAddNodeHeadlistLinkNodeHeadlistAddNodeTaillistLinkNodeTaillistInsertNodelistDelNodelistUlinkNodelistIndexredis3.2.100quicklistredis7.2.2quicklist redis的基本数据类型之一…...

Prometheus+grafana配置监控系统

使用docker compose安装 方便拓展, 配置信息都放在在 /docker/prometheus 目录下 1.目录结构如下 . ├── conf │ └── prometheus.yml ├── grafana_data ├── prometheus_data └── prometheus_grafana.yaml2.创建目录文件 mkdir /docker/prometheus &&am…...

Linux之安装配置CentOS 7

一、CentOS简介 CentOS&#xff08;Community Enterprise Operating System&#xff0c;中文意思是社区企业操作系统&#xff09;是Linux发行版之一&#xff0c;它是来自于Red Hat Enterprise Linux依照开放源代码规定释出的源代码所编译而成。由于出自同样的源代码&#xff0c…...

神经网络与深度学习Pytorch版 Softmax回归 笔记

Softmax回归 目录 Softmax回归 1. 独热编码 2. Softmax回归的网络架构是一个单层的全连接神经网络。 3. Softmax回归模型概述及其在多分类问题中的应用 4. Softmax运算在多分类问题中的应用及其数学原理 5. 小批量样本分类的矢量计算表达式 6. 交叉熵损失函数 7. 模型预…...

git学习及简单maven打包

前提&#xff1a; 已经有远程仓库地址 和账号密码了 已经安装git了 1.本地新建文件夹A用作本地仓库 2.在A文件夹下右键打开GIT BASH HERE 3.创建用户和密码&#xff0c;方便追踪提交记录 git config --global user.email “caoqingqing0108” //创建邮箱 git config --global …...

<6>-MySQL表的增删查改

目录 一&#xff0c;create&#xff08;创建表&#xff09; 二&#xff0c;retrieve&#xff08;查询表&#xff09; 1&#xff0c;select列 2&#xff0c;where条件 三&#xff0c;update&#xff08;更新表&#xff09; 四&#xff0c;delete&#xff08;删除表&#xf…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

【ROS】Nav2源码之nav2_behavior_tree-行为树节点列表

1、行为树节点分类 在 Nav2(Navigation2)的行为树框架中,行为树节点插件按照功能分为 Action(动作节点)、Condition(条件节点)、Control(控制节点) 和 Decorator(装饰节点) 四类。 1.1 动作节点 Action 执行具体的机器人操作或任务,直接与硬件、传感器或外部系统…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

听写流程自动化实践,轻量级教育辅助

随着智能教育工具的发展&#xff0c;越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式&#xff0c;也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建&#xff0c;…...

2025季度云服务器排行榜

在全球云服务器市场&#xff0c;各厂商的排名和地位并非一成不变&#xff0c;而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势&#xff0c;对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析&#xff1a; 一、全球“三巨头”…...

纯 Java 项目(非 SpringBoot)集成 Mybatis-Plus 和 Mybatis-Plus-Join

纯 Java 项目&#xff08;非 SpringBoot&#xff09;集成 Mybatis-Plus 和 Mybatis-Plus-Join 1、依赖1.1、依赖版本1.2、pom.xml 2、代码2.1、SqlSession 构造器2.2、MybatisPlus代码生成器2.3、获取 config.yml 配置2.3.1、config.yml2.3.2、项目配置类 2.4、ftl 模板2.4.1、…...

Spring AI Chat Memory 实战指南:Local 与 JDBC 存储集成

一个面向 Java 开发者的 Sring-Ai 示例工程项目&#xff0c;该项目是一个 Spring AI 快速入门的样例工程项目&#xff0c;旨在通过一些小的案例展示 Spring AI 框架的核心功能和使用方法。 项目采用模块化设计&#xff0c;每个模块都专注于特定的功能领域&#xff0c;便于学习和…...