贪心算法(2024/7/16)

1合并区间

以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。

示例 1:

输入:intervals = [[1,3],[2,6],[8,10],[15,18]]
输出:[[1,6],[8,10],[15,18]]
解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

示例 2:

输入:intervals = [[1,4],[4,5]]
输出:[[1,5]]
解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。

提示:

  • 1 <= intervals.length <= 104
  • intervals[i].length == 2
  • 0 <= starti <= endi <= 104

思路:本题是判断重叠区间问题  先排序,让所有的相邻区间尽可能的重叠在一起,按左边界,或者右边界排序都可以.

  1. 排序: 首先,根据每个区间的左边界,对给定的区间集合 intervals 进行升序排序。这是为了确保处理区间时,可以按顺序考虑它们的位置关系。

  2. 合并过程: 排序完成后,使用一个结果集合 result 来存储最终合并后的区间。开始时,将排序后的第一个区间直接放入 result 中。

  3. 遍历区间: 从第二个区间开始遍历,与 result 中的最后一个区间比较:

    • 如果当前区间与 result 中的最后一个区间有重叠(即当前区间的左边界小于等于 result 中最后一个区间的右边界),则更新 result 中最后一个区间的右边界为两者的最大值,以实现合并。
    • 如果当前区间与 result 中的最后一个区间没有重叠,则直接将当前区间加入 result

代码

class Solution {
public:// 定义一个静态函数作为比较函数,用于排序static bool cmp(const vector<int>& a, const vector<int>& b) {return a[0] < b[0]; // 按照区间的左边界进行升序排序}vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.empty()) return result; // 如果区间集合为空直接返回空结果// 使用cmp函数对区间进行排序sort(intervals.begin(), intervals.end(), cmp);// 第一个区间直接放入结果集合中result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间// 合并区间,只需要更新结果集合中最后一个区间的右边界result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠,将当前区间加入结果集合}}return result;}
};

2 单调递增的数字

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

给定一个整数 n ,返回 小于或等于 n 的最大数字,且数字呈 单调递增 。

示例 1:

输入: n = 10
输出: 9

示例 2:

输入: n = 1234
输出: 1234

示例 3:

输入: n = 332
输出: 299

提示:

  • 0 <= n <= 109

思路:

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

那么从后向前遍历,就可以重复利用上次比较得出的结果了,从后向前遍历332的数值变化为:332 -> 329 -> 299

  1. 将整数 N 转换为字符串 strNum,便于按位处理。
  2. 从右向左遍历字符串 strNum,找到第一个出现递减的位置 i,即满足 strNum[i-1] > strNum[i]
  3. 将第 i-1 位减一,并标记 flag 为 i,表示从这里开始需要调整。
  4. 将从 flag 开始的所有位置的字符设为 ‘9’,以确保得到最大的单调递增数。
  5. 将处理后的字符串转换为整数并返回作为结果。

代码:

class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用来标记需要修改的位置,初始化为字符串长度,防止第二个循环在未赋值的情况下执行int flag = strNum.size();// 从倒数第二位开始向前遍历for (int i = strNum.size() - 1; i > 0; i--) {// 如果当前位大于前一位,则前一位需要减一,并更新flagif (strNum[i - 1] > strNum[i]) {flag = i; // 记录需要减一的位置strNum[i - 1]--; // 前一位减一}}// 将flag位置及之后的所有位数变为9,以获得最大的单调递增数for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum); // 转换为整数并返回}
};

3监控二叉树

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

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

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

示例 1:

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

示例 2:

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


提示:

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

思路:我们要从下往上看,局部最优:让叶子节点的父节点安摄像头,所用摄像头最少,整体最优:全部摄像头数量所用最少!可以使用后序遍历也就是左右中的顺序,这样就可以在回溯的过程中从下到上进行推导了.

给定一个二叉树,节点状态有三种:未被覆盖、已被覆盖(无需额外摄像头)、已安装摄像头。目标是找出最少需要安装的摄像头数量,覆盖整棵树的所有节点。

定义递归函数 traversal,对当前节点进行处理:

  • 如果左右子树有任意一个是未被覆盖的状态(返回2),则当前节点需要安装摄像头,返回1表示当前节点已安装摄像头。
  • 如果左右子树都已被覆盖(返回0),则当前节点不需要额外的摄像头覆盖。
  • 如果左右子树有一个已安装摄像头(返回1),则当前节点被覆盖,返回0。
  1. 根节点处理: 调用 traversal 函数处理根节点。如果根节点未被覆盖(返回2),则需要额外安装一个摄像头。

  2. 终返回 result,即安装摄像头的总数量。

