算法记录 | Day37 贪心算法

news/2024/4/24 23:54:30/

738.单调递增的数字

思路:

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

2.向后遍历

从前向后遍历的话,遇到strNum[i - 1] > strNum[i]的情况,让strNum[i - 1]减一,但此时如果strNum[i - 1]减一了,可能又小于strNum[i - 2]。

e.g:332,从前向后遍历的话,那么就把变成了329,此时2又小于了第一位的3了,真正的结果应该是299。

​ 后向前遍历332的数值变化为:332 -> 329 -> 299

class Solution:def monotoneIncreasingDigits(self, n: int) -> int:a = list(str(n))for i in range(len(a)-1,0,-1):if int(a[i]) < int(a[i-1]):a[i-1] = str(int(a[i-1])-1)a[i:] = '9' *(len(a)-i)return int("".join(a))

968.监控二叉树

思路:

让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!

可以使用后序遍历的方式遍历二叉树的节点,这样就可以优先遍历叶子节点。

对于每个节点,利用贪心思想,可以确定三种状态:

  • 第一种状态:该节点无覆盖
  • 第二种状态:该节点已经装上了摄像头
  • 第三种状态:该节点已经覆盖

为了让摄像头数量最少,要尽量让叶子节点的父节点安装摄像头,这样才能摄像头的数量最少。对此应当分析当前节点和左右两侧子节点的覆盖情况。

  • 情况1:左右节点都有覆盖

​ 左孩子有覆盖,右孩子有覆盖,那么此时中间节点应该就是无覆盖的状态了。

if left == 2 and right == 2:return 0

968.监控二叉树2

  • 情况2:左右节点至少有一个无覆盖的情况,如果是以下情况,则中间节点(父节点)应该放摄像头:

    • left == 0 && right == 0 左右节点无覆盖

    • left == 1 && right == 0 左节点有摄像头,右节点无覆盖

    • left == 0 && right == 1 左节点有无覆盖,右节点摄像头

    • left == 0 && right == 2 左节点无覆盖,右节点覆盖

    • left == 2 && right == 0 左节点覆盖,右节点无覆盖

这个不难理解,毕竟有一个孩子没有覆盖,父节点就应该放摄像头。

此时摄像头的数量要加一,并且return 1,代表中间节点放摄像头。

# Case 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 += 1
return 1
  • 情况3:左右节点至少有一个有摄像头,如果是以下情况,其实就是 左右孩子节点有一个有摄像头了,那么其父节点就应该是2(覆盖的状态)

    • left == 1 && right == 2 左节点有摄像头,右节点有覆盖

    • left == 2 && right == 1 左节点有覆盖,右节点有摄像头

    • left == 1 && right == 1 左右节点都有摄像头

968.监控二叉树1

# Case 3:# left == 1 && right == 2 左节点有摄像头,右节点有覆盖# left == 2 && right == 1 左节点有覆盖,右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头
if left == 1 or right == 1:return 2
  • 情况4:头结点没有覆盖,以上都处理完了,递归结束之后,可能头结点 还有一个无覆盖的情况,如图:

968.监控二叉树3

if traversal(root) == 0:result += 1
class Solution:def minCameraCover(self, root: TreeNode) -> int:# Greedy Algo:# 从下往上安装摄像头:跳过leaves这样安装数量最少,局部最优 -> 全局最优# 先给leaves的父节点安装,然后每隔两层节点安装一个摄像头,直到Head# 0: 该节点未覆盖# 1: 该节点有摄像头# 2: 该节点有覆盖result = 0# 从下往上遍历:后序(左右中)def traversal(curr: TreeNode) -> int:nonlocal resultif not curr: return 2left = traversal(curr.left)right = traversal(curr.right)# Case 1:# 左右节点都有覆盖if left == 2 and right == 2:return 0# Case 2:# left == 0 && right == 0 左右节点无覆盖# left == 1 && right == 0 左节点有摄像头,右节点无覆盖# left == 0 && right == 1 左节点有无覆盖,右节点摄像头# left == 0 && right == 2 左节点无覆盖,右节点覆盖# left == 2 && right == 0 左节点覆盖,右节点无覆盖elif left == 0 or right == 0:result += 1return 1# Case 3:# left == 1 && right == 2 左节点有摄像头,右节点有覆盖# left == 2 && right == 1 左节点有覆盖,右节点有摄像头# left == 1 && right == 1 左右节点都有摄像头elif left == 1 or right == 1:return 2# 其他情况前段代码均已覆盖if traversal(root) == 0:result += 1return result

