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

代码随想录算法训练营第37天|● 738.单调递增的数字 ● 968.监控二叉树 ● 总结

738. 单调递增的数字

中等
相关标签
相关企业
提示
当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。
给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。

示例 1:
输入: n = 10输出: 9
示例 2:
输入: n = 1234输出: 1234
示例 3:
输入: n = 332输出: 299

提示:

  • 0 <= n <= 10(9)

思路

  • 从后往前遍历
  • 一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]–,然后strNum[i]给为9,这样这个整数就是89,即小于98的最大的单调递增整数。

代码

func monotoneIncreasingDigits(N int) int {s := strconv.Itoa(N)//将数字转为字符串,方便使用下标ss := []byte(s)//将字符串转为byte数组,方便更改。n := len(ss)if n <= 1 {return N}// 从后向前遍历332的数值变化为:332 -> 329 -> 299for i := n-1; i > 0; i-- {if ss[i-1] > ss[i] {   //前一个大于后一位,前一位减1,后面的全部置为9ss[i-1] -= 1for j := i; j < n; j++ {   //后面的全部置为9ss[j] = '9'}} }res, _ := strconv.Atoi(string(ss))return res 
}

968. 监控二叉树

困难
相关标签
相关企业
给定一个二叉树,我们在树的节点上安装摄像头。
节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。
计算监控树的所有节点所需的最小摄像头数量。

示例 1:
[图片]
输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。
示例 2:
[图片]
输入:[0,0,null,0,null,0,null,null,0]
输出:2
解释:需要至少两个摄像头来监视树的所有节点。 上图显示了摄像头放置的有效位置之一。

提示:

  1. 给定树的节点数的范围是 [1, 1000]。
  2. 每个节点的值都是 0。

思路

  • 局部最优:让叶子节点的父节点安摄像头
  • 此时这道题目还有两个难点:
    1. 二叉树的遍历:后序遍历
    2. 如何隔两个节点放一个摄像头
  • 如何隔两个节点放一个摄像头,来看看这个状态应该如何转移,先来看看每个节点可能有几种状态:有如下三种:
    • 该节点无覆盖
    • 本节点有摄像头
    • 本节点有覆盖

相关文章:

代码随想录算法训练营第37天|● 738.单调递增的数字 ● 968.监控二叉树 ● 总结

738. 单调递增的数字 中等 相关标签 相关企业 提示 当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时&#xff0c;我们称这个整数是单调递增的。 给定一个整数 n &#xff0c;返回 小于或等于 n 的最大数字&#xff0c;且数字呈 单调递增 。 示例 1: 输入: n 10输出: …...

出现 java: 找不到符号 符号: 变量 log 的解决方法

目录 1. 问题所示2. 原理分析3. 解决方法3.1 增加编译参数3.2 增加lombok插件3.3 清楚本地缓存1. 问题所示 使用Springboot启动项目的时候,出现如下bug: java: 找不到符号符号: 变量 log位置: 类 org.springblade.example.consumer.rpc.BlogStu...

大数据机器学习与深度学习—— 生成对抗网络(GAN)

GAN概述 在讲GAN之前&#xff0c;先讲一个小趣事&#xff0c;你知道GAN是怎么被发明的吗&#xff1f;据Ian Goodfellow自己说&#xff1a; 之前他一直在研究生成模型&#xff0c;可能是一时兴起&#xff0c;有一天他在酒吧喝酒时&#xff0c;在酒吧里跟朋友讨论起生成模型。然…...

vue前端访问Django channels WebSocket失败

现象 前端报错&#xff1a;SSH.vue:51 WebSocket connection to ‘ws://127.0.0.1:8000/server/terminal/120.59.88.26/22/1/’ failed: 后端报错&#xff1a;Not Found: /server/terminal/120.79.83.26/22/1/ 原因 django的版本与channels的版本不匹配&#xff08;django…...

厉害了!水浸监控技术有升级啦

水浸监控在今天的社会中变得愈发重要&#xff0c;特别是在各种行业和场所。面对突发的水灾&#xff0c;及时有效的监测和预警系统可以帮助组织减少损失&#xff0c;保障人员和财产的安全。 客户案例 商业办公楼 合肥某大型商业办公楼面临着水灾风险&#xff0c;而传统的监控系…...