代码: 

class Solution {
private:int result; // 记录需要安装摄像头的数量// 递归函数,返回当前节点的状态:// 0 - 节点已被覆盖// 1 - 节点安装了摄像头// 2 - 节点未被覆盖int traversal(TreeNode* cur) {if (cur == NULL) return 2; // 空节点默认已覆盖int left = traversal(cur->left);    // 处理左子树int right = traversal(cur->right);  // 处理右子树// 如果左右子树有任意一个未被覆盖,当前节点需要安装摄像头if (left == 2 || right == 2) {result++; // 安装摄像头return 1; // 当前节点已安装摄像头}// 如果左右子树的状态都是已覆盖,当前节点不需要额外摄像头覆盖else if (left == 0 && right == 0) {return 2; // 当前节点未被覆盖} else {return 0; // 当前节点已被覆盖}}public:int minCameraCover(TreeNode* root) {result = 0; // 初始化摄像头数量为0if (traversal(root) == 2) { // 如果根节点未被覆盖,则需额外安装摄像头result++;}return result; // 返回最终需要安装的摄像头数量}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

每日练习,不要放弃

目录 题目1.下面叙述错误的是 ( )2.java如何返回request范围内存在的对象&#xff1f;3.以下代码将打印出4.下列类定义中哪些是合法的抽象类的定义&#xff1f;&#xff08;&#xff09;5.以下代码段执行后的输出结果为6.以下代码运行输出的是总结 题目 选自牛客网 1.下面叙述…

成为git砖家(1): author 和 committer 的区别

大家好&#xff0c;我是白鱼。一直对 git author 和 committer 不太了解&#xff0c; 今天通过 cherry-pick 的例子搞清楚了区别。 原理 例如我克隆了著名开源项目 spdlog 的源码&#xff0c; 根据某个历史 commit A 创建了分支&#xff0c; 然后 cherry-pick 了这个 commit …

DPU:值不值得托付下一代存储加速架构?

一、为什么需要DPU&#xff1f; 在信息爆炸的时代&#xff0c;数据处理单元&#xff08;DPU&#xff09;作为新兴的数据中心基础设施核心&#xff0c;正逐步崭露头角&#xff0c;成为提升数据处理效率、优化成本结构的关键角色。 传统的数据中心架构主要以CPU为中心&#xff…

【C#】已知有三个坐标点:P0、P1、P2,当满足P3和P4连成的一条直线 与 P0和P1连成一条直线平行且长度一致,该如何计算P3、P4?

问题描述 已知有三个坐标点&#xff1a;P0、P1、P2&#xff0c;当满足P3和P4连成的一条直线 与 P0和P1连成一条直线平行且长度一致&#xff0c;该如何计算P3、P4&#xff1f; 解决办法 思路一&#xff1a;斜率及点斜式方程 # 示例坐标 x0, y0 1, 1 # P0坐标 x1, y1 4, 4 # …

pytorch中一些最基本函数和类

1.Tensor操作 Tensor是PyTorch中最基本的数据结构&#xff0c;类似于NumPy的数组&#xff0c;但可以在GPU上运行加速计算。 示例&#xff1a;创建和操作Tensor import torch# 创建一个零填充的Tensor x torch.zeros(3, 3) print(x)# 加法操作 y torch.ones(3, 3) z x y pr…

SEO:6个避免被搜索引擎惩罚的策略-华媒舍

在当今数字时代&#xff0c;搜索引擎成为了绝大多数人获取信息和产品的首选工具。为了在搜索结果中获得良好的排名&#xff0c;许多网站采用了各种优化策略。有些策略可能会适得其反&#xff0c;引发搜索引擎的惩罚。以下是彭博社发稿推广的6个避免被搜索引擎惩罚的策略。 1. 内…

链接追踪系列-07.logstash安装json_lines插件

进入docker中的logstash 容器内&#xff1a; jelexbogon ~ % docker exec -it 7ee8960c99a31e607f346b2802419b8b819cc860863bc283cb7483bc03ba1420 /bin/sh $ pwd /usr/share/logstash $ ls bin CONTRIBUTORS Gemfile jdk logstash-core modules tools x-pack …

本地部署 EVE: Unveiling Encoder-Free Vision-Language Models

本地部署 EVE: Unveiling Encoder-Free Vision-Language Models 0. 引言1. 快速开始2. 运行 Demo 0. 引言 EVE (Encoder-free Vision-language model) 是一种创新的多模态 AI 模型&#xff0c;主要特点是去除了传统视觉语言模型中的视觉编码器。 核心创新 架构创新&#xff…

【python虚拟环境管理】【mac m3】 使用pipx安装poetry

文章目录 一. 安装 pipx二. 安装Poetry1. 安装2. advanced 操作 官网文档&#xff1a;https://python-poetry.org/docs/ pipx介绍文档&#xff1a;https://blog.51cto.com/u_15064632/2570626 一. 安装 pipx pipx 用于全局安装 Python 命令行应用程序&#xff0c;同时在虚拟环…

[ACM独立出版] 2024年虚拟现实、图像和信号处理国际学术会议(VRISP 2024,8月2日-4)

2024年虚拟现实、图像和信号处理国际学术会议&#xff08;VRISP 2024&#xff09;将于2024年8月2-4日在中国厦门召开。 VRISP 2024将围绕“虚拟现实、图像和信号处理”的最新研究领域&#xff0c;为来自国内外高等院校、科学研究所、企事业单位的专家、教授、学者、工程师等提供…

二次开发源码 借贷系统uniapp/借贷认证系统/小额信贷系统/工薪贷APP/资金贷系统h5

前端&#xff1a;UNIAPP 后端&#xff1a;ThinkPHP 数据库&#xff1a; Mysql 前端使用的uniapp 可以打包APP H5 小程序 系统提供了完善的网络借贷体系&#xff0c;为金融中介平台提供从获客到贷后管理全流程服务&#xff0c;解决了借贷手续繁琐、流程缓慢等问题 此源码为运营…

解决一下git clone失败的问题

1&#xff09;.不开梯子&#xff0c;我们用https克隆 git clone https://github.com 报错&#xff1a; Failed to connect to github.com port 443 after 2091 ms: Couldnt connect to server 解决办法&#xff1a; 开梯子&#xff0c;然后# 注意修改成自己的IP和端口号 gi…

el-table的selection多选表格改为单选

需求场景: 选择表格数据时&#xff0c;需要控制单条数据的操作按钮是否禁用。 效果图: html代码: <div><el-tableref"multipleTable":data"tableData"tooltip-effect"dark"style"width: 100%"selection-change"handl…

【笔记】nginx命令

查看 启动 通过./nginx启动nginx之后 可以在虚拟机中进入/usr/local/nginx/html 去查看cat index.html 也就是此页面的源代码 进入vim /etc/profile 配置完之后保存退出 source /etc/profile 手动重载资源 随后就可以在任意位置重载资源了 nginx -s reload 部署静态资源就把静…

el-table表格操作列错行处理

解决方法&#xff1a; <style>::v-deep .el-table th.el-table__cell > .cell {white-space: nowrap !important;} </style>

IDEA启动Web项目总是提示端口占用

文章目录 IDEA启动Web项目总是提示端口占用一、前言1.场景2.环境 二、正文1.场景一:真端口占用2. 场景二:假端口占用 IDEA启动Web项目总是提示端口占用 一、前言 1.场景 IDEA启动Web项目总是提示端口占用&#xff1a; 确实是端口被占用&#xff0c;比如&#xff1a;没有正常…

在GPU上运行PyTorch

文章目录 1、查看GPU的CUDA版本2、下载CUDA版本3、安装cuDNN4、配置CUDA环境变量5、安装配置Anaconda6、使用Anaconda7、pycharm导入虚拟环境8、安装带GPU的PyTorch⭐9、总结 &#x1f343;作者介绍&#xff1a;双非本科大三网络工程专业在读&#xff0c;阿里云专家博主&#x…

2024.7.16日 最新版 docker cuda container tookit下载!

nvidia官方指导 https://docs.nvidia.com/datacenter/cloud-native/container-toolkit/latest/install-guide.html 其实就是这几个命令&#xff0c;但是有墙&#xff1a; curl -fsSL https://nvidia.github.io/libnvidia-container/gpgkey | sudo gpg --dearmor -o /usr/shar…

SpringBoot3.3.0升级方案

本文介绍了由SpringBoot2升级到SpringBoot3.3.0升级方案&#xff0c;新版本的升级可以解决旧版本存在的部分漏洞问题。 一、jdk17下载安装 1、下载 官网下载地址 Java Archive Downloads - Java SE 17 Jdk17下载后&#xff0c;可不设置系统变量java_home&#xff0c;仅在id…

【C++】类和对象的基本概念与使用

本文通过面向对象的概念以及通俗易懂的例子介绍面向对象引出类和对象。最后通过与之有相似之处的C语言中的struct一步步引出C中的类的定义方式&#xff0c;并提出了一些注意事项&#xff0c;最后描述了类的大小的计算方法。 一、什么是面向对象&#xff1f; 1.面向对象的概念 …