算法打卡day32

今日任务:

1)738.单调递增的数字

2)968.监控二叉树

738.单调递增的数字

题目链接:738. 单调递增的数字 - 力扣(LeetCode)

文章讲解:代码随想录 (programmercarl.com)

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

思路:

这个问题的解题思路是通过从右往左遍历数字,找到第一个比右边数字大的位置 i,然后将位置 i 上的数字减一,并将位置 i 右侧的所有数字都变成9。这样可以保证最终得到的数字是小于或等于原始数字的最大单调递增数字。

具体的步骤如下:

  1. 将整数转换为数字列表,便于按位处理。
  2. 从倒数第二个位置开始向左遍历字符串列表,直到第一个位置。
  3. 在遍历过程中,如果当前数字比后一个数字大,说明需要将当前数字减一,并将后面的数字全部置为9。
  4. 最后将列表转换为整数并返回。

通过这样的操作,可以确保得到的数字是小于或等于原始数字的最大单调递增数字。

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        # 如果区间集合为空,返回0
        if not intervals:
            return 0

        intervals.sort(key=lambda x: x[0])

        # 初始化移除区间的数量为0
        remove_count = 0
        # 初始化上一个不重叠区间的结束位置为第一个区间的结束位置
        end = intervals[0][1]
        for i in intervals[1:]:
            # 存在重叠区间
            if i[0] < end:
                # 更新重叠区间的右边界:选一个结束位置小的区间,减少重叠
                end = min(i[1],end)
                remove_count += 1
            else:
                end = i[1]
        return remove_count

968.监控二叉树

题目链接:968. 监控二叉树 - 力扣(LeetCode)

文章讲解:代码随想录 (programmercarl.com)

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

思路:

  1. 对于每个节点,考虑其三种状态:

    • 状态0:表示当前节点没有被覆盖。
    • 状态1:表示当前节点有摄像头。
    • 状态2:表示当前节点被覆盖,但没有摄像头。
  2. 采用后序遍历(左-右-根)的方式遍历二叉树:

    • 左右节点至少有一个无覆盖的情况:如果左子节点或右子节点的状态为0(未被覆盖),则当前节点需要放置摄像头(状态1)。
    • 左右节点至少有一个有摄像头:如果左子节点或右子节点的状态为1(有摄像头),则当前节点已经被覆盖(状态2)。
      • left == 1 && right == 2 左节点有摄像头,右节点有覆盖
      • left == 2 && right == 1 左节点有覆盖,右节点有摄像头
      • left == 1 && right == 1 左右节点都有摄像头
    • 左右节点都有覆盖:如果左子节点且右子节点的状态为2(被覆盖但没有摄像头),则当前节点不需要放置摄像头,但需要标记为未被覆盖(状态0)。
  3. 对于根节点,如果其状态为0,则需要额外放置一个摄像头(状态1)。

  4. 统计放置的摄像头数量即为所需的最小摄像头数量。

class Solution:
         # Greedy Algo:
        # 从下往上安装摄像头:跳过leaves这样安装数量最少,局部最优 -> 全局最优
        # 先给leaves的父节点安装,然后每隔两层节点安装一个摄像头,直到Head
        # 0: 该节点未覆盖
        # 1: 该节点有摄像头
        # 2: 该节点有覆盖
    def minCameraCover(self, root: TreeNode) -> int:
        # 定义递归函数
        result = [0]  # 用于记录摄像头的安装数量
        if self.traversal(root, result) == 0:
            result[0] += 1

        return result[0]

        
    def traversal(self, cur: TreeNode, result: List[int]) -> int:
        if not cur:
            return 2

        left = self.traversal(cur.left, result)
        right = self.traversal(cur.right, result)

        # 情况1: 左右节点都有覆盖
        if left == 2 and right == 2:
            return 0

        # 情况2:
        # left == 0 && right == 0 左右节点无覆盖
        # left == 1 && right == 0 左节点有摄像头,右节点无覆盖
        # left == 0 && right == 1 左节点无覆盖,右节点有摄像头
        # left == 0 && right == 2 左节点无覆盖,右节点覆盖
        # left == 2 && right == 0 左节点覆盖,右节点无覆盖
        if left == 0 or right == 0:
            result[0] += 1
            return 1

        # 情况3:
        # left == 1 && right == 2 左节点有摄像头,右节点有覆盖
        # left == 2 && right == 1 左节点有覆盖,右节点有摄像头
        # left == 1 && right == 1 左右节点都有摄像头
        if left == 1 or right == 1:
            return 2

