Day36|贪心算法part05:435. 无重叠区间、763.划分字母区间、56. 合并区间

435. 无重叠区间

有了上题射气球的因子,这题也就有思路了,反正无脑排序就行了:

  • 首先将所有区间按照end的大小从小到大排序;
  • 选取最早end为起始x_end
  • 遍历所有区间,如果该区间的start比end大(可重叠),说明不重叠,count++,该区间的end重新定义为end

(以上就是不重叠区间的用法,用总区间数 - 不重叠区间数就是要删除的区间树)

class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[1]));
        int count = 1;
        int x_end = intervals[0][1];
        for(int[] point : intervals){
            if(point[0] >= x_end){//这里是等于,因为顶点重叠不算重叠(跟气球那题不一样)
                count++;
                x_end = point[1];
            }
        }
        return intervals.length - count;
    }
}

763. 划分字母区间

贪心就是找到每个字符最后出现的位置,如果如果找到之前遍历过的所有字母的最远边界, 当前i等于边界,就加入结果集再把left+ 1:

class Solution {
        private int[] alphabet  = new int[26];
        private List<Integer> resList = new ArrayList<>();
        public List<Integer> partitionLabels(String s) {
            for(int i = 0 ; i < s.length(); i++){
                alphabet[s.charAt(i) - 'a'] = i;
            }
            int left = 0, right = 0;
            for(int i = 0; i < s.length(); i++){
                right = Math.max(right, alphabet[s.charAt(i) - 'a']);
                if(i == right){
                    resList.add(i - left + 1);
                    left = i + 1;
                }
            }
            return resList;
        }
    }

image

  • 初始化一个右边界right,是i之前所有字母的最远边界的最大值,左边界left用于计算区间长度。

56. 合并区间

  • 这题的关键点在于通过更新resList中的元素(特别是终点end)而不是创建新元素直接加入。
class Solution {
    public int[][] merge(int[][] intervals) {
        LinkedList<int[]> res = new LinkedList<>();
        Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));
        res.add(intervals[0]);
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] <= res.getLast()[1]) {
                int start = res.getLast()[0];
                int end = Math.max(intervals[i][1], res.getLast()[1]);
                //实际上就是更新res的最后一个元素
                res.removeLast();
                res.add(new int[]{start, end});
            }
            else {
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}

image

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【牛客SQL快速入门】SQL基础(三)

一、条件函数 IF 条件函数 IF函数是最常用到的条件函数&#xff0c;写法为 if(xn,a,b)&#xff0c;xn代表判断条件&#xff0c;如果xn时&#xff0c;那么结果返回a&#xff0c;否则返回b。 -- 把非北京大学的用户统一归为其他大学 Select device_id,if(university ‘北京大…

51-基于GitHubActions的CI实战

在Go项目开发中&#xff0c;我们要频繁地执行静态代码检查、测试、编译、构建等操作。如果每一步我们都手动执行&#xff0c;效率低不说&#xff0c;还容易出错。所以&#xff0c;我们通常借助CI系统来自动化执行这些操作。 当前业界有很多优秀的CI系统可供选择&#xff0c;例…

✌2024/4/3—力扣—无重复字符的最长子串

代码实现&#xff1a; 解法一&#xff1a;暴力法 int lengthOfLongestSubstring(char *s) {int hash[256] {0};int num 0;for (int i 0; i < strlen(s); i) {int count 0;for (int j i; j < strlen(s); j) {if (hash[s[j]] 0) {hash[s[j]];count;num num > cou…

基于 WebRTC 实现的点对点文件传输和音视频聊天工具 | 开源日报 No.220

tl-open-source/tl-rtc-file Stars: 2.1k License: MIT tl-rtc-file 是一个基于 WebRTC 的文件传输工具&#xff0c;支持跨终端、不限平台的在线文件传输。它提供了丰富的功能和特性&#xff1a; 分片传输&#xff1a;支持大型文件的分片传输&#xff0c;确保高效稳定地完成上…

OSPF的P2P和Broadcast

OSPF为什么会有P2P和BROADCAST两种类型 OSPF&#xff08;开放最短路径优先&#xff09;协议中存在P2P&#xff08;点对点&#xff09;和BROADCAST&#xff08;广播多路访问&#xff09;两种网络类型&#xff0c;主要是为了适应不同类型的网络环境和需求。具体分析如下&#xf…

Prototype 原型

意图 用原型实例指定创建对象的种类&#xff0c;并且通过复制这些原型创建新的对象。 结构 Prototype声明一个复制自身的接口。ConcretePrototype实现一个复制自身的操作。Client让一个原型复制自身从而创建一个新的对象。 适用性 当一个系统应该独立于他的产品创建、构成和…

设备基础命令,路由基础

直连路由 静态路由 动态路由 根据路由器学习路由信息、生成并维护路由表的方法包括直连路由(Direct)、静态路由(Static)和动态路由(Dynamic)。直连路由&#xff1a;路由器接口所连接的子网的路由方式称为直连路由&#xff1b;非直连路由&#xff1a;通过路由协议从别的路由器…

docker exec 命令提示:Error: No such container: /bin/bash