http://www.ppmy.cn/news/48570.html

相关文章

10分钟了解人工智能(最通俗的语言)

最通俗的语言&#xff1a;15分钟了解人工智能&#xff1b;唯一优点&#xff0c;受众完全听懂 无人驾驶、智能家居、远程医疗……如今&#xff0c;人工智能(AI)技术已被广泛应用于金融、交通、医疗、安防、教育等领域&#xff0c;成为经济增长新动能 一 什么是人工智能 人工智能…

JVM之JDK 监控和故障处理工具总结

JDK 命令行工具 这些命令在 JDK 安装目录下的 bin 目录下&#xff1a; jps (JVM Process Status&#xff09;: 类似 UNIX 的 ps 命令。用于查看所有 Java 进程的启动类、传入参数和Java 虚拟机参数等信息&#xff1b;jstat&#xff08;JVM Statistics Monitoring Tool&#x…

java项目之疫情网课管理系统(springboot+vue源码)

风定落花生&#xff0c;歌声逐流水&#xff0c;大家好我是风歌&#xff0c;混迹在java圈的辛苦码农。今天要和大家聊的是一款基于springboot的疫情网课管理系统。项目源码以及部署相关请联系风歌&#xff0c;文末附上联系信息 。 &#x1f495;&#x1f495;作者&#xff1a;风…

redis笔记