感想:

有点难,情况比较多。仅理解。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/537060.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

CPU核心数、线程数都是什么意思?

最早&#xff0c;每个物理 cpu 上只有一个核心&#xff0c;对操作系统而言&#xff0c;也就是同一时刻只能运行一个进程/线程。 为了提高性能&#xff0c;cpu 厂商开始在单个物理 cpu 上增加核心&#xff08;实实在在的硬件存在&#xff09;&#xff0c;也就出现了多核 cpu&…

个人博客项目笔记_07

写文章 写文章需要 三个接口&#xff1a; 获取所有文章类别 获取所有标签 发布文章 1. 所有文章分类 1.1 接口说明 接口url&#xff1a;/categorys 请求方式&#xff1a;GET 请求参数&#xff1a; 参数名称参数类型说明 返回数据&#xff1a; {"success":…

Linux启动流程,常见故障英文总结/Linux学习环境发行版本选择及运行故障(补充)

小编这里对前面文章内容进行补充 1.运维架构人员理解Linux启动流程&#xff08;对故障进行排查&#xff09;&#xff0c;企业面试面试官让面试者描述Linux启动细节&#xff0c;小编在这篇文章补充以下&#xff0c;制作了图表&#xff0c;有利于大家看懂整个流程 2.对于初学者/老…

14亿美元!德国默克与AI生物科技公司合作;马斯克Neuralink首位脑机接口植入者用意念打游戏;黄仁勋在俄勒冈州立大学开讲

AI for Science 的新成果、新动态、新视角—— 日本第一 IT 公司富士通&#xff1a;生成式 AI 加速药物研发 马斯克&#xff1a;Neuralink 首位脑机接口植入者用「意念」打游戏 默克与 AI 生物科技公司 Caris 达成合作 AI 蛋白质设计服务提供商「天鹜科技」完成数千万元 Pre…

IDEA中使用正则表达式替换时间日期

很多时候需要把系统中的时间替换成当前时间&#xff0c;这是后我们就可以把数据库SQL文件在IDEA中打开&#xff0c;然后使用正则进行替换&#xff0c;下面我们来看下&#xff1a; 1.日期格式&#xff1a;校验yyyy&#xff0d;MM&#xff0d;dd ((([0-9]{3}[1-9]|[0-9]{2}[1-9…

ELK 企业级日志分析 ELFK

一 ELK 简介 ELK平台是一套完整的日志集中处理解决方案&#xff0c;将 ElasticSearch、Logstash 和 Kiabana 三个开源 工具配合使用&#xff0c; 完成更强大的用户对日志的查询、排序、统计需求。 1 ElasticSearch&#xff1a; 是基于Lucene&#xff08;一个全文检索引擎的…

golang的引用和非引用总结

目录 概述 一、基本概念 指针类型&#xff08;Pointer type&#xff09; 非引用类型&#xff08;值类型&#xff09; 引用类型&#xff08;Reference Types&#xff09; 解引用&#xff08;dereference&#xff09; 二、引用类型和非引用类型的区别 三、golang数据类型…

李沐27_含并行连结的网络GoogLeNet_Inception——自学笔记

Inception块 1.四个路径从不同层面抽取信息&#xff0c;然后在输出通道维合并。 2.有更少的参数个数和计算复杂度&#xff08;相比于3X3和5X5卷积层&#xff09; GoogLeNet 1.五个stages&#xff0c;九个inception块 Inception各种后续变种 1.Inception-BN(V2)——使用ba…

【Harbor】harbor.yml详解

目录 前言参数详解hostnameHTTP和HTTPSinternal_tlsharbor_admin_passworddatabasedata_volumestorage_serviceclairtrivyjobservicenotificationchartlog_versionexternal_databaseexternal_redisuaaproxy 前言 网络上对Harbor相关的资料真是少之又少&#xff0c;基本上都是教…

2024mathorcup数学建模A 题思路分析-移动通信网络中 PCI 规划问题

