【代码随想录训练营】【Day 38】【贪心-5】| Leetcode 435, 763, 56

2024-06-03 03:12

本文主要是介绍【代码随想录训练营】【Day 38】【贪心-5】| Leetcode 435, 763, 56,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

【代码随想录训练营】【Day 38】【贪心-5】| Leetcode 435, 763, 56

需强化知识点

  • 重叠区间系列 题, 763, 435

题目

435. 无重叠区间

  • 左起点排序,记录重叠区间个数,总数相减即为结果,过程中维护右边界
  • 注意:出现重叠区域时,右边界取最小值,即保留更靠左的区间,来使得后面区间更有可能不重合,从而移除次数最少
class Solution:def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:intervals.sort(key = lambda x: x[0])times = 0sr = intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] >= sr:sr = intervals[i][1]else:times += 1sr = min(sr, intervals[i][1])return times

763. 划分字母区间

  • 思路:记录每个字母出现的最大位置,然后再次遍历,当遇到 i == 最大位置时,则可以切分一次
class Solution:def partitionLabels(self, s: str) -> List[int]:label_index = [-1] * 26result = []max_right = -1start_index = 0for i, c in enumerate(s):label_index[ord(c) - ord('a')] = max(label_index[ord(c) - ord('a')], i)for i , c in enumerate(s):max_right = max(max_right, label_index[ord(c) - ord('a')])if i == max_right:result.append(i - start_index + 1)start_index = i+1return result

56. 合并区间

  • 思路:遇到重叠进行合并,遇到不重叠,保存之前区间
class Solution:def merge(self, intervals: List[List[int]]) -> List[List[int]]:intervals.sort(key = lambda x: x[0])result = []sl, sr = intervals[0][0], intervals[0][1]for i in range(1, len(intervals)):if intervals[i][0] <= sr:sr = max(sr, intervals[i][1])else:result.append([sl, sr])sl, sr = intervals[i][0], intervals[i][1]result.append([sl, sr])return result

这篇关于【代码随想录训练营】【Day 38】【贪心-5】| Leetcode 435, 763, 56的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1025871

相关文章

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素(O(1)) 当我们要频繁的查找某个元素,第一哈希表O(1),第二,二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储,只要开26个c

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

usaco 1.3 Barn Repair(贪心)

思路:用上M块木板时有 M-1 个间隙。目标是让总间隙最大。将相邻两个有牛的牛棚之间间隔的牛棚数排序,选取最大的M-1个作为间隙,其余地方用木板盖住。 做法: 1.若,板(M) 的数目大于或等于 牛棚中有牛的数目(C),则 目测 给每个牛牛发一个板就为最小的需求~ 2.否则,先对 牛牛们的门牌号排序,然后 用一个数组 blank[ ] 记录两门牌号之间的距离,然后 用数组 an

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

day-51 合并零之间的节点

思路 直接遍历链表即可,遇到val=0跳过,val非零则加在一起,最后返回即可 解题过程 返回链表可以有头结点,方便插入,返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*

poj 3190 优先队列+贪心

题意: 有n头牛,分别给他们挤奶的时间。 然后每头牛挤奶的时候都要在一个stall里面,并且每个stall每次只能占用一头牛。 问最少需要多少个stall,并输出每头牛所在的stall。 e.g 样例: INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 2976 分数规划二分贪心(部分对总体的贡献度) poj 3111

poj 2976: 题意: 在n场考试中,每场考试共有b题,答对的题目有a题。 允许去掉k场考试,求能达到的最高正确率是多少。 解析: 假设已知准确率为x,则每场考试对于准确率的贡献值为: a - b * x,将贡献值大的排序排在前面舍弃掉后k个。 然后二分x就行了。 代码: #include <iostream>#include <cstdio>#incl

计算机毕业设计 大学志愿填报系统 Java+SpringBoot+Vue 前后端分离 文档报告 代码讲解 安装调试

🍊作者:计算机编程-吉哥 🍊简介:专业从事JavaWeb程序开发,微信小程序开发,定制化项目、 源码、代码讲解、文档撰写、ppt制作。做自己喜欢的事,生活就是快乐的。 🍊心愿:点赞 👍 收藏 ⭐评论 📝 🍅 文末获取源码联系 👇🏻 精彩专栏推荐订阅 👇🏻 不然下次找不到哟~Java毕业设计项目~热门选题推荐《1000套》 目录 1.技术选型 2.开发工具 3.功能

代码随想录冲冲冲 Day39 动态规划Part7

198. 打家劫舍 dp数组的意义是在第i位的时候偷的最大钱数是多少 如果nums的size为0 总价值当然就是0 如果nums的size为1 总价值是nums[0] 遍历顺序就是从小到大遍历 之后是递推公式 对于dp[i]的最大价值来说有两种可能 1.偷第i个 那么最大价值就是dp[i-2]+nums[i] 2.不偷第i个 那么价值就是dp[i-1] 之后取这两个的最大值就是d

pip-tools:打造可重复、可控的 Python 开发环境,解决依赖关系,让代码更稳定

在 Python 开发中,管理依赖关系是一项繁琐且容易出错的任务。手动更新依赖版本、处理冲突、确保一致性等等,都可能让开发者感到头疼。而 pip-tools 为开发者提供了一套稳定可靠的解决方案。 什么是 pip-tools? pip-tools 是一组命令行工具,旨在简化 Python 依赖关系的管理,确保项目环境的稳定性和可重复性。它主要包含两个核心工具:pip-compile 和 pip