【开题报告】基于SpringBoot的大学生心理教育平台的设计与实现

1.研究背景 大学生心理健康问题一直备受关注。随着社会压力的增加、人际关系的复杂化以及学业与就业压力等因素的影响&#xff0c;大学生心理健康问题日益突出。因此&#xff0c;设计并实现基于SpringBoot的大学生心理教育平台具有重要的研究意义和实践价值。 &#xff08;1&…...

376. 摆动序列

376. 摆动序列 原题链接&#xff1a;完成情况&#xff1a;解题思路&#xff1a;参考代码&#xff1a;_376摆动序列_376摆动序列 错误经验吸取 原题链接&#xff1a; 376. 摆动序列 https://leetcode.cn/problems/wiggle-subsequence/description/ 完成情况&#xff1a; 解题…...

现在个人想上架微信小游戏已经这么难了吗...

引言 大家好&#xff0c;最近我突然想起来我还有一款微信小游戏还没有上架&#xff0c;于是捣鼓了一天把游戏完善了一下&#xff0c;然后准备提交审核&#xff0c;却发现异常的艰难... 1.为什么难&#xff1f; 相信大家都大概知道&#xff0c;自从微信平台宣布 9月1日起&…...

C语言数据结构-----二叉树(2)堆的深入理解及应用、链式二叉树的讲解及代码实现

前言 本篇文章讲述的内容有部分是上一节写过的。重复内容不会再进行说明&#xff0c;大家可以看上一节内容 链接: C语言数据结构-----二叉树(1)认识数、二叉树、堆及堆的代码实现 文章目录 前言1.使用堆解决TOP-K问题2.向下调整堆的时间复杂度与向上调整堆的时间复杂度对比3.堆…...

【算法】【动规】等差数列划分

跳转汇总链接 &#x1f449;&#x1f517;算法题汇总链接 1.2 等差数列划分 &#x1f517;题目链接 如果一个数列 至少有三个元素 &#xff0c;并且任意两个相邻元素之差相同&#xff0c;则称该数列为等差数列。例如&#xff0c;[1,3,5,7,9]、[7,7,7,7] 和 [3,-1,-5,-9] 都是…...

系统架构设计师教程(五)软件工程基础知识

软件工程基础知识 5.1 软件工程5.1.1 软件工程定义5.1.2 软件过程模型5.1.3 敏捷模型敏捷开发的特点敏捷方法的核心思想主要敏捷方法简介 5.1.4 统一过程模型 (RUP)RUP的生命周期RUP中的核心概念RUP的特点 5.1.5 软件能力成熟度模型 5.2 需求工程5.2.1 需求获取需求获取的基本步…...

计算机中的文件管理

操作系统对计算机的管理包括两个方面&#xff1a;硬件资源和软件资源。硬件资源的管理包括CPU 的管理、存储器的管理、设备管理等&#xff0c;主要解决硬件资源的有效和合理利用问题。 软件资源包括各种系统程序、各种应用程序、各种用户程序&#xff0c;也包括大量的文档材料、…...

Linux常见排错思路及命令

Linux常见排错思路及命令 一、引言 在Linux系统中&#xff0c;由于其高度可配置和可定制的特性&#xff0c;可能会遇到各种问题。本文将介绍一些常见的排错思路&#xff0c;并提供一些常用的命令&#xff0c;以帮助您快速定位和解决问题。 二、常见排错思路 查看系统日志 …...

【springboot】【easyexcel】excel文件读取

目录 pom.xmlExcelVo逐行读取并处理全部读取并处理向ExcelListener 传参 pom.xml <dependency><groupId>com.alibaba</groupId><artifactId>easyexcel</artifactId><version>3.1.1</version> </dependency>ExcelVo 字段映射…...

【STM32】ADC模数转换器

1 ADC简介 ADC&#xff08;Analog-Digital Converter&#xff09;模拟-数字转换器 ADC可以将引脚上连续变化的模拟电压转换为内存中存储的数字变量&#xff0c;建立模拟电路到数字电路的桥梁 STM32是数字电路&#xff0c;只有高低电平&#xff0c;没有几V电压的概念&#xff…...

