代码随想录算法训练营第三十六天|435. 无重叠区间、763.划分字母区间 、56. 合并区间

文章目录

      • 重叠问题
      • 435. 无重叠区间
      • 763.划分字母区间:star:
      • 56. 合并区间

重叠问题

这几道题都是判断区间重叠,区别就是判断区间重叠后的逻辑

435. 无重叠区间

  • 链接:代码随想录

  • 解题思路:
    这道题和射气球的题几乎思路一样
    不断求出重叠的最小右区间,模拟重叠过程就可解题

public int eraseOverlapIntervals(int[][] intervals) {
    //按左边排序
    Arrays.sort(intervals, (a,b)->{
        return Integer.compare(a[0], b[0]);
    });

    int remove = 0;//该移除的区间
    int pre = intervals[0][1];//前一个判断的右区间
    for (int i = 1; i < intervals.length; i++) {
        //有重叠的情况
        if(pre > intervals[i][0]){
            remove++;
            //更新最新的右区间为
            //相交的时候去最小的右边,没被取的右边的区间即被删除
            pre = Math.min(pre, intervals[i][1]);
        }else{
            pre = intervals[i][1];//没有重叠的情况
        }
    }

    return remove;
}

763.划分字母区间⭐️

  • 链接:代码随想录

  • 解题思路:
    ①统计每一个字符最后出现的位置**(哈希结构存储)**
    ②从头遍历字符,并更新字符的最远出现下标,如果找到字符最远出现位置下标和当前下标相等了,则找到了分割点

    ​ 贪心可能体现在,找最远下标的情况
    ​ 用最远出现距离模拟了圈字符。
    ​ 如果遍历的 i == 最远下标,说明之前遍历过的元素都符合划分范围,即划分

  • 图像理解

    Snipaste_2023-04-19_17-06-11

public List<Integer> partitionLabels(String s) {
    int[] hash = new int[26];//hash[i] 为字符最远出现的地方的索引  用哈希结构维护(索引 -- 值)

    for (int i = 0; i < s.length(); i++) {
        hash[s.charAt(i) - 'a'] = i;
    }

    int left = 0;//每一次区间的起点位置
    int right = 0;//每一次划分区间的末尾位置

    List<Integer> res = new ArrayList<>();

    for (int i = 0; i < s.length(); i++) {
        right = Math.max(right, hash[s.charAt(i) - 'a']);//取最大边界

        //遍历到最大边界
        if(i == right){
            res.add(right - left + 1);

            left = right + 1;//更新起点位置
        }
    }

    return res;
}

56. 合并区间

  • 题目链接:代码随想录

重叠问题

  • 解题思路:
    此题判断重叠区间还是原先的思路,先排序,再根据右边界和左边界进行判断
    关键点在于判定重叠区间后,判断进行加入结果集的操作

  • 图像理解:

    Snipaste_2023-04-19_17-48-39

public int[][] merge(int[][] intervals) {

    List<int[]> res = new LinkedList<>();//结果集

    //1.排序
    Arrays.sort(intervals,(a,b) -> {
        return Integer.compare(a[0], b[0]);
    });

    //2.定义区间,来求最大重叠区域,并处理最大重叠区域,添加进一个新的结果集,耗空间
    int start = intervals[0][0];//起始位置
    int right = intervals[0][1];//右区间
    //3.进行遍历

    for (int i = 1; i < intervals.length; i++) {

        //重叠区域,更新最大右区间,先不加入结果集
        if(right >= intervals[i][0]){
            right = Math.max(right, intervals[i][1]);
        }else{//非重叠区域,将非重叠的第一个区域加入结果集,符合要求

            res.add(new int[]{start,right});//前一个位置

            //更新当前区间
            start = intervals[i][0];
            right = intervals[i][1];
        }
    }

    //最后一定要加入最后一个待加入区间
    res.add(new int[]{start,right});

    return res.toArray(new int[res.size()][]);
}

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

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

相关文章

通俗讲解什么是Socket通讯

