一刷代码随想录(贪心5)

56. 合并区间

题意:

给出一个区间的集合,请合并所有重叠的区间。

示例 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] 可被视为重叠区间。
  • 注意:输入类型已于2019年4月15日更改。 请重置默认代码定义以获取新方法签名。

解法:同之前的三道题,主要是判断区间是否重叠,可以首先将第一个区间存入结果,判断重叠就更新右边界即可,由于是按左边界排序的,那么存入结果数组的左边界必然是最小的不用更新。

代码:

class Solution {
public:vector<vector<int>> merge(vector<vector<int>>& intervals) {vector<vector<int>> result;if (intervals.size() == 0) return result; // 区间集合为空直接返回// 排序的参数使用了lambda表达式sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b){return a[0] < b[0];});// 第一个区间就可以放进结果集里,后面如果重叠,在result上直接合并result.push_back(intervals[0]); for (int i = 1; i < intervals.size(); i++) {if (result.back()[1] >= intervals[i][0]) { // 发现重叠区间// 合并区间,只更新右边界就好,因为result.back()的左边界一定是最小值,因为我们按照左边界排序的result.back()[1] = max(result.back()[1], intervals[i][1]); } else {result.push_back(intervals[i]); // 区间不重叠 }}return result;}
};

求最大整数

题意:

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

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

示例 1:

  • 输入: N = 10
  • 输出: 9

示例 2:

  • 输入: N = 1234
  • 输出: 1234

示例 3:

