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

算法通关村第十七关:白银挑战-贪心高频问题

白银挑战-贪心高频问题

1. 区间问题

所有的区间问题,参考下面这张图

在这里插入图片描述

1.1 判断区间是否重叠

LeetCode252
https://leetcode.cn/problems/meeting-rooms/

思路分析

因为一个人在同一时刻只能参加一个会议,因此题目的本质是判断是否存在重叠区间

  1. 将区间按照会议开始时间进行排序
  2. 然后遍历一遍判断后面的会议开始的时候是否前面的还没有结束
  3. 如果出现重叠,返回false

代码实现

class Solution:def canAttendMeetings(self, intervals: List[List[int]]) -> bool:intervals.sort(key=lambda x: x[0])for i in range(1, len(intervals)):if intervals[i][0] < intervals[i - 1][1]:return Falsereturn True
class Solution:def canAttendMeetings(self, intervals: List[List[int]]) -> bool:intervals.sort(key=lambda x: x[0])return all(intervals[i][0] >= intervals[i - 1][1] for i in range(1, len(intervals)))

1.2 合并区间

LeetCode 56
https://leetcode.cn/problems/merge-intervals/

思路分析

  1. 首先对区间按照起始端点进行升序排序
  2. 然后逐个判断当前区间是否与前一个区间重叠
    如果不重叠,直接加入结果集
    如果重叠,将当前区间与前一个区间进行合并

区间合并
区间1,区间2 合并

[ 区间1起始时间,max(区间1结束时间,区间2结束时间) ]

代码实现

class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key=lambda x: x[0])merged = []for interval in intervals:# 合并列表为空if not merged:merged.append(interval)# 当前区间与上一区间不重叠elif interval[0] > merged[-1][1]:merged.append(interval)# 当前区间与上一区间重叠,需要合并else:# 区间合并操作merged[-1][1] = max(merged[-1][1], interval[1])return merged

1.3 插入区间

LeetCode57
https://leetcode.cn/problems/insert-interval/

思路分析

区间已经按照起始端点升序排序,我们直接遍历区间列表,寻找新区间的插入位置即可

  1. 将新区间左边且相离的区间加入结果集
  2. 接着判断当前区间是否与新区间重叠
    重叠,进行合并,直到遍历到当前区间在新区间右边且相离,加入合并后区间
    不重叠,直接加入新区间
  3. 将新区间右边且相离的区间加入结果集

代码实现

class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:inserted = []index = 0n = len(intervals)# 将新区间左边且相离的区间加入结果集while index < n and intervals[index][1] < newInterval[0]:inserted.append(intervals[index])index += 1# 接着判断当前区间是否与新区间重叠# 重叠,进行合并,直到遍历到当前区间在新区间右边且相离,加入合并后区间# 不重叠,直接加入新区间while index < n and intervals[index][0] <= newInterval[1]:newInterval[0] = min(newInterval[0], intervals[index][0])newInterval[1] = max(newInterval[1], intervals[index][1])index += 1inserted.append(newInterval)# 将新区间右边且相离的区间加入结果集while index < n:inserted.append(intervals[index])index += 1return inserted
class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) -> List[List[int]]:inserted = []index = 0n = len(intervals)while index < n:if intervals[index][1] < newInterval[0]:inserted.append(intervals[index])index += 1elif intervals[index][0] <= newInterval[1]:newInterval[0] = min(newInterval[0], intervals[index][0])newInterval[1] = max(newInterval[1], intervals[index][1])index += 1else:breakinserted.append(newInterval)inserted.extend(intervals[index:])return inserted

2. 字符串分割

LeetCode763
https://leetcode.cn/problems/partition-labels/

思路分析

需要把同一个字母圈在同一个区间里

该遍历过程相当于要找每一个字母的边界,如果找到之前遍历过的所有字母的最远边界,说明这个边界就是分割点了。此时前面出现过所有字母,最远也就到这个边界了。

具体做法

  1. 统计每一个字符最后出现的位置
  2. 从头遍历字符,并更新字符最远出现下标,如果找到字符最远出现位置下标和当前下标相等,则找到了分割点

在这里插入图片描述

代码实现

class Solution:def partitionLabels(self, s: str) -> List[int]:ans = []# 第一轮遍历,统计每一个字符最后出现的位置char_dict = {}for i in range(len(s)):char_dict[s[i]] = i# 第二轮遍历begin_index = -1char_far_index = 0for i in range(len(s)):char_far_index = max(char_far_index, char_dict[s[i]])if char_far_index == i:ans.append(i - begin_index)begin_index = ireturn ans
class Solution:def partitionLabels(self, s: str) -> List[int]:last = [0] * 26for i, char in enumerate(s):last[ord(char) - ord('a')] = ipartition = list()start, end = 0, 0for i, char in enumerate(s):end = max(end, last[ord(char) - ord('a')])if i == end:partition.append(end - start + 1)start = end + 1return partition