Socket通讯原理 1、什么是Socket&#xff1f; Socket&#xff0c;即套接字。就是两台主机之间逻辑连接的端点。&#xff08;通俗来说&#xff1a;网络上的两个程序通过一个双向的通信连接实现数据的交换&#xff0c;这个连接的一端称为一个socket&#xff09;。 Socket是一套…

CSS基础——盒子模型

目录 简介 盒子模型组成 内容区 内边距 边框 border-width border-color border-style border 外边距 负值 auto 简写属性 垂直外边距的重叠 浏览器默认设置 内联元素的盒子 简介 在网页中&#xff0c;一切都是可以看作为“盒子”。 在css处理网页的时候&…

常见的四种排名函数的用法(sql)

四个排名函数&#xff1a; 1.row_number 2.rank 3.dense_rank 4.ntile 1. ROW_NUMBER&#xff08;排名场景推荐&#xff09; 1.1 介绍 在 SQL 中&#xff0c;ROW_NUMBER() 是一个窗口函数&#xff0c;它为结果集中的每一行分配一个唯一的序号。该函数的语法如下&#xff1a; …

内网穿透实现在外远程连接RabbitMQ服务

文章目录 前言1.安装erlang 语言2.安装rabbitMQ3. 内网穿透3.1 安装cpolar内网穿透(支持一键自动安装脚本)3.2 创建HTTP隧道 4. 公网远程连接5.固定公网TCP地址5.1 保留一个固定的公网TCP端口地址5.2 配置固定公网TCP端口地址 转载自远控源码文章&#xff1a;无公网IP&#xff…

srm采购管理系统有那些功能

srm采购管理系统&#xff0c;是通过系统的手段对采购过程进行管理和控制&#xff0c;实现降低成本、提高效益、提高企业核心竞争力的目的。那么 srm采购管理系统有哪些功能呢&#xff1f; 计划管理 srm采购管理系统提供了各种物料需求计划的功能&#xff0c;以帮助企业制定并控…

设置环境变量

文章目录 window设置linux设置python设置 window设置 命令行设置 set 临时设置setx 永久设置 # 打开一个cmd命令行 set # 查看所有环境变量 set FLASK_APPsuperset # 临时设置&#xff0c;当前窗口有效 set FLASK_APP%FLASK_APP%;777 # # 查看 echo %FLASK_APP%# 永久设置…

k8s安装部署apollo配置中心

一、文章大纲 二、安装MySQL5.7 三、创建apollo-config 四、创建apollo-admin 五、创建apollo-portal 六、查看apollo各个组件服务状态 七、访问apollo 八、nginx代理配置转发#注意 一定要先启动apollo-config&#xff0c;再启动apollo-admin&#xff0c;最后启动apollo-porta…

matrix部署

一、环境描述 首先matrix是一个去中心化的聊天服务&#xff0c;matrix实现了端对端的加密&#xff0c;这意味着不仅其他人无法查看你的聊天内容&#xff0c;哪怕你更换了一个终端&#xff0c;你也需要私钥才能够查看你的聊天记录。 这是终极的隐私保护方案&#xff0c;因为一旦…

深入理解机器学习——过拟合(Overfitting)与欠拟合(Underfitting)

分类目录&#xff1a;《深入理解深度学习》总目录 机器学习的主要挑战是我们的算法必须能够在先前未观测的新输入上表现良好&#xff0c;而不只是在训练集上表现良好。在先前未观测到的输入上表现良好的能力被称为泛化&#xff08;Generalization&#xff09;。通常情况下&…

20、单元测试

文章目录 1、JUnit5 的变化2、JUnit5常用注解3、断言&#xff08;assertions&#xff09;1、简单断言2、数组断言3、组合断言4、异常断言5、超时断言6、快速失败 4、前置条件&#xff08;assumptions&#xff09;5、嵌套测试6、参数化测试7、迁移指南 【尚硅谷】SpringBoot2零基…

医院体检PEIS系统源码

