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

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

题目与题解

参考资料:贪心总结

738.单调递增的数字

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

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

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

解题思路:

        一开始想复杂了,赋值的时候就手忙脚乱,看答案了。

看完代码随想录之后的想法 

        其实逻辑非常单纯,依次从数字的末尾开始往高位比较,如果不符合单调递增的原理,就把当前位的数字减一,同时把后面的所有数字都变成9,一定是最大的数。

        为了做起来方便,可以将输入的数字转换为字符数组,这样修改其中每一位数的时候会简单很多。另外,最好从最小位往高位遍历,同时记录要变成9的数字起始位置,方便后续数字的修改。

class Solution {public int monotoneIncreasingDigits(int n) {if (n <= 9) return n;String[] s = (n + "").split("");int flag = s.length;for (int i = s.length - 1; i > 0 ; i--) {if (Integer.parseInt(s[i]) < Integer.parseInt(s[i-1])) {flag = i;s[i-1] = Integer.parseInt(s[i-1]) - 1 + "";}}for (int i = flag; i < s.length; i++) {s[i] = "9";}return Integer.parseInt(String.join("", s));}
}

遇到的困难

        看过思路以后,一开始想用StringBuilder接收n,然后修改其中的参数,但是不知道为什么setCharAt(i)的时候先读取字符再对其进行-1处理数据类型会变成int,也不知道如何变回char,最后还是老老实实用string数组接收n了,java在字符串处理这一块不是特别好用。

968.监控二叉树

题目链接:​​​​​​​968.监控二叉树

代码随想录题解:968.监控二叉树

视频讲解:贪心算法,二叉树与贪心的结合,有点难...... LeetCode:968.监督二叉树_哔哩哔哩_bilibili

解题思路:

        从善如流,二刷再说

看完代码随想录之后的想法 

        在此先记录一下,感觉很难写。

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;}}
}

遇到的困难

        下次

今日收获

        贪心算法到这里正式结束了。贪心算法说白了就是一些常识的模拟,用到了一些贪心的思维,但没有固定的套路,如何找到局部最优,如何判断局部最优是否能构成全局最优,非常依赖数学直觉。尽量把这几道题都做熟吧,以不变应万变。

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



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

相关文章

Python实现MQTT通信的示例代码

《Python实现MQTT通信的示例代码》本文主要介绍了Python实现MQTT通信的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一... 目录1. 安装paho-mqtt库‌2. 搭建MQTT代理服务器(Broker)‌‌3. pytho

MySQL进行数据库审计的详细步骤和示例代码

《MySQL进行数据库审计的详细步骤和示例代码》数据库审计通过触发器、内置功能及第三方工具记录和监控数据库活动,确保安全、完整与合规,Java代码实现自动化日志记录,整合分析系统提升监控效率,本文给大... 目录一、数据库审计的基本概念二、使用触发器进行数据库审计1. 创建审计表2. 创建触发器三、Java

Zabbix在MySQL性能监控方面的运用及最佳实践记录

《Zabbix在MySQL性能监控方面的运用及最佳实践记录》Zabbix通过自定义脚本和内置模板监控MySQL核心指标(连接、查询、资源、复制),支持自动发现多实例及告警通知,结合可视化仪表盘,可有效... 目录一、核心监控指标及配置1. 关键监控指标示例2. 配置方法二、自动发现与多实例管理1. 实践步骤

prometheus如何使用pushgateway监控网路丢包

《prometheus如何使用pushgateway监控网路丢包》:本文主要介绍prometheus如何使用pushgateway监控网路丢包问题,具有很好的参考价值,希望对大家有所帮助,如有错误... 目录监控网路丢包脚本数据图表总结监控网路丢包脚本[root@gtcq-gt-monitor-prome

Spring Boot集成Druid实现数据源管理与监控的详细步骤

《SpringBoot集成Druid实现数据源管理与监控的详细步骤》本文介绍如何在SpringBoot项目中集成Druid数据库连接池,包括环境搭建、Maven依赖配置、SpringBoot配置文件... 目录1. 引言1.1 环境准备1.2 Druid介绍2. 配置Druid连接池3. 查看Druid监控

如何在Ubuntu 24.04上部署Zabbix 7.0对服务器进行监控

《如何在Ubuntu24.04上部署Zabbix7.0对服务器进行监控》在Ubuntu24.04上部署Zabbix7.0监控阿里云ECS服务器,需配置MariaDB数据库、开放10050/1005... 目录软硬件信息部署步骤步骤 1:安装并配置mariadb步骤 2:安装Zabbix 7.0 Server

Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式

《Java通过驱动包(jar包)连接MySQL数据库的步骤总结及验证方式》本文详细介绍如何使用Java通过JDBC连接MySQL数据库,包括下载驱动、配置Eclipse环境、检测数据库连接等关键步骤,... 目录一、下载驱动包二、放jar包三、检测数据库连接JavaJava 如何使用 JDBC 连接 mys

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

JavaSE正则表达式用法总结大全

《JavaSE正则表达式用法总结大全》正则表达式就是由一些特定的字符组成,代表的是一个规则,:本文主要介绍JavaSE正则表达式用法的相关资料,文中通过代码介绍的非常详细,需要的朋友可以参考下... 目录常用的正则表达式匹配符正则表China编程达式常用的类Pattern类Matcher类PatternSynta

Java中调用数据库存储过程的示例代码

《Java中调用数据库存储过程的示例代码》本文介绍Java通过JDBC调用数据库存储过程的方法,涵盖参数类型、执行步骤及数据库差异,需注意异常处理与资源管理,以优化性能并实现复杂业务逻辑,感兴趣的朋友... 目录一、存储过程概述二、Java调用存储过程的基本javascript步骤三、Java调用存储过程示