当前位置: 首页 > 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 …...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

Appium+python自动化(十六)- ADB命令

简介 Android 调试桥(adb)是多种用途的工具&#xff0c;该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具&#xff0c;其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利&#xff0c;如安装和调试…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

3.3.1_1 检错编码(奇偶校验码)

从这节课开始&#xff0c;我们会探讨数据链路层的差错控制功能&#xff0c;差错控制功能的主要目标是要发现并且解决一个帧内部的位错误&#xff0c;我们需要使用特殊的编码技术去发现帧内部的位错误&#xff0c;当我们发现位错误之后&#xff0c;通常来说有两种解决方案。第一…...

如何将联系人从 iPhone 转移到 Android

从 iPhone 换到 Android 手机时&#xff0c;你可能需要保留重要的数据&#xff0c;例如通讯录。好在&#xff0c;将通讯录从 iPhone 转移到 Android 手机非常简单&#xff0c;你可以从本文中学习 6 种可靠的方法&#xff0c;确保随时保持连接&#xff0c;不错过任何信息。 第 1…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

Fabric V2.5 通用溯源系统——增加图片上传与下载功能

fabric-trace项目在发布一年后,部署量已突破1000次,为支持更多场景,现新增支持图片信息上链,本文对图片上传、下载功能代码进行梳理,包含智能合约、后端、前端部分。 一、智能合约修改 为了增加图片信息上链溯源,需要对底层数据结构进行修改,在此对智能合约中的农产品数…...

初探Service服务发现机制

1.Service简介 Service是将运行在一组Pod上的应用程序发布为网络服务的抽象方法。 主要功能&#xff1a;服务发现和负载均衡。 Service类型的包括ClusterIP类型、NodePort类型、LoadBalancer类型、ExternalName类型 2.Endpoints简介 Endpoints是一种Kubernetes资源&#xf…...

水泥厂自动化升级利器:Devicenet转Modbus rtu协议转换网关

在水泥厂的生产流程中&#xff0c;工业自动化网关起着至关重要的作用&#xff0c;尤其是JH-DVN-RTU疆鸿智能Devicenet转Modbus rtu协议转换网关&#xff0c;为水泥厂实现高效生产与精准控制提供了有力支持。 水泥厂设备众多&#xff0c;其中不少设备采用Devicenet协议。Devicen…...