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

leetcode贪心(单调递增的数字、监控二叉树)

738.单调递增的数字

给定一个非负整数 N,找出小于或等于 N 的最大的整数,同时这个整数需要满足其各个位数上的数字是单调递增。

(当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时,我们称这个整数是单调递增的。)

示例 1:

输入: N = 10
输出: 9
示例 2:

输入: N = 1234
输出: 1234
示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

class Solution:def monotoneIncreasingDigits(self, N: int) -> int:# 将整数转换为字符串strNum = str(N)# flag用来标记赋值9从哪里开始# 设置为字符串长度,为了防止第二个for循环在flag没有被赋值的情况下执行flag = len(strNum)# 从右往左遍历字符串for i in range(len(strNum) - 1, 0, -1):# 如果当前字符比前一个字符小,说明需要修改前一个字符if strNum[i - 1] > strNum[i]:flag = i  # 更新flag的值,记录需要修改的位置# 将前一个字符减1,以保证递增性质strNum = strNum[:i - 1] + str(int(strNum[i - 1]) - 1) + strNum[i:]# 将flag位置及之后的字符都修改为9,以保证最大的递增数字for i in range(flag, len(strNum)):strNum = strNum[:i] + '9' + strNum[i + 1:]# 将最终的字符串转换回整数并返回return int(strNum)

968.监控二叉树

力扣题目链接(opens new window)

给定一个二叉树,我们在树的节点上安装摄像头。

节点上的每个摄影头都可以监视其父对象、自身及其直接子对象。

计算监控树的所有节点所需的最小摄像头数量。

示例 1:
在这里插入图片描述

输入:[0,0,null,0,0]
输出:1
解释:如图所示,一台摄像头足以监控所有节点。
示例 2:

在这里插入图片描述

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

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

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] += 1return result[0]def traversal(self, cur: TreeNode, result: List[int]) -> int:if not cur:return 2left = 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] += 1return 1# 情况3:# left == 1 && right == 2 左节点有摄像头,右节点有覆盖# left == 2 && right == 1 左节点有覆盖,右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头if left == 1 or right == 1:return 2

相关文章:

leetcode贪心(单调递增的数字、监控二叉树)

738.单调递增的数字 给定一个非负整数 N&#xff0c;找出小于或等于 N 的最大的整数&#xff0c;同时这个整数需要满足其各个位数上的数字是单调递增。 &#xff08;当且仅当每个相邻位数上的数字 x 和 y 满足 x < y 时&#xff0c;我们称这个整数是单调递增的。&#xff…...

如何在win7同样支持Webview2 在 WPF 中使用本地 Webview2 ,如何不依赖系统 Runtime

项目运行环境&#xff1a; .Net Framework 4.5.2 Windows 7 x64 Service Pack 1 WebView2 Microsoft.WebView2.FixedVersionRuntime.120.0.2210.91.x64 考虑到很多老项目&#xff0c;本项目使用的是.Net Framework 4.5.2&#xff0c;.Net 更高版本的其实也是可以支持的。 …...

【docker】网络模式管理

目录 一、Docker网络实现原理 二、Docker的网络模式 1、host模式 1.1 host模式原理 1.2 host模式实操 2、Container模式 2.2 container模式实操 3、none模式 4、bridger模式 4.1 bridge模式的原理 4.2 bridge实操 5、overlay模式 6、自定义网络模式 6.1 为什么需要…...

LiveGBS国标GB/T28181流媒体平台功能-国标级联中作为下级平台对接海康大华宇视华为政务公安内网等GB28181国标平台查看级联状态及会话

LiveGBS国标级联中作为下级平台对接海康大华宇视华为政务公安内网等GB28181国标平台查看级联状态及会话 1、GB/T28181级联是什么2、搭建GB28181国标流媒体平台3、获取上级平台接入信息3.1、如何提供信息给上级3.2、上级国标平台如何添加下级域3.2、接入LiveGBS示例 4、配置国标…...

技术发展驱动编程语言走向

