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

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

文章目录

  • 前言
  • 一、738.单调递增的数字
  • 二、968.监控二叉树
  • 总结

前言

可以吗?


一、738.单调递增的数字

本题只要想清楚个例,例如98,一旦出现strNum[i - 1] > strNum[i]的情况(非单调递增),首先想让strNum[i - 1]减一,strNum[i]赋值9,这样这个整数就是89。就可以很自然想到对应的贪心解法了。

想到了贪心,还要考虑遍历顺序,只有从后向前遍历才能重复利用上次比较的结果。

最后代码实现的时候,也需要一些技巧,例如用一个flag来标记从哪里开始赋值9。

下面代码的flag为start,flag是为了标识使得后面变为9的位置,防止1000得出900的操作(正确:999),亦或是234得出199(正确:234)。

1和2相同,只是更改了length()与length,以及start--->flag;

class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] ch = s.toCharArray();int start = s.length();for(int i = start-1;i>0;i--)if(ch[i-1] > ch[i]){ch[i-1]--;start = i;}for(int i = start;i<s.length();i++){ch[i] = '9';}return Integer.parseInt(String.valueOf(ch));}
}class Solution {public int monotoneIncreasingDigits(int n) {String s = String.valueOf(n);char[] ch = s.toCharArray();int flag = ch.length;for(int i = flag-1;i>0;i--){if(ch[i-1] > ch[i]){ch[i-1]--;flag = i;}}for(int i = flag;i < ch.length;i++){ch[i] = '9';}return Integer.parseInt(String.valueOf(ch));}
}

二、968.监控二叉树

从题目中示例,其实可以得到启发,我们发现题目示例中的摄像头都没有放在叶子节点上!这是很重要的一个线索,摄像头可以覆盖上中下三层,如果把摄像头放在叶子节点上,就浪费的一层的覆盖。所以把摄像头放在叶子节点的父节点位置,才能充分利用摄像头的覆盖面积。那么有同学可能问了,为什么不从头结点开始看起呢,为啥要从叶子节点看呢?

因为头结点放不放摄像头也就省下一个摄像头, 叶子节点放不放摄像头省下了的摄像头数量是指数阶别的。所以我们要从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!局部最优推出全局最优,找不出反例,那么就按照贪心来!

此时,大体思路就是从低到上,先给叶子节点父节点放个摄像头,然后隔两个节点放一个摄像头,直至到二叉树头结点。此时这道题目还有两个难点:

  1. 二叉树的遍历
  2. 如何隔两个节点放一个摄像头

有如下三种:

  • 该节点无覆盖
  • 本节点有摄像头
  • 本节点有覆盖

我们分别有三个数字来表示:

  • 0:该节点无覆盖
  • 1:本节点有摄像头
  • 2:本节点有覆盖

大家应该找不出第四个节点的状态了。

一些同学可能会想有没有第四种状态:本节点无摄像头,其实无摄像头就是 无覆盖 或者 有覆盖的状态,所以一共还是三个状态。

因为在遍历树的过程中,就会遇到空节点,那么问题来了,空节点究竟是哪一种状态呢? 空节点表示无覆盖? 表示有摄像头?还是有覆盖呢?

空节点不能是无覆盖的状态,这样叶子节点就要放摄像头了,空节点也不能是有摄像头的状态,这样叶子节点的父节点就没有必要放摄像头了,而是可以把摄像头放在叶子节点的爷爷节点上。

所以空节点的状态只能是有覆盖,这样就可以在叶子节点的父节点放摄像头了;

本题的难点首先是要想到贪心的思路,然后就是遍历和状态推导。

在二叉树上进行状态推导,其实难度就上了一个台阶了,需要对二叉树的操作非常娴熟。

/**
     节点的状态值:
       0 表示无覆盖
       1 表示 有摄像头
       2 表示有覆盖
    后序遍历,根据左右节点的情况,来判读 自己的状态
     */

// 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头 (2,2)

// 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头, (0,0) (0,1) (0,2) (1,0) (2,0),状态值为 1,摄像头数 ++;

// 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头,那么本节点就是处于被覆盖状态