虽然是低级错误&#xff0c;但是还是记录一下吧。。。。。。。。 这个容器运行起来了&#xff0c;docker ps 是可以查询到的 但是 我想进入 容器内部时就出现了&#xff1a; docker exec -it /bin/bash e51b4dcdf51a Error: No such container: /bin/bash 开始以为是容器内部…

C语言 | Leetcode C语言题解之第22题括号生成

题目&#xff1a; 题解&#xff1a; // 回溯法求解 #define MAX_SIZE 1430 // 卡特兰数: 1, 1, 2, 5, 14, 42, 132, 429, 1430 void generate(int left, int right, int n, char *str, int index, char **result, int *returnSize) {if (index 2 * n) { // 当前长度已达2nre…

多线程的入门(五)线程池的保活策略

线程池是如何保活的呢&#xff1f;通过对源码的分析得出&#xff0c;线程池通过阻塞队列&#xff0c;与关闭工作线程后新生成空闲线程实现的保活策略源代码如下&#xff1a; runkworker&#xff08;&#xff09;方法的getTask&#xff08;&#xff09;方法中有这样一段代码&…

FMix: Enhancing Mixed Sample Data Augmentation 论文阅读

1 Abstract 近年来&#xff0c;混合样本数据增强&#xff08;Mixed Sample Data Augmentation&#xff0c;MSDA&#xff09;受到了越来越多的关注&#xff0c;出现了许多成功的变体&#xff0c;例如MixUp和CutMix。通过研究VAE在原始数据和增强数据上学习到的函数之间的互信息…

避免使用第三方工具完成电脑环境检测

0. 简介 在之前配置各种深度学习环境的时候经常需要先检测一下电脑的软硬件环境&#xff0c;其实整个过程比较重复和固定&#xff0c;所以我们是否有可能一键检测Python版本、PIP版本、Conda版本、CUDA版本、电脑系统、CPU核数、CPU频率、内存、硬盘等内容这是很多Deepper苦恼…

Nginx+Keepalived Kubernetes 负载均衡

部署NginxKeepalived高可用负载均衡器 kube-apiserver高可用架构图&#xff1a; Nginx是一个主流Web服务和反向代理服务器&#xff0c;这里用四层实现对apiserver实现负载均衡。Keepalived是一个主流高可用软件&#xff0c;基于VIP绑定实现服务器双机热备&#xff0c;在上述拓…

关于部署ELK和EFLKD的相关知识

文章目录 一、ELK日志分析系统1、ELK简介1.2 ElasticSearch1.3 Logstash1.4 Kibana&#xff08;展示数据可视化界面&#xff09;1.5 Filebeat 2、使用ELK的原因3、完整日志系统的基本特征4、ELK的工作原理 二、部署ELK日志分析系统1、服务器配置2、关闭防火墙3、ELK ElasticSea…

React + three.js 3D模型骨骼绑定

系列文章目录 React 使用 three.js 加载 gltf 3D模型 | three.js 入门React three.js 3D模型骨骼绑定React three.js 3D模型面部表情控制 项目代码(github)&#xff1a;https://github.com/couchette/simple-react-three-skeleton-demo 项目代码(gitcode)&#xff1a;https:…

这几个方面需要注意,减少服务器被入侵

网络时代&#xff0c;服务器和计算机不时地遭受入侵和攻击&#xff0c;给人们带来了无法预料的重大损失。诸如服务器入侵、数据盗窃和勒索软件等事件频繁发生&#xff0c;这令许多企业和游戏开发团队备受困扰。通过总结经验和吸取教训&#xff0c;我们必须汲取教益&#xff0c;…

Linux C应用编程:MQTT物联网

1 MQTT通信协议 MQTT&#xff08;Message Queuing Telemetry Transport&#xff0c;消息队列遥测传 输&#xff09;是一种基于客户端-服务端架构的消息传输协议&#xff0c;如今&#xff0c;MQTT 成为了最受欢迎的物联网协议&#xff0c;已广泛应用于车联网、智能家居、即时聊…

pycharm debug 的时候 waiting for process detach

当你使用pycharm debug或者run的时候&#xff0c;突然出现了点不动&#xff0c;然后一直显示&#xff1a;waiting for process detach 可能是以下问题&#xff1a; 1、需要设置Gevent compatible pycharm一直没显示运行步骤&#xff0c;只是出现waiting for process detach-C…

正则表达式---【Python版】

目录 前言 一.正则表达式概括 1.1简介 1.2使用场景 二.正则表达式语法 2.1基本匹配 2.2元字符 2.2.1点运算符. 2.2.2字符类[] 2.2.3否定字符类 2.2.4*号 2.2.5号 2.2.6&#xff1f;号 2.2.7{}号 2.2.8()号 2.2.9|或运算 2.2.10转码特殊字符\ 2.2.11^和$ 2.3简…

【论文阅读】Digging Into Self-Supervised Monocular Depth Estimation

论文&#xff1a;https://arxiv.org/pdf/1806.01260.pdf 代码&#xff1a;https://github.com/nianticlabs/monodepth2 Q: 这篇论文试图解决什么问题&#xff1f; A: 这篇论文试图解决的问题是如何提高仅使用单目图像进行深度估计的性能。具体来说&#xff0c;它关注的是如何…