未来编程语言的走向可能会受到多种因素的影响&#xff0c;包括技术进步、市场需求、开发人员的偏好和生态系统的演变等。以下是一些可能的发展趋势&#xff1a; 简洁性和易用性 随着技术的进步&#xff0c;编程语言可能会变得越来越简洁和易于使用。一些语言可能会引入更高级的…...

tp5+workman(GatewayWorker) 安装及使用

一、安装thinkphp5 1、宝塔删除php禁用函数putenv、pcntl_signal_dispatch、pcntl_wai、pcntl_signal、pcntl_alarm、pcntl_fork&#xff0c;执行安装命令。 composer create-project topthink/think5.0.* tp5 --prefer-dist 2、配置好站点之后&#xff0c;浏览器打开访问成…...

vscode安装Prettier插件,对vue3项目进行格式化

之前vscode因为安装了Vue Language Features (Volar)插件&#xff0c;导致Prettier格式化失效&#xff0c;今天有空&#xff0c;又重新设置了一下 1. 插件要先安装上 2. 打开settings.json {"editor.defaultFormatter": "esbenp.prettier-vscode","…...

macOS跨进程通信: XPC 创建实例

一&#xff1a;简介 XPC 是 macOS 里苹果官方比较推荐和安全的的进程间通信机制。 集成流程简单&#xff0c;但是比较绕。 主要需要集成 XPC Server 这个模块&#xff0c;这个模块最终会被 apple 的根进程 launchd 管理和以独立进程的方法唤起和关闭&#xff0c; 我们主app 进…...

Ubuntu18.04 升级Ubuntu20.04

文章目录 背景升级方法遇到的问题 背景 因项目环境需要&#xff0c;欲将Ubuntu18.04升级至Ubuntu20.04&#xff0c;参考网上其他小伙伴的方法&#xff0c;也遇到了一个问题&#xff0c;特此记录一下&#xff0c;希望能帮助其他有同样问题的小伙伴。 升级方法 参考&#xff1a…...

自动化测试怎么做?看完你就懂了。。。

前言 我想应该有很多测试人员应该有这样的疑虑&#xff0c;自动化测试要怎么去做&#xff0c;现在我把自己的一些学习经验分享给大家&#xff0c;希望对你们有帮助&#xff0c;有说的不好的地方&#xff0c;还请多多指教&#xff01; 对于测试人员来说&#xff0c;不管进行功…...

小秋SLAM入门实战opencv所有文章汇总

opencv_core和 opencv_imgcodecs是 OpenCV&#xff08;开源计算机视觉库&#xff09;的两个主要模块 【如何使用cv::erode()函数对图像进行腐蚀操作】 头文件用途 用OpenCV创建一张类型为CV_8UC1的单通道随机灰度图像 用OpenCV创建一张灰度黑色图像并设置某一列为白色 OpenCV创…...

2023年终总结(脚踏实地,仰望星空)

回忆录 2023年&#xff0c;经历非常多的大事情&#xff0c;找工作、实习、研究生毕业、堂哥结婚、大姐买车、申博、读博、参加马拉松&#xff0c;有幸这一年全家人平平安安&#xff0c;在稳步前进。算是折腾的一年&#xff0c;杭州、赣州、武汉、澳门、珠海、遵义来回跑。完成…...

Transforer逐模块讲解

本文将按照transformer的结构图依次对各个模块进行讲解&#xff1a; 可以看一下模型的大致结构&#xff1a;主要有encode和decode两大部分组成&#xff0c;数据经过词embedding以及位置embedding得到encode的时输入数据 输入部分 embedding就是从原始数据中提取出单词或位置&…...

macOS进程间通信的常用技术汇总

macOS进程间通信的常用技术汇总 命令行传参。yyds管道(pipe), 匿名管道&#xff0c; c的技术&#xff0c;可以跨平台使用 只能在父子进程间通信&#xff0c;由于是单向的管道&#xff0c;只能单方面传输数据。 如果需要双向传输&#xff0c;需要建立双向的两条管道才行 匿名管…...

高德地图信息窗体设置

1. 添加默认信息窗体 //构建信息窗体中显示的内容var info [];info.push(<div style"height: 36px; line-height: 45px; padding: 0px 20px; white-space:nowrap;">位置&#xff1a;北京</div>);info.push(<div style"height: 36px; line-heig…...