一、医院体检系统概述 1. 医院体检系统概述 目前&#xff0c;大多数的体检还停留在手工操作上&#xff0c;如单位体检时手工书写体检人员信息、医生手工书写体检结果、检验报告打印后进行手工粘贴等&#xff0c;这样造成极大的工作量&#xff0c;效率低下&#xff0c;而且极易…

OpenCV 安卓编程示例:1~6 全

原文&#xff1a;OpenCV Android Programming By Example 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 本文来自【ApacheCN 计算机视觉 译文集】&#xff0c;采用译后编辑&#xff08;MTPE&#xff09;流程来尽可能提升效率。 当别人说你没有底线的时候&#xff0c;…

npm和yarn的相同点和不同点

官网 npmhttps://www.npmjs.com Home | Yarn - Package ManagerFast, reliable, and secure dependency management.https://yarnpkg.com Fast, disk space efficient package manager | pnpmFast, disk space efficient package managerhttps://pnpm.io 使用场景 npm&#x…

发布会前准备新闻通稿的重要性,为什么媒体不会原稿发布报道?

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体 胡老师。 最近有宣传的小伙伴问胡老师&#xff0c;为什么我们精心准备的新闻通稿&#xff0c;媒体没有按照稿子发布呢&#xff1f;今天就与大家交流下这方面的经验。 一&#xff0c;发布会前准备新…

4月20日第壹简报,星期四,农历三月初一,谷雨

4月20日第壹简报&#xff0c;星期四&#xff0c;农历三月初一&#xff0c;谷雨坚持阅读&#xff0c;静待花开1. 已致29人死亡&#xff0c;26人为患者&#xff01;北京长峰医院火灾事故因院内施工作业火花引发&#xff0c;院长王某玲等12人被刑拘。2. 海南发布旅游产品参考价格&…

教你轻松申请Azure OpenAI

Azure OpenAI 和 OpenAI 官方提供的服务基本是一致的&#xff0c;但是目前前者还是处于预览版的状态&#xff0c;一些功能还没有完全开放。 优点&#xff1a; 不受地域限制&#xff0c;国内可以直接调用。可以自己上传训练数据进行训练&#xff08;据说很贵&#xff09;。Azu…

低代码开发重要工具:jvs-logic(逻辑引擎)可视化设计要素

逻辑引擎可视化的交互 可视化的服务编排是逻辑引擎的核心功能&#xff0c;逻辑引擎的界面可视化设计是为了方便用户使用和操作逻辑引擎而设计的。一个好的界面设计能够提高用户的工作效率和使用体验&#xff0c;同时也能增加软件的可靠性和可维护性。 以下是逻辑引擎界面可视化…

【Linux初阶】进程的相关概念 | 进程管理 查看进程 获取进程标识符 fork进程创建

&#x1f31f;hello&#xff0c;各位读者大大们你们好呀&#x1f31f; &#x1f36d;&#x1f36d;系列专栏&#xff1a;【Linux初阶】 ✒️✒️本篇内容&#xff1a;进程的概念&#xff0c;进程管理初识&#xff08;描述、管理进程&#xff09;&#xff0c;查看进程的基础方法…

K_A33_001 基于STM32等单片机驱动RC522射频卡 读写IC卡 串口显示

K_A33_001 基于STM32等单片机驱动RC522射频卡 读写IC卡 串口显示 所有资源导航一、资源说明二、基本参数参数引脚说明 三、驱动说明时序:对应程序: 四、部分代码说明1、接线引脚定义1.1、STC89C52RCRC522射频模块1.2、STM32F103C8T6RC522射频模块 五、基础知识学习与相关资料下…

使用chatgpt实现微信聊天小程序(秒回复),github开源(附带链接)

文章目录 前言效果展示原理说明服务器端代码说明微信小程序代码说明代码链接总结 前言 我在前一段时间突发奇想&#xff0c;就使用java来调用chatgpt的接口&#xff0c;然后写了一个简单小程序&#xff0c;也上了热榜第一&#xff0c;java调用chatgpt接口&#xff0c;实现专属…