  • 输入: N = 332
  • 输出: 299

说明: N 是在 [0, 10^9] 范围内的一个整数。

解法:要求是单调递增还要求最大,那么若发现高位低于低位,将高位减一,低位就可以赋为9,这样让这一小部分达到最大,按照贪心思路,一步步往下做即可,就会退出全局最优,遍历应该从低位到高位,否则可能导致,判断好的位置又因为下面的变化改成了不符合题意的情况,因为从前往后遍历会导致下一个值变小,会破坏其递增条件。

代码:

class Solution {
public:int monotoneIncreasingDigits(int N) {string strNum = to_string(N);// flag用来标记赋值9从哪里开始// 设置为这个默认值,为了防止第二个for循环在flag没有被赋值的情况下执行int flag = strNum.size();for (int i = strNum.size() - 1; i > 0; i--) {if (strNum[i - 1] > strNum[i] ) {flag = i;strNum[i - 1]--;}}for (int i = flag; i < strNum.size(); i++) {strNum[i] = '9';}return stoi(strNum);}
};

968.监控二叉树

题意:

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

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

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

示例 1:

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

示例 2:

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

解法:将摄像头放在两个节点中间,从叶子节点的父节点开始,每隔开两个放一个摄像头即可,最后还要判断头结点并放摄像头,由于要从叶子节点开始,因此应该使用后序遍历以满足条件,同时对于每个节点都有三种情况,覆盖、摄像头、没有覆盖。通过左右孩子的状态判断属于那种情况,并返回对应的数字即可.

代码:

// 版本一
class Solution {
private:int result;int traversal(TreeNode* cur) {// 空节点,该节点有覆盖if (cur == NULL) return 2;int left = traversal(cur->left);    // 左int right = traversal(cur->right);  // 右// 情况1// 左右节点都有覆盖if (left == 2 && 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 || right == 0) {result++;return 1;}// 情况3// left == 1 && right == 2 左节点有摄像头,右节点有覆盖// left == 2 && right == 1 左节点有覆盖,右节点有摄像头// left == 1 && right == 1 左右节点都有摄像头// 其他情况前段代码均已覆盖if (left == 1 || right == 1) return 2;// 以上代码我没有使用else,主要是为了把各个分支条件展现出来,这样代码有助于读者理解// 这个 return -1 逻辑不会走到这里。return -1;}public:int minCameraCover(TreeNode* root) {result = 0;// 情况4if (traversal(root) == 0) { // root 无覆盖result++;}return result;}
};

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

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

相关文章

windows子系统wsl完成本地化设置locale,LC_ALL

在 Windows 的子系统 Linux&#xff08;WSL&#xff09;环境中&#xff0c;解决本地化设置问题可以采取以下步骤&#xff1a; 1. **检查本地化设置**&#xff1a; 打开你的 WSL 终端&#xff08;比如 Ubuntu、Debian 等&#xff09;&#xff0c;运行以下命令来查看当前的本…

51单片机和STM32区别

51单片机和 STM32 区别 51单片机和 STM32 是两种常见的微控制器&#xff0c;它们在架构、性能、外设接口、功耗和开发环境等方面有所不同。 1. 架构差异 51单片机基于传统的哈佛总线结构&#xff0c;采用 CISC 架构&#xff0c;而 STM32 基于 ARM Cortex-M 系列的32位处理器核…

CRMEB-众邦科技 使用笔记

1.启动项目报错 Unable to load authentication plugin ‘caching_sha2_password’. 参考&#xff1a;http://t.csdnimg.cn/5EqaE 解决办法&#xff1a;升级mysql驱动 <dependency><groupId>mysql</groupId><artifactId>mysql-connector-java</ar…

【天机学堂】面试总结

写在前面&#xff0c;首先要将天机学堂包装一下&#xff0c;智慧教育平台》&#xff0c;暂时就想到这个。天机学堂文档 1.包装简历 待更新。。。

【iOS】iOS内存五大分区

iOS内存五大分区 总揽 iOS中&#xff0c;内存主要分为五大区域&#xff1a;栈区&#xff0c;堆区&#xff0c;全局区/静态区&#xff0c;常量区和代码区。总览图如下。 这个图我觉得更好记&#xff0c;因为下面是低地址&#xff0c;上面是高地址&#xff0c;是比较符合日常…

堆的实现-向上调整算法-向下调整算法-堆排序-TopK问题 C语言

一、堆的概念及结构 二、 向上调整算法 注意:循环条件不可写parent > 0 //向上调整算法 //child为下标 void adjustup(int* a, int child) {int parent (child - 1) / 2;while (child > 0){if (a[child] < a[parent]){swap(&a[child], &a[parent]);child pa…

CoderGuide

CoderGuide是一个针对同学们前后端求职面试的开源项目&#xff0c;作为一名互联网/IT从业人员&#xff0c;经常需要搜索一些书籍、面试题等资源&#xff0c;在这个过程中踩过很多坑、浪费过很多时间。欢迎大家 Watch、Star&#xff0c;供各位同学免费使用&#xff0c;永不收费&…

Spring框架 配置Gateway网关/spring cloud gateway 基础入门案例教程

文章目录 目录 文章目录 安装流程 小结 概要安装流程技术细节小结 概要 网关作为微服务集群唯一的对外入口,可以实现很多功能. 例如: 统一的解决跨域(一个ajax请求 origin域名和请求目标url中域名不同,ip不同,域名不同,端口不同,都会引发的问题)问题. 统一的身份认证.认证解…

C++ 关键字与库函数 学习总结

sizeof与strlen 含义 sizeof&#xff1a;是一个操作符&#xff0c;用于计算数据类型或变量的大小&#xff08;以字节为单位&#xff09;。在编译时求值strlen&#xff1a; 是一个函数&#xff0c;用于计算字符串的长度&#xff08;不包括终止符 \0&#xff09;。在运行时求值不…

考研数学|保100冲130暑假强化保姆级规划

只做这些的话还不够&#xff0c;还要加上真题、模拟题。而且必须确保自己完全掌握上面的内容。 只看30讲和做1000题考90分是比较有困难的。如果刷完知能行1000题&#xff0c;90分应该很稳。 张宇1000题是考研数学难度较大一些的题集&#xff0c;题目难&#xff0c;计算量大&a…

机器学习笔记 - RAFT 光流简读

一、光流 光流是图像序列中像素的表观运动。为了估计光流,场景中物体的移动必须具有相应的亮度位移。这意味着一个图像中移动的红球在下一个图像中应该具有相同的亮度和颜色,这使我们能够确定它以像素为单位移动了多少。下图显示了光流示例,其中一系列图像捕获了逆时针旋转的…

增加一个按钮,批量获取凭证号

create PROCEDURE Cux_Ar_ServiceLedger_Voucher_ProcOrgId Int ,result Int output AS BEGIN SET NOCOUNT ONDECLARE Date DATETIME IF OrgId 0 or OrgIdBEGIN RAISERROR(N获取当前组织ID失败&#xff01;, 16, 1) RETURNEND SET Date GETDATE()BEGIN TRANSACTION BEGIN…

微调(一)

微调有两种办法&#xff0c; 一是模型全部参数的微调&#xff0c;二是少量参数高效的微调。前者由于参数多&#xff0c;需要的GPU多&#xff0c;并且全参数微调可能把模型带偏&#xff0c;后者只需要微调少量参数&#xff0c;需要的GPU少&#xff0c;还可能达到不错的效果&…

秒懂Linux之自动化构建工具-make/Makefile

目录 一.前文摘要 二.make/Makefile 一.前文摘要 在学习自动化构建工具前我们先来补充一下动静态库的相关指令 动态库指令 gcc -o 文件&#xff08;重命名&#xff09; 源文件 静态库指令 gcc -o 文件&#xff08;重命名&#xff09; 源文件 -static 二.make/Makefile 怎么形…

MATLAB(14)预处理

一、前言 在MATLAB中进行插值拟合、主成分分析&#xff08;PCA&#xff09;和小波分析之前&#xff0c;通常需要对数据进行一些预处理。这些预处理步骤可能包括数据清洗、缺失值处理、标准化或归一化等。下面我将分别为这三种分析方法提供预处理模型的示例代码。 二、实现 1.…

校园点餐系统

1 项目介绍 1.1 摘要 在这个被海量信息淹没的数字化时代&#xff0c;互联网技术以惊人的速度迭代&#xff0c;信息的触角无处不在&#xff0c;社会的脉动随之加速。每一天&#xff0c;我们都被汹涌而至的数据浪潮包裹&#xff0c;生活在一个全方位的数字信息矩阵中。互联网的…

大模型微调实战项目总结(非常详细)零基础入门到精通,收藏这一篇就够了

写在前面 不知不觉之间&#xff0c;距开源ChatGLM-Finetuning项目已经过去了8个月。大模型也在飞速的发展&#xff0c;开源社区也是越来越活跃&#xff0c;开源模型越来越多。 中间更新过一次&#xff0c;将代码重构让大家更容易理解&#xff0c;本次更新主要增加ChatGLM3模型…

JavaScript (十)——JavaScript 比较 和 逻辑运算符

目录 JavaScript 比较 和 逻辑运算符 比较运算符 如何使用 逻辑运算符 条件运算符 语法 JavaScript 比较 和 逻辑运算符 比较和逻辑运算符用于测试 true 或者 false 比较运算符 比较运算符在逻辑语句中使用&#xff0c;以测定变量或值是否相等。 如何使用 可以在条件语…

【C++】模拟实现list

&#x1f984;个人主页:修修修也 &#x1f38f;所属专栏:数据结构 ⚙️操作环境:Visual Studio 2022 目录 一.了解项目及其功能 &#x1f4cc;了解list官方标准 了解模拟实现list &#x1f4cc;了解更底层的list实现 二.list迭代器和vector迭代器的异同 &#x1f4cc;迭代…