Git篇---第九篇

系列文章目录 文章目录 系列文章目录前言一、使用过git merge和git rebase吗?它们之间有什么区别?二、使用过git cherry-pick,有什么作用?前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站,这篇文章男女通用,看…...

Paper Reading: (ACRST) 基于自适应类再平衡自训练的半监督目标检测

目录 简介工作重点方法CropBankFBRAFFRTwo-stage Pseudo-label Filtering 实验与SOTA比较消融实验 简介 题目&#xff1a;《Semi-Supervised Object Detection with Adaptive Class-Rebalancing Self-Training》&#xff0c;AAAI’22&#xff0c; 基于自适应类再平衡自训练的半…...

2023年贺岁电影:一眼多,二眼好多

如果从11月末开始统计&#xff0c;今年贺岁档共有72部贺岁片&#xff0c;平均一天就有2部电影上映&#xff0c;看完总计需要花费7400分钟。 这个数量几乎快赶上2021年到2022年贺岁片的总和。 今年电影市场快速回暖以来&#xff0c;多部爆款作品接力上映&#xff0c;持续刺激市…...

软件测试面试中基础与功能的问题

一、 你们的测试流程是怎么样的&#xff1f; 答&#xff1a;1.项目开始阶段&#xff0c; BA &#xff08;需求分析师&#xff09; 从用户方收集需求并将需求转化为规格说明书&#xff0c;接 下来在 项目组领导 会组织需求评审。 2.需求评审通过后&#xff0c;BA 会组织 项目…...

map|二分查找|离线查询|LeetCode:2736最大和查询

本文涉及的基础知识点 二分查找算法合集 题目 给你两个长度为 n 、下标从 0 开始的整数数组 nums1 和 nums2 &#xff0c;另给你一个下标从 1 开始的二维数组 queries &#xff0c;其中 queries[i] [xi, yi] 。 对于第 i 个查询&#xff0c;在所有满足 nums1[j] > xi 且…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

el-switch文字内置

el-switch文字内置 效果 vue <div style"color:#ffffff;font-size:14px;float:left;margin-bottom:5px;margin-right:5px;">自动加载</div> <el-switch v-model"value" active-color"#3E99FB" inactive-color"#DCDFE6"…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

零基础在实践中学习网络安全-皮卡丘靶场(第九期-Unsafe Fileupload模块)(yakit方式)

本期内容并不是很难&#xff0c;相信大家会学的很愉快&#xff0c;当然对于有后端基础的朋友来说&#xff0c;本期内容更加容易了解&#xff0c;当然没有基础的也别担心&#xff0c;本期内容会详细解释有关内容 本期用到的软件&#xff1a;yakit&#xff08;因为经过之前好多期…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

Mysql中select查询语句的执行过程

目录 1、介绍 1.1、组件介绍 1.2、Sql执行顺序 2、执行流程 2.1. 连接与认证 2.2. 查询缓存 2.3. 语法解析&#xff08;Parser&#xff09; 2.4、执行sql 1. 预处理&#xff08;Preprocessor&#xff09; 2. 查询优化器&#xff08;Optimizer&#xff09; 3. 执行器…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...

【无标题】湖北理元理律师事务所:债务优化中的生活保障与法律平衡之道

文/法律实务观察组 在债务重组领域&#xff0c;专业机构的核心价值不仅在于减轻债务数字&#xff0c;更在于帮助债务人在履行义务的同时维持基本生活尊严。湖北理元理律师事务所的服务实践表明&#xff0c;合法债务优化需同步实现三重平衡&#xff1a; 法律刚性&#xff08;债…...

自然语言处理——文本分类

文本分类 传统机器学习方法文本表示向量空间模型 特征选择文档频率互信息信息增益&#xff08;IG&#xff09; 分类器设计贝叶斯理论&#xff1a;线性判别函数 文本分类性能评估P-R曲线ROC曲线 将文本文档或句子分类为预定义的类或类别&#xff0c; 有单标签多类别文本分类和多…...