class Solution {int  res=0;public int minCameraCover(TreeNode root) {// 对根节点的状态做检验,防止根节点是无覆盖状态 .if(minCame(root)==0){res++;}return res;}/**节点的状态值:0 表示无覆盖1 表示 有摄像头2 表示有覆盖后序遍历,根据左右节点的情况,来判读 自己的状态*/public int minCame(TreeNode root){if(root==null){// 空节点默认为 有覆盖状态,避免在叶子节点上放摄像头return 2;}int left=minCame(root.left);int  right=minCame(root.right);// 如果左右节点都覆盖了的话, 那么本节点的状态就应该是无覆盖,没有摄像头if(left==2&&right==2){//(2,2)return 0;}else if(left==0||right==0){// 左右节点都是无覆盖状态,那 根节点此时应该放一个摄像头// (0,0) (0,1) (0,2) (1,0) (2,0)// 状态值为 1 摄像头数 ++;res++;return 1;}else{// 左右节点的 状态为 (1,1) (1,2) (2,1) 也就是左右节点至少存在 1个摄像头,// 那么本节点就是处于被覆盖状态return 2;}}
}


总结

我们可以的!

只要一路坚持下来,不仅基础扎实,而且进步也是飞速的。

相关文章:

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

文章目录 前言一、738.单调递增的数字二、968.监控二叉树总结 前言 可以吗&#xff1f; 一、738.单调递增的数字 本题只要想清楚个例&#xff0c;例如98&#xff0c;一旦出现strNum[i - 1] > strNum[i]的情况&#xff08;非单调递增&#xff09;&#xff0c;首先想让strNum…...

SOPC之NIOS Ⅱ实现电机转速PID控制(调用中断函数)

通过FPGA开发板上的NIOS Ⅱ搭建电机控制的硬件平台&#xff0c;包括电机正反转、编码器的读取&#xff0c;再通过软件部分实现PID算法对电机速度进行控制&#xff0c;使其能够渐近设定的编码器目标值。 一、问题与改进 SOPC之NIOS Ⅱ实现电机转速PID控制_STATEABC的博客-CSDN…...

ElasticSearch安装为Win11服务

在windows的环境下操作是Elasticsearch,并且喜欢使用命令行 &#xff0c;启动时通过cmd直接在elasticsearch的bin目录下执行elasticsearch ,这样直接启动的话集群名称会默elasticsearch&#xff0c;节点名称会随机生成。 停止就直接在cmd界面按CtrlC 其实我们也可以将elasticse…...

ransac拟合平面,代替open3d的segment_plane

0.open3d打包太大了&#xff0c;所以决定网上找找代码 使用open3d拟合平面并且求平面的法向量&#xff0c;open3d打包大概1个g的大小。 import open3d as o3dpcd o3d.geometry.PointCloud()pcd.points o3d.utility.Vector3dVector(points)## 使用RANSAC算法拟合平面plane_m…...

Docker技术--Docker镜像管理

1.Docker镜像特性 ①.镜像创建容器的特点 Docker在创建容器的时候需要指定镜像,每一个镜像都有唯一的标识:image_id,也可也使用镜像名称和版本号做唯一的标识,如果不指定版本号,那么默认使用的是最新的版本标签(laster)。 ②.镜像分层机制 Docker镜像是分层构建的,并通过…...

生态环境保护3D数字展厅提供了一个线上环保知识学习平台

在21世纪的今天&#xff0c;科技与环保的交汇点提供了无数令人兴奋的可能性。其中&#xff0c;生态环境保护3D数字展厅就是一个绝佳的例子。这个展厅以其独特的3D技术&#xff0c;为我们带来了一个全新的、互动的学习环境&#xff0c;让我们能够更直观地了解和理解我们的环境。…...

OPENCV实现计算描述子

1、计算描述子 kp,des = sift.computer(img,kp) 2、其作用是进行特征匹配 3、同时计算关键点和描述 3.1、kp,des = sift.detectAnd Computer(img,...)...

Android View动画之LayoutAnimation的使用

接前篇 Android View动画整理 &#xff0c;本篇介绍 LayoutAnimation 的使用。 参考《安卓开发艺术探索》。 View 动画作用于 View 。 LayoutAnimation 则作用于 ViewGroup &#xff0c; 为 ViewGoup 指定一个动画&#xff0c;ViewGoup 的子 View 出场时就具体动画效果。 简言…...

低代码与低代码平台的概念解析

随着数字化转型和软件需求的不断增长&#xff0c;传统的手写代码开发方式已经无法满足迅速推出应用程序的需求。为了加快软件开发的速度并降低技术门槛&#xff0c;低代码开发模式应运而生。本文将介绍低代码的概念&#xff0c;探讨什么是低代码什么是低代码平台&#xff1f; 一…...

玩转Mysql系列 - 第8篇:详解排序和分页(order by limit),及存在的坑

这是Mysql系列第7篇。 环境&#xff1a;mysql5.7.25&#xff0c;cmd命令中进行演示。 代码中被[]包含的表示可选&#xff0c;|符号分开的表示可选其一。 本章内容 详解排序查询 详解limit limit存在的坑 分页查询中的坑 排序查询&#xff08;order by&#xff09; 电商…...

Django实现音乐网站 ⒂

使用Python Django框架制作一个音乐网站&#xff0c; 本篇主要是歌手详情页-基本信息、单曲列表功能开发实现内容。 目录 歌手基本信息 增加路由 显示视图 模板显示 推荐歌手跳转详情 歌手增加基本信息 表模型增加字段 数据表更新 基本信息增加内容渲染 歌手单曲列表…...

爬虫逆向实战(二十八)--某税网第一步登录

一、数据接口分析 主页地址&#xff1a;某税网 1、抓包 通过抓包可以发现登录接口是factorAccountLogin 2、判断是否有加密参数 请求参数是否加密&#xff1f; 通过查看载荷模块可以发现有一个datagram 和 一个signature加密参数 请求头是否加密&#xff1f; 通过查看“标…...

【Dots之003】SystemAPI.Query相关基础笔记

1、SystemAPI.Query 注&#xff1a;SystemAPI.Query只能作为foreach中in的的子句 SystemAPI.Query<RefRO<LocalTransform>>().WithAll<Obstacle>()解析&#xff1a;对于每个具有LocalTransform和Obstacle的Entity&#xff1b;都会将LocalTransform的只读引…...

vue v-for 例子

vue v-for 例子 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>Document</title> </head&…...

206.Flink(一):flink概述,flink集群搭建,flink中执行任务,单节点、yarn运行模式,三种部署模式的具体实现

一、Flink概述 1.基本描述 Flink官网地址:Apache Flink — Stateful Computations over Data Streams | Apache Flink Flink是一个框架和分布式处理引擎,用于对无界和有界数据流进行有状态计算。 2.有界流和无界流 无界流(流): 有定义流的开始,没有定义结束。会无休止…...

科技探究之旅--亲子研学活动

2023年8月26日&#xff0c;广州市从化区齐家社会工作服务中心&#xff08;以下简称“齐家”&#xff09;的“星乐园-乡村儿童公益辅导服务项目”组织了新开村及西湖村助学点24对亲子到广州市白云区文搏3D打印基地进行“科技探究之旅--亲子研学”活动&#xff0c;旨在发现、点燃…...

华为云Stack的学习(三)

四、华为云Stack公共组件 1.华为云Stack公共负载均衡方案介绍 1.1 LVS原理 LVS是四层负载均衡&#xff0c;建立在OSI模型的传输层之上&#xff0c;所以效率非常高。 LVS有两种转发模式&#xff1a; NAT模式的转发主要通过修改IP地址&#xff08;位于OSI模型的第三层网络层&…...

大数据平台三大优势详解-行云管家

大数据平台三大优势详解 1、轻松进行数据共享 企业在管理以及快速发展过程中&#xff0c;有着越来越多的数据需要进行管理&#xff0c;如果单独管理则工作量巨大&#xff0c;且难免出现问题&#xff0c;同时共享难。因此需要大数据平台对数据进行统一管理&#xff0c;以及轻松…...

智慧景区方案:AI与视频融合技术如何助力景区监管智能化升级?

随着经济的发展&#xff0c;人们对生活的需求也不再局限于温饱层面&#xff0c;越来越多的人们开始追求文化、艺术的高层次需求&#xff0c;旅游也逐渐成为人们日常放松的一种方式。由于我国人口多、易扎堆等特点&#xff0c;景区的运营监管方式也亟需改革。TSINGSEE青犀智能分…...

HTML基础--Form表单--内联元素

目录 Form表单 表单元素 创建表单 () 文本输入 () 密码输入 单选按钮 () 和 复选框 () 下拉列表 () 和 选项 ()提交按钮 () 重置按钮 () 块元素与行内元素&#xff08;内联元素&#xff09; Form表单 HTML中的表单&#xff08;<form>&#xff09;是一个重要的元…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

CTF show Web 红包题第六弹

提示 1.不是SQL注入 2.需要找关键源码 思路 进入页面发现是一个登录框&#xff0c;很难让人不联想到SQL注入&#xff0c;但提示都说了不是SQL注入&#xff0c;所以就不往这方面想了 ​ 先查看一下网页源码&#xff0c;发现一段JavaScript代码&#xff0c;有一个关键类ctfs…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

2025年能源电力系统与流体力学国际会议 (EPSFD 2025)

2025年能源电力系统与流体力学国际会议&#xff08;EPSFD 2025&#xff09;将于本年度在美丽的杭州盛大召开。作为全球能源、电力系统以及流体力学领域的顶级盛会&#xff0c;EPSFD 2025旨在为来自世界各地的科学家、工程师和研究人员提供一个展示最新研究成果、分享实践经验及…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

2024年赣州旅游投资集团社会招聘笔试真

2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

Neo4j 集群管理:原理、技术与最佳实践深度解析

Neo4j 的集群技术是其企业级高可用性、可扩展性和容错能力的核心。通过深入分析官方文档,本文将系统阐述其集群管理的核心原理、关键技术、实用技巧和行业最佳实践。 Neo4j 的 Causal Clustering 架构提供了一个强大而灵活的基石,用于构建高可用、可扩展且一致的图数据库服务…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...