isEmpty 和 isBlank 的用法区别,居然一半的人答不上来.....

isEmpty 和 isBlank 的用法区别 isEmpty系列isBank系列 hi&#xff01;我是沁禹&#xff5e; 也许你两个都不知道,也许你除了isEmpty/isNotEmpty/isNotBlank/isBlank外,并不知道还有isAnyEmpty/isNoneEmpty/isAnyBlank/isNoneBlank的存在, come on ,让我们一起来探索org.apache…...

数据分析求职-简历准备

简历在整个求职过程中的重要性不言而喻&#xff0c;今天咱们来聊求职过程中简历准备的那些事儿~ 1. 简历究竟有啥用 求职的流程简单说就是&#xff1a;网申->笔试->面试->offer 其中网申环节&#xff0c;简历100%决定了你的通过与否&#xff0c;这个点大家都知道。…...

亚马逊店铺遇到账号申诉模版分享

1.表达诚意&#xff0c;先认错再说&#xff1a;我知道&#xff0c;最近我们在Amazon.com上作为卖家的表现已经低于亚马逊和我们自己的质量标准。 2.清楚分明的格式&#xff1a;我们库存管理的混乱导致了延迟发货&#xff0c;更糟糕的是&#xff0c;物品无法使用。当延迟发货和…...

2023年广东省网络安全A模块(笔记详解)

模块A 基础设施设置与安全加固 一、项目和任务描述&#xff1a; 假定你是某企业的网络安全工程师&#xff0c;对于企业的服务器系统&#xff0c;根据任务要求确保各服务正常运行&#xff0c;并通过综合运用登录和密码策略、流量完整性保护策略、事件监控策略、防火墙策略等多…...

竞赛保研 基于机器视觉的银行卡识别系统 - opencv python

1 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 基于深度学习的银行卡识别算法设计 该项目较为新颖&#xff0c;适合作为竞赛课题方向&#xff0c;学长非常推荐&#xff01; &#x1f9ff; 更多资料, 项目分享&#xff1a; https://gitee.com/dancheng…...

书摘:C 嵌入式系统设计模式 04

本书的原著为&#xff1a;《Design Patterns for Embedded Systems in C ——An Embedded Software Engineering Toolkit 》&#xff0c;讲解的是嵌入式系统设计模式&#xff0c;是一本不可多得的好书。 本系列描述我对书中内容的理解。 实现类的最简单方法是使用文件作为封装…...

C 练习实例16 - 最大公约数和最小公倍数

题目&#xff1a;输入两个正整数a和b&#xff0c;求其最大公约数和最小公倍数 数学&#xff1a;最大公约数*最小公倍数a*b 例如&#xff1a;a16&#xff0c;b20。最小公倍数80&#xff0c;最大公约数4。80*416*20。 算法&#xff1a;辗转相除法&#xff0c;又称欧几里德算法…...

GAN-概念和应用场景

概念和应用 生成对抗网络 &#xff08;GAN&#xff09; 的 18 个令人印象深刻的应用 by 杰森布朗利 on July 12&#xff0c; 2019 in 生成对抗网络110 鸣叫 共享 生成对抗网络 &#xff08;GAN&#xff09; 是一种用于生成建模的神经网络架构。 生成式建模涉及使用模型生成可…...

LeetCode(36)有效的数独 ⭐⭐

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 &#xff0c;验证已经填入的数字是否有效即可。 数字 1-9 在每一行只能出现一次。数字 1-9 在每一列只能出现一次。数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。&#xff08;请参考示例图&#xff09; 注…...

用LCD显示字符‘A‘

#include<reg51.h> //包含单片机寄存器的头文件 #include<intrins.h> //包含_nop_()函数定义的头文件 sbit RSP2^0; //寄存器选择位&#xff0c;将RS位定义为P2.0引脚 sbit RWP2^1; //读写选择位&#xff0c;将RW位定义为P2.1引脚 sbit EP2^2; //使能…...

Zookeeper相关问题及答案(2024)