3. 加油站问题

LeetCode134
https://leetcode.cn/problems/gas-station/

思路分析

很容易想到暴力解法,从第一站开始尝试。缺点就是需要大量的重复计算

在这里插入图片描述

优化:
总油量 - 总消耗 ≥ 0,可以跑完一圈,具体到每一段就是各个加油站的剩油量 rest[i] 相加一定是大于等于0的

  • 每个加油站剩油量 rest[i] = gas[i] - cost[i]
  • i从0开始累加 rest[i] ,得到当前油量 curSum
  • 一旦curSum小于0,说明[0, i]区间都不能作为起始位置,起始位置必须从i+1开始重新算,只有这样才能保证有可能完成

复杂度降低:从O(n^2)降低到O(n)

在这里插入图片描述

代码实现


class Solution:def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:total_sum = 0cur_sum = 0start = 0for i in range(len(gas)):cur_sum += gas[i] - cost[i]total_sum += gas[i] - cost[i]# 当前累加rest[i]和 cur_sum小于0if cur_sum < 0:# 更新起始位置为 i+1start = i+1# cur_sum从 0 开始cur_sum = 0return -1 if total_sum < 0 else start

相关文章:

算法通关村第十七关:白银挑战-贪心高频问题

白银挑战-贪心高频问题 1. 区间问题 所有的区间问题&#xff0c;参考下面这张图 1.1 判断区间是否重叠 LeetCode252 https://leetcode.cn/problems/meeting-rooms/ 思路分析 因为一个人在同一时刻只能参加一个会议&#xff0c;因此题目的本质是判断是否存在重叠区间 将区…...

目标检测评估指标mAP:从Precision,Recall,到AP50-95

1. TP, FP, FN, TN True Positive 满足以下三个条件被看做是TP 1. 置信度大于阈值&#xff08;类别有阈值&#xff0c;IoU判断这个bouding box是否合适也有阈值&#xff09; 2. 预测类型与标签类型相匹配&#xff08;类别预测对了&#xff09; 3. 预测的Bouding Box和Ground …...

七大排序算法