# 1 赛题 A 题 移动通信网络中 PCI 规划问题 物理小区识别码(PCI)规划是移动通信网络中下行链路层上&#xff0c;对各覆盖 小区编号进行合理配置&#xff0c;以避免 PCI 冲突、 PCI 混淆以及 PCI 模 3 干扰等 现象。 PCI 规划对于减少物理层的小区间互相干扰(ICI)&#xff0c;增…

STM32程序 关于Semhosting(半主机)和Microlib 以及Printf的关系

一&#xff0c;Keil中Printf导致程序无法运行到Main函数 在Keil中调试STM32程序&#xff0c;编译烧录后&#xff0c;发现程序不能运行&#xff0c;Main函数中点亮LED灯的语句没起作用&#xff0c;说明没有进入Main函数。用Keil调试的时候&#xff0c;虽然设置了Run to main()&…

Docker学习笔记(二):在Linux中部署Docker(Centos7下安装docker、环境配置,以及镜像简单使用)

一、前言 记录时间 [2024-4-6] 前置文章&#xff1a;Docker学习笔记&#xff08;一&#xff09;&#xff1a;入门篇&#xff0c;Docker概述、基本组成等&#xff0c;对Docker有一个初步的认识 在上文中&#xff0c;笔者进行了Docker概述&#xff0c;介绍其历史、优势、作用&am…

springboot相关报错解决

Caused by: java.lang.ClassNotFoundException: 目录 Caused by: java.lang.ClassNotFoundException: org.springframework.context.event.GenericApplicationListener spring-boot-dependencies:jar:2.1.9.RELEASE was not found org.springframework.context.event.Generi…

Mybatis-plus动态数据源

由于服务没有做微服务部署&#xff0c;需要在后台管理系统访问其他服务的库&#xff0c;所以需要用到动态数据源切换 引入依赖 mybatis-plus动态数据源依赖 <dependency><groupId>com.baomidou</groupId><artifactId>dynamic-datasource-spring-boot…

【生产实习-毕设】pyspark学生成绩分析与预测(上)

注意&#xff1a;数据由实习单位老师提供&#xff08;需要自行搜索下载&#xff09;&#xff0c;页面美化为下载模板。 项目介绍&#xff1a;前端页面输入影响成绩的属性&#xff0c;预测出成绩&#xff0c;并作可视化展示——属性对成绩的影响。使用python pyspark 进行数据预…

SpringBoot + Dobbo + nacos

SpringBoot Dobbo nacos 一、nacos https://nacos.io/zh-cn/docs/quick-start.html 1、下载安装包 https://github.com/alibaba/nacos/releases/下载后在主目录下&#xff0c;创建一个logs的文件夹&#xff1a;用来存日志 2、启动nacos 在bin目录下打开cmd运行启动命令&a…

小红的白色字符串

题目描述 小红拿到了一个字符串&#xff0c;她准备将一些字母变成白色&#xff0c;变成白色的字母看上去就和空格一样&#xff0c;这样字符串就变成了一些单词。 现在小红希望&#xff0c;每个单词都满足以下两种情况中的一种&#xff1a; 1.开头第一个大写&#xff0c;其余为…

简述OSI七层模型及每层的功能任务和协议

文章目录 一、OSI七层模型的功能和任务1.物理层2.数据链路层3.网络层4.传输层5.会话层6.表示层7. 应用层 二、OSI七层模型每层的协议 开放系统互连参考模型&#xff08;Open System Interconnect&#xff0c;简称OSI&#xff09;是国际标准化组织(ISO)和国际电报电话咨询委员会…

为什么选择成为程序员?

目录 兴趣和热爱高薪和就业机会持续学习和不断成长挑战和乐趣 兴趣和热爱 许多人选择成为程序员可能是热爱&#xff0c;对计算机&#xff0c;以及编程和科技产生了浓厚的兴趣&#xff0c;并且享受着解决每一个技术问题&#xff0c;构建应用程序和探索新技术所带来的乐趣。 谈到…

vue快速入门(十七)v-model数据双向绑定修饰符

注释很详细&#xff0c;直接上代码 上一篇 新增内容 v-model.trim 自动去除首尾空格v-model.number 自动转换成数字类型 源码 <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport" con…