1、ZooKeeper是什么&#xff1f;它的主要用途是什么&#xff1f; ZooKeeper 是一个由 Apache 预先开发和维护的开源服务器&#xff0c;用于协调分布式应用程序。它是一个集中式服务&#xff0c;为分布式应用提供一致性保障&#xff0c;配置管理&#xff0c;命名&#xff0c;同…...

1.大数据概述

目录 概述hadoophadoop 模块hadoop 发行版apache社区版本CDP(CDHHDP)其它云产商框架选择 hadoop 安装 结束 概述 先了解几个常用的网站 apache 官网hadoop 官网hadoop githubhttps://github.com/apache/xxx [https://github.com/apache/spark (example)] hadoop hadoop 模块…...

NGUI基础-Widget

目录 Widget是什么 Widget组件包含的属性 Pivot Depth Size snap Aspect Free Based on Width Based on Height Widget是什么 在Unity UI系统中&#xff0c;"Widget"是指UI元素的基类&#xff0c;它为UI元素提供了位置、大小和锚点等基本属性。通过使用&qu…...

SpringBoot集成沙箱支付

前言 支付宝沙箱支付&#xff08;Alipay Sandbox Payment&#xff09;是支付宝提供的一个模拟支付环境&#xff0c;用于开发和测试支付宝支付功能的开发者工具。在真实的支付宝环境中进行支付开发和测试可能涉及真实资金和真实用户账户&#xff0c;而沙箱环境则提供了一个安全…...

BUUCTF--gyctf_2020_borrowstack1

这是一题栈迁移的题目&#xff0c;先看看保护&#xff1a; 黑盒测试&#xff1a; 用户可输入两次内容&#xff0c;接着看看IDA中具体程序流程&#xff1a; 我们看到溢出内容只有0x10的空间给我们布局&#xff0c;这显然是不足以我们布置rop的。因此肯定就是栈迁移了。迁到什么地…...

哪家网站建设/个人博客登录入口

点击蓝字关注我们吧&#xff01;第一种打印hello world的方法启动Python程序并打印Hello world&#xff01;第二种打印hello world的方法1&#xff0c;新建一个hello.py文件&#xff0c;使用notepad打开&#xff08;或者新建一个hello.txt文档&#xff0c;编写完代码后&#xf…...

iis建设的网站无法访问/seo概念的理解

MySQL联合索引VS单列索引以一个一千万数据量的表格为例mysql1. 建表建索引USE foo;DROP TABLE IF EXISTS tmp;CREATE TABLE tmp (id INT UNSIGNED PRIMARY KEY AUTO_INCREMENT,school_id INT UNSIGNED NOT NULL,student_id INT UNSIGNED NOT NULL,INDEX school_id(school_id),I…...

网页建站网站申请/广告联盟app下载

讨人喜欢的26个原则&#xff0c;让你的人际关系更上一层楼&#xff01; 1.长相不令人讨厌&#xff0c;如果长得不好&#xff0c;就让自己有才气&#xff1b;如果才气也没有&#xff0c;那就总是微笑。      2.气质是关键。如果时尚学不好&#xff0c;宁愿纯朴。      …...

南通通州区网站制作/seo优化软件购买

计算机网络 网络层 【4-18】 请回答下列问题&#xff1a; Q&#xff1a; (1) 有人认为&#xff1a; "ARP 协议向网络层提供了转换地址的服务&#xff0c; 因此ARP 应当属于数据链路层。”这种说法为什么是错误的&#xff1f; (2) 试解释为什么ARP 高速缓存每存入一个…...

宜宾建设招标网站/搜索广告是什么

2018年中考学校录取分数线尚未公布&#xff0c;以下是2017年录取分数线&#xff0c;仅供参考&#xff01;菏泽二中统招线&#xff1a;613.5。指标生调剂线&#xff1a;604。最低线&#xff1a;513.5。体育&#xff1a;481。音乐&#xff1a;475.5。美术&#xff1a;428。曹州一…...

公司自己做网站流程和备案/电子商务

从这篇文章起&#xff0c;我们看看Vue3.0的响应式部分源码。这部分reactive方法是核心&#xff0c;reactive方法如下&#xff1a; export function reactive<T extends object>(target: T): UnwrapNestedRefs<T> export function reactive(target: object) {// if…...