string sds(简单动态字符串) sds内部又可以转为int ,embstr(连续&#xff0c;查一次内存),raw&#xff08;查两次&#xff09; 效率 防止数据溢出 空间预分配 惰性空间释放 hash ziplist (数据量小) hashtable list ziplist (连续内存空间&#xff0c;访问效率高) quicklist&am…

QT CTK控件 CTK开发(二)

CTK 为支持生物医学图像计算的公共开发包,其全称为 Common Toolkit。为医学成像提供一组统一的基本功能;促进代码和数据的交互及结合;避免重复开发;在工具包(医学成像)范围内不断扩展到新任务,而不会增加现有任务的负担;整合并适应成功的解决方案。 本专栏文章较为全面…

【华为OD机试真题】预定酒店(javaC++python)100%通过率

预定酒店 知识点排序 时间限制:1s空间限制:256MB限定语言:不限 题目描述: 放暑假了,小明决定到某旅游景点游玩,他在网上搜索到了各种价位的酒店(长度为 n的数组A),他的心理价位是x元,请帮他筛选出k个最接近x元的酒店(n>=k>0),并由低到高打印酒店的价格。 …

无线蓝牙耳机哪款音质好?目前音质最好的无线蓝牙耳机推荐

现如今&#xff0c;蓝牙耳机已经是一个非常实用且常见的数码产品了&#xff0c;不少人喜欢戴着蓝牙耳机听歌&#xff0c;玩游戏。一款音质好的蓝牙耳机不止能听个响&#xff0c;还能给人极致的听觉享受。在此&#xff0c;我来给大家分享几款目前音质最好的无线蓝牙耳机&#xf…

只要这5步,帮您和团队成功从手工测试转到自动化测试

目前有很多团队正在逐步从手工测试调整到自动化测试&#xff0c;只因自动化测试可以最大限度减少回归错误并且克服手工测试的问题。手工测试和自动化测试的区别在于谁来执行&#xff0c;人还是机器。对于手工测试。测试人员手工执行所有测试步骤&#xff0c;以便在应用程序发布…

大数据相关开源项目及组件汇总

前言 花了一点时间&#xff0c;整理了大数据相关开源项目、组件和官网地址。按照实际应用功能的不同&#xff0c;分为以下10个部分&#xff0c;并在目录图中进行归纳&#xff0c;后续章节的内容则是分别介绍各组件的背景及应用场景。 调度与管理服务 文件系统 数据搜集 消…

垃圾回收面试总结

堆空间的基本结构 Java 的自动内存管理主要是针对对象内存的回收和对象内存的分配。同时&#xff0c;Java 自动内存管理最核心的功能是 堆 内存中对象的分配与回收。 Java 堆是垃圾收集器管理的主要区域&#xff0c;因此也被称作 GC 堆&#xff08;Garbage Collected Heap&am…

连接VPN后无法上网 Windows Route 轻松解决

连接VPN后无法上网 Windows Route 轻松解决 引言文档添加路由 引言 很多时候&#xff0c;我们公司的 VPN 为了不占用公司的外网带宽和安全起见&#xff0c;都会禁止访问外网。我们的电脑连接 VPN 后&#xff0c;所有的网络数据包都会走 VPN&#xff0c;从而导致我们无法访问互…

EIGRP配置邻居关系详解

1.2 EIGRP 邻居关系 1.2.1 实验目的 通过 EIGRP 邻居建立的相关实验&#xff0c;学习到如何调整 EIGRP 的 HELLO 和 HOLD 时间&#xff0c;使用 被动接口阻止不必要的邻居关系&#xff0c;认证 EIGRP 邻居&#xff0c;静态邻居的配置以及哪些参数影响 EIGRP 邻居建立。 1.2.…

java调用webservicer的方法

对于使用 Webservicer的方式&#xff0c;一般采用 Java API调用的方式。Webservicer是一个运行在浏览器中的客户端程序&#xff0c;它可以通过 Webservicer的接口来访问服务器上的服务。 使用 Java调用 Webservicer有两种方式&#xff1a; 下面是一个简单的例子&#xff1a; 2、…

three.js之摄像机

本节将在上一节的基础上进一步介绍一下摄像机功能。 three.js的摄像机主要包括两类&#xff1a;正交投影摄像机和透视投影摄像机。 透视投影摄像机&#xff1a;THREE.PerspectiveCamera&#xff0c;最自然的视图&#xff0c;距离摄像机越远&#xff0c;它们就会被渲染得越小。…

一只小蜜蜂

文章目录 一只小蜜蜂程序设计程序分析一只小蜜蜂 【问题描述】 有一只经过训练的蜜蜂只能爬向右侧相邻的蜂房,不能反向爬行。请编程计算蜜蜂从蜂房a爬到蜂房b的可能路线数。 其中,蜂房的结构如下所示。 【输入形式】 输入数据的第一行是一个整数N,表示测试实例的个数,然后是…

【数据库多表操作】sql语句基础及进阶

常用数据库&#xff1a; 数据库&#xff08;Database&#xff09;是按照数据结构来组织、存储和管理数据的仓库&#xff0c;它是长期存储在计算机内、有组织、有结构的数据集合。数据库是信息系统的核心部分&#xff0c;现代软件系统中大量采用了数据库管理系统&#xff08;DBM…

Oracle EBS数据定义移植工具:FNDLOAD

在实际的EBS二次开发中&#xff0c;我们经常会碰到需要在各个环境之间移植二次开发的程序对象以及数据定义&#xff0c;如在EBS二次开发中并发请求的定义会涉及到&#xff1a; 可执行、并发程序、值集、请求组等的定义&#xff0c;定义需要从开发环境、测试环境、UAT环境一直到…

【微信小程序-原生开发】实用教程21 - 分包

分包的流程 当微信小程序主包大小超过2M时&#xff0c;则需要对微信小程序进行分包&#xff0c;方法如下&#xff1a; 1. 转移页面文件 在项目根目录下&#xff0c;新建文件夹 package1 &#xff08;即自定义的分包名为 package1 &#xff09;文件夹 package1 内新建文件夹 p…

差分运算放大电路原理解析

差分运算放大电路&#xff0c;对共模信号得到有效抑制&#xff0c;而只对差分信号进行放大&#xff0c;因而得到广泛的用。 注&#xff1a; &#xff08;1&#xff09;共模信号   共模信号&#xff08;common mode signal&#xff09;是指同时作用于多个电路或电子设备上的信…

列表、栈、队列

列表&#xff08;List&#xff09; 介绍 一系列有序元素的集合。列表中的元素可以是任意类型&#xff0c;允许重复。 可通过索引定位、访问列表中的&#xff08;单个&#xff09;元素&#xff0c;还可使用切片&#xff08;slice&#xff09;操作一次性访问多个元素&#xff…