目录 直接插入排序 希尔排序 直接选择排序 堆排序 冒泡排序 快速排序 快速排序优化 非递归实现快速排序 归并排序 非递归的归并排序 排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作. 常见的排序算法有插入排序(直接插入…...

GitHub two-factor authentication

1. 介绍 登录 GitHub 官网&#xff0c;会提示要开启双因子认证。 但推荐的 APP 都是国外了&#xff0c;国内用不了。 可以使用 “腾讯身份验证器” 微信小程序。 2. 操作 开启双因子认证&#xff1a; 打开 “腾讯身份验证器” 微信小程序&#xff0c;扫描 GitHub 那个二维…...

un-app-手机号授权登录-授权框弹不出情况

前言 手机号授权是获取用户信息api停用之后&#xff0c;经常使用的api。但是此api也是有很多坑 手机号授权会出现调用不起来的情况&#xff0c;这是因为小程序后台没有进行微信认证导致的 手机号授权调用不起来-没有微信认证 来到小程序后台-设置-基本设置-下拉找到微信认证…...

手写Spring:第14章-自动扫描Bean对象注册

文章目录 一、目标&#xff1a;自动扫描Bean对象注册二、设计&#xff1a;自动扫描Bean对象注册三、实现&#xff1a;自动扫描Bean对象注册3.0 引入依赖3.1 工程结构3.2 Bean生命周期中自动加载包扫描注册Bean对象和设置占位符属性类图3.3 主力占位符配置3.4 定义拦截注解3.4.1…...

redux中间件的简单讲解

redux中间件 中间件的作用&#xff1a; 就是在 源数据 到 目标数据 中间做各种处理&#xff0c;有利于程序的可拓展性&#xff0c;通常情况下&#xff0c;一个中间件就是一个函数&#xff0c;且一个中间件最好只做一件事情 数据源 --------> 中间件 --------> 中间件 -…...

嵌入式开发-绪论

目录 一.什么是嵌入式 1.1硬件系统 1.2软件系统 二.嵌入式应用场景 2.1消费电子 2.1.1智能家居 2.1.2影音 2.1.3家用电器 2.1.4玩具游戏机 2.2通信领域 2.2.1对讲机 2.2.2手机 2.2.3卫星 2.2.4雷达 2.3控制领域 2.3.1机器人 2.3.2采集器PLC 2.4金融 2.4.1POS…...

大数据知识合集之预处理方法

数据预处理方法主要有&#xff1a; 数据清洗、数据集成、数据规约和数据变换。 1、数据清洗 数据清洗(data cleaning) &#xff1a;是通过填补缺失值、光滑噪声数据&#xff0c;平滑或删除离群点&#xff0c;纠正数据的不一致来达到清洗的目的。 缺失值处理 实际开发获取信…...

mysql(九)mysql主从复制

目录 前言概述提出问题主从复制的用途工作流程 主从复制的配置创建复制账号配置主库和从库启动主从复制从另一个服务器开始主从复制主从复制时推荐的配置sync_binloginnodb_flush_logs_at_trx_commitinnodb_support_xa1innodb_safe_binlog 主从复制的原理基于语句复制优点&…...

nodejs采集淘宝、天猫网商品详情数据以及解决_m_h5_tk令牌及sign签名验证(2023-09-09)

一、淘宝、天猫sign加密算法 淘宝、天猫对于h5的访问采用了和APP客户端不同的方式&#xff0c;由于在h5的js代码中保存appsercret具有较高的风险&#xff0c;mtop采用了随机分配令牌的方式&#xff0c;为每个访问端分配一个token&#xff0c;保存在用户的cookie中&#xff0c;通…...

虚拟机上部署K8S集群

虚拟机上部署K8S集群 安装VM Ware安装Docker安装K8S集群安装kubeadm使用kubeadm引导集群 安装VM Ware 参考&#xff1a;http://www.taodudu.cc/news/show-2034573.html?actiononClick 安装Docker 参考&#xff1a;https://www.yuque.com/leifengyang/oncloud/mbvigg#2ASxH …...

设计模式 - 责任链

一、前言 ​ 相信大家平时或多或少都间接接触过责任链设计模式&#xff0c;只是可能有些同学自己不知道此处用的是该设计模式&#xff0c;比如说 Java Web 中的 Filter 过滤器&#xff0c;就是非常经典的责任链设计模式的例子。 那么什么是责任链设计模式呢&#xff1f; ​ …...

【小沐学Unity3d】3ds Max 骨骼动画制作(CAT、Character Studio、Biped、骨骼对象)

文章目录 1、简介2、 CAT2.1 加载 CATRig 预设库2.2 从头开始创建 CATRig 3、character studio3.1 基本描述3.2 Biped3.3 Physique 4、骨骼系统4.1 创建方法4.2 简单示例 结语 1、简介 官网地址&#xff1a; https://help.autodesk.com/view/3DSMAX/2018/CHS https://help.aut…...

CUDA说明和安装[window]

文章目录 1、查看版本信息查看GPU查看cuda版本其他方法 2区分 了解cudaCUDA ToolkitNVCCcuDNN 3/ 安装过程4/版本的问题CUDA Toolkit和 显卡驱动 的版本对应CUDA / CUDA Toolkit和cuDNN的版本对应 5/关于CUDA和Cudnn**5.1 CUDA的命名规则****5.2 如何查看自己所安装的CUDA的版本…...

sqlserver2012性能优化配置:设置性能相关的服务器参数

前言 sqlserver2012 长时间运行的话会将服务器的内存占满 解决办法 通过界面设置 下图中设置最大服务器内存 通过执行脚本设置 需要先开发开启高级选项配置才能设置成功 设置完成之后将高级选择配置关闭&#xff0c;还原成跟之前一样 --可以配置高级选项 EXEC sp_conf…...

介绍 dubbo-go 并在Mac上安装,完成一次自己定义的接口RPC调用

目录 RPC 远程调用的说明作用&#xff1a;像调用本地方法一样调用远程方法和直接HTTP调用的区别&#xff1a;调用模型图示&#xff1a; Dubbo 框架说明Dubbo Go 介绍应用 Dubbo Go环境安装&#xff08;Mac 系统&#xff09;安装 Go语言环境安装 序列化工具protoc安装 dubbogo-c…...

目标检测数据集:摄像头成像吸烟检测数据集(自己标注)

1.专栏介绍 ✨✨✨✨✨✨目标检测数据集✨✨✨✨✨✨ 本专栏提供各种场景的数据集,主要聚焦:工业缺陷检测数据集、小目标数据集、遥感数据集、红外小目标数据集,该专栏的数据集会在多个专栏进行验证,在多个数据集进行验证mAP涨点明显,尤其是小目标、遮挡物精度提升明显的…...

Unity的UI管理器

1、代码 public class UIManager {private static UIManager instance new UIManager();public static UIManager Instance > instance;//存储显示着的面板脚本&#xff08;不是面板Gameobject&#xff09;&#xff0c;每显示一个面板就存入字典//隐藏的时候获取字典中对…...

Mp4文件提取详细H.264和MP3文件

文章目录 Mp4文件提取为H.264和MP3文件**提取视频为H.264&#xff1a;****提取音频为MP3&#xff1a;** 点赞收藏加关注&#xff0c;追求技术不迷路&#xff01;&#xff01;&#xff01;欢迎评论区互动。 Mp4文件提取为H.264和MP3文件 要将视频分开为H.264&#xff08;视频编…...

Qt应用程序连接达梦数据库-飞腾PC麒麟V10

目录 前言1 安装ODBC1.1 下载unixODBC源码1.2 编译安装1.4 测试 2 编译QODBC2.1 修改 qsqldriverbase.pri 文件2.2 修改 odbc.pro 文件2.3 编译并安装QODBC 3 Qt应用程序连接达梦数据库测试4 优化ODBC配置&#xff0c;方便程序部署4.1 修改pro文件&#xff0c;增加DESTDIR 变量…...

2023-09-03 LeetCode每日一题(消灭怪物的最大数量)

2023-09-03每日一题 一、题目编号 1921. 消灭怪物的最大数量二、题目链接 点击跳转到题目位置 三、题目描述 你正在玩一款电子游戏&#xff0c;在游戏中你需要保护城市免受怪物侵袭。给你一个 下标从 0 开始 且长度为 n 的整数数组 dist &#xff0c;其中 dist[i] 是第 i …...

绘图 | MATLAB

目的语法注意事项图片中出现网格grid on放在plot后面在同一图片中绘制多个图例hold on在图形中添加图例legend LineSpec 线性 线型描述线型描述" - "实线" : "点线" - - "虚线" -. "点划线 标记 标记描述标记描述“o”圆圈“squa…...

2023年下半年高项考试学习计划

之前总结 2023年上半年的考试&#xff0c;对于我自己&#xff0c;就是虎头蛇尾&#xff0c;也谈不上太过自信&#xff0c;好好学习了一段时间之后&#xff0c;也就是不再发博文&#xff0c;截止到2022年11月的时候&#xff0c;自己就算是放弃了&#xff0c;没有再主动学习。 结…...

SpringBoot中CommandLineRunner的使用

开发中&#xff0c;你有没有遇到这样的场景&#xff0c;项目启动后&#xff0c;立即需要进行一些操作。比如&#xff1a;加载一些初始化数据、执行一段逻辑代码。你可以使用SpringBoot中CommandLineRunner。它可以在项目启动后&#xff0c;执行CommandLineRunner接口实现类的相…...

<OpenCV> Mat属性

OpenCV的图像数据类型可参考之前的博客&#xff1a;https://blog.csdn.net/thisiszdy/article/details/120238017 OpenCV-Mat类型的部分属性如下&#xff1a; size&#xff1a;矩阵的大小&#xff0c; s i z e ( c o l s , r o w s ) size(cols,rows) size(cols,rows)&#xf…...

LAMP 综合实验

LAMP 综合实验 一.实验目标 实验目标如下&#xff1a; 实现 LAMP 架构 实现数据库主从复制 实现 NFS 服务器存储 wordpress 文件 实现备份服务器实时备份 NFS 服务器文件 实现日志集中存储 实现 loganalyzer 分析展示日志 二.实验准备 2.1 实验环境 实验环境: 虚拟机版本: VM…...

JavaScript发展历程

目录 一、起源&#xff08;1995-1997&#xff09; 二、发展&#xff08;1997-2005&#xff09; 三、进化——Ajax与Web 2.0&#xff08;2005-2010年&#xff09; 四、移动互联网与现代化&#xff08;2010年至今&#xff09; 结论 JavaScript是一种广泛使用的网络编程语言&…...

LP(六十九)智能文档助手升级

本文在笔者之前研发的大模型智能文档问答项目中&#xff0c;开发更进一步&#xff0c;支持多种类型文档和URL链接&#xff0c;支持多种大模型接入&#xff0c;且使用更方便、高效。 项目介绍 在文章NLP&#xff08;六十一&#xff09;使用Baichuan-13B-Chat模型构建智能文档中…...

VIM统计搜索关键词命令

:%s/./&/gn 统计字符数 :%s/\i\/&/gn 统计单词数 :%s/^//n 统计行数 :%s/keyword/&/g 统计任何地方出现的 "keyword" :%s/keyword/&/gn 统计任何地方出现的 "keyword" :%s/keyword/&#xff1a;这部分是 Vi…...