代码随想录算法训练营第36天(贪心算法05 ● 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

贪心算法 part05

  • 435. 无重叠区间
    • 解题思路
  • 763.划分字母区间
    • 解题思路
    • 补充
  • 56. 合并区间
    • 解题思路
    • 不熟悉的基础语法知识

详细布置

今天的三道题目,都算是 重叠区间 问题,大家可以好好感受一下。 都属于那种看起来好复杂,但一看贪心解法,惊呼:这么巧妙!
还是属于那种,做过了也就会了,没做过就很难想出来。
不过大家把如下三题做了之后, 重叠区间 基本上差不多了

435. 无重叠区间

题目链接: 435. 无重叠区间
文章/视频链接: 435. 无重叠区间

解题思路

这道题和452.用最少数量的箭引爆气球思路很类似。
二者的区别仅在于

  • 这道题 intervals[i][0] >= intervals[i-1][1] 算2个区间不重叠,即[1,2]和[2,3]属于两个不同的区间
  • 引爆气球那道题intervals[i][0] > intervals[i-1][1] 严格大于才算2个区间不重叠,即[1,2]和[2,3]属于同一个区间,用一个弓箭即可

弓箭的数量就相当于是非交叉区间的数量,只要把弓箭那道题目代码里射爆气球的判断条件加个等号(认为[0,1][1,2]不是相邻区间),然后用总区间数减去弓箭数量 就是要移除的区间数量了。

// 贪心
// 直接计算要移除的区间数量
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
        int count = 0;
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] < intervals[i-1][1]){
                count++;
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
            }
        }
        return count;
    }
}
// 延续452.用最少数量的箭引爆气球 的代码稍作修改
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a,b)-> {
            return Integer.compare(a[0],b[0]);
        });
        int count = 1;
        for(int i = 1;i < intervals.length;i++){
            if(intervals[i][0] >= intervals[i-1][1]){
                count++;
            }else{
                intervals[i][1] = Math.min(intervals[i][1], intervals[i-1][1]);
            }
         }
        return intervals.length - count;
    }
}

763.划分字母区间

题目链接: 763.划分字母区间
文章/视频链接: 763.划分字母区间

解题思路

可以分为如下两步:

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

补充

这里提供一种与452.用最少数量的箭引爆气球435.无重叠区间相同的思路。
统计字符串中所有字符的起始和结束位置,记录这些区间(实际上也就是435.无重叠区间题目里的输入),将区间按左边界从小到大排序,找到边界将区间划分成组,互不重叠。找到的边界就是答案。
代码感觉写起来比较麻烦,可以去代码随想录上看。

// 贪心
class Solution {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new LinkedList<>();
        int[] edge = new int[26];  //用数组模拟哈希表
        int left = 0;
        int right = 0;
        // int index = 0;
        char[] chars = s.toCharArray();
        for(int i = 0; i < chars.length; i++){
            edge[chars[i] - 'a'] = i;
        }

        for(int i = 0; i < chars.length; i++){
            right = Math.max(right, edge[chars[i] - 'a']);
            if(i == right){
                list.add(i-left+1);
                left = i + 1;
            }
        }
        return list;

    }
}

56. 合并区间

本题相对来说就比较难了。
题目链接: 56. 合并区间
文章/视频链接: 56. 合并区间

解题思路

和我们刚刚讲过的452. 用最少数量的箭引爆气球435. 无重叠区间 都是一个套路。
这几道题都是判断区间重叠,区别就是判断区间重叠后的逻辑,本题是判断区间重贴后要进行区间合并。

  1. 先排序,让所有的相邻区间尽可能的重叠在一起,按左边界,或者右边界排序都可以,处理逻辑稍有不同。
  2. 若有重叠,即intervals[i][0] <= res.getLast()[1], 用合并区间后左边界和右边界,作为一个新的区间,加入到result数组里就可以了。
    如果没有合并就把原区间加入到result数组。

不熟悉的基础语法知识

排序

Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));

list相关操作

List<int[]> res = new LinkedList<>();
res.getLast()[0]和res.getLast()[1]
res.add(new int[]{start, end})
res.add(intervals[i])
res.toArray(new int[res.size()][])
// 贪心 法1 延续之前两道重叠区间问题的思路
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
        //按照左边界排序
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[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.removeLast();
                res.add(new int[]{start, end});
            }else{
                res.add(intervals[i]);
            }
        }
        return res.toArray(new int[res.size()][]);
    }
}
// 贪心 法2  思路类似
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]> res = new LinkedList<>();
        //按照左边界排序
        Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
        //initial start 是最小左边界
        int start = intervals[0][0];
        int rightmostRightBound = intervals[0][1];
        for(int i = 1; i < intervals.length; i++){
            if(intervals[i][0] > rightmostRightBound){
                res.add(new int[]{start, rightmostRightBound});
                start = intervals[i][0];
                rightmostRightBound = intervals[i][1];
            }else{
                rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
            }
        }
        res.add(new int[]{start, rightmostRightBound});
        return res.toArray(new int[res.size()][]);


    }
}

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

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

相关文章

【C++入门到精通】特殊类的设计 | 单例模式 [ C++入门 ]

阅读导航 引言一、设计模式概念&#xff08;了解&#xff09;二、单例模式1. 饿汉模式&#xff08;1&#xff09;概念&#xff08;2&#xff09;模拟实现&#xff08;3&#xff09;优缺点&#xff08;4&#xff09;适用场景 2. 懒汉模式&#xff08;1&#xff09;概念&#xff…

vue使用富文本

1、安装 cnpm install vue-quill-editor2、在main.js中引入 // 富文本 import VueQuillEditor from vue-quill-editor // require styles 引入样式 import quill/dist/quill.core.css import quill/dist/quill.snow.css import quill/dist/quill.bubble.css Vue.use(VueQuill…

cesium-球体透明

在开发的过程&#xff0c;要求cesium加载的地球透明 只是地表透明还不能满足要求&#xff0c;只加载部分区域的方式来解决的 代码如下&#xff1a; <template><div id"cesiumContainer" style"height: 100vh;"></div><div id"…

【C++进阶08】哈希的应用(位图and布隆过滤器)

一、位图 1.1 位图的概念 面试题 给40亿个不重复的无符号整数&#xff0c;没排过序 给一个无符号整数&#xff0c;如何快速判断一个数是否在 这40亿个数中。【腾讯】 能想到的解决思路&#xff1a; 遍历&#xff0c;时间复杂度O(N)排序(O(NlogN)) 利用二分查找: logN放到哈…

centos搭建ftp踩坑记录

ftp服务器搭建参考b站视频 第1坑&#xff0c;开放端口后仍然无法连接&#xff1a; 这里不仅需要在防火墙打开20和21端口&#xff0c;还需要打开被动访问所使用的端口&#xff0c;也就是在配置文件vsftpd.conf中指定的被动访问接收端口。 pasv_enableYES pasv_min_port40000 p…

小红书论文刷新 SOTA:人体动作预测再升级,能精准到指尖

想象一下&#xff0c;你在玩一款 VR 游戏&#xff0c;准备伸手拿起一个虚拟杯子喝水。‍​​‌​‌​‎‎ 在传统的交互系统中&#xff0c;这通常需要你按下控制器上的特定按钮。但如果游戏集成了 EAI 框架&#xff0c;这一过程将变得无比自然。当你的手缓缓接近虚拟杯子时&…

数据库基础知识(一)

数据库基础知识&#xff08;一&#xff09; 一、数据库基本概念 1.1 数据 数据&#xff08;Data&#xff09;是指对客观事物进行描述并可以鉴别的符号&#xff0c;这 些符号是可识别的、抽象的。它不仅指狭义上的数字&#xff0c;而是有多 种表现形式&#xff1a;字母、文…

如何开通GitHub Copilot

GitHub Copilot 是由GitHub 和OpenAI共同开发的人工智能代码辅助工具&#xff0c;可以自动地生成高质量代码片段、上下文信息等。 通过自然语言处理和机器学习技术&#xff0c;能够通过分析程序员编写的代码、注释和上下文信息&#xff0c;自动生成代码&#xff0c;减轻程序员的…

在线摸头GIF生成系统源码

在线摸头GIF在线生成器html网页源码&#xff0c;可以点击选择文件按钮&#xff0c;或者直接将图片拖入&#xff0c;即可生成导出

Python爬虫---Scrapy框架---CrawlSpider

CrawlSpider 1. CrawlSpider继承自scrapy.Spider 2. CrawlSpider可以定义规则&#xff0c;再解析html内容的时候&#xff0c;可以根据链接规则提取出指定的链接&#xff0c;然后再向这些链接发送请求&#xff0c;所以&#xff0c;如果有需要跟进链接的需求&#xff0c;意思就是…

Code - VQ-VAE (Vector Quantised Variational AutoEncoder) 的实现源码

欢迎关注我的CSDN&#xff1a;https://spike.blog.csdn.net/ 本文地址&#xff1a;https://spike.blog.csdn.net/article/details/135936848 VQ-VAE&#xff0c;即Vector Quantized Variational AutoEncoder&#xff0c;向量量化变分自编码器。VQ-VAE 的创新之处是引入了一个向…

ArcGIS学习(二)属性表的基本操作

ArcGIS学习(二)属性表的基本操作 1.查看属性表 ArcGIS是处理空间数据的平台。对于空间数据,大家可以理解成它是由两个部分构成:1.一个是空间形体,也就是点、线、面三种。线又可以分为直线、曲线,面又分为圆形、正方形、不规则形体等;2.另外一个部分是空间形体所附带的…

Unix/Linux上的五种IO模型

a.阻塞 blocking 调用者调用了某个函数&#xff0c;等待这个函数返回&#xff0c;期间什么也不做&#xff0c;不停的去检查这个函数有没有返回&#xff0c;必须等这个函数返回才能进行下一步动作。 注意&#xff1a;阻塞并不是函数的行为&#xff0c;而是跟文件描述符有关。通…

离谱题 3236:练39.1 书香阁座位

3236正常写法 #include<bits/stdc.h> using namespace std; int main() {int sum,a,b;a1;b10;sumb;cout<<a<<" "<<b;cout<<" "<<sum<<endl;do{a;b2;sumx;cout<<a<<" "<<b<<&…

uniapp本地存储日志

uniapp本地存储日志 背景实现代码实现使用查看生成log读取 注意事项尾巴 背景 我们的APP开发完成之后&#xff0c;在我们测试环境或者自测的时候都好好的&#xff0c;但是发布到生产环境客户使用总会出现一些奇奇怪怪的问题。这时候因为没在开发环境&#xff0c;我们无法查看到…

力扣hot100 买卖股票的最佳时机 贪心 经典题

Problem: 121. 买卖股票的最佳时机 文章目录 思路复杂度Code 思路 假设今天卖出&#xff0c;那怎么样收益最大呢&#xff1f;之前买入价是最低的 复杂度 ⏰ 时间复杂度: &#xff1a; O ( n ) O(n) O(n) &#x1f30e; 空间复杂度: O ( 1 ) O(1) O(1) Code class Solut…

c++之IO流

1.C语言的输入与输出 C语言中我们用到的最频繁的输入输出方式就是scanf ()与printf()。 scanf(): 从标准输入设备(键 盘)读取数据&#xff0c;并将值存放在变量中。printf(): 将指定的文字/字符串输出到标准输出设备(屏幕)。 注意宽度输出和精度输出控制。C语言借助了相应的缓…

tsmc12: m0po max length问题(H384.M0_PO.L.1)

更多学习内容请关注「拾陆楼」知识星球 拾陆楼知识星球入口 在pt eco之后会有一些m0po max length问题出现,大部分问题都可以通过替换decap来解决,少部分由于局部density过高,需要手动调整。

2023强网杯复现

强网先锋 SpeedUp 要求2的27次方的阶乘的逐位之和 在A244060 - OEIS 然后我们将4495662081进行sha256加密 就得到了flag flag{bbdee5c548fddfc76617c562952a3a3b03d423985c095521a8661d248fad3797} MISC easyfuzz 通过尝试输入字符串判断该程序对输入字符的验证规则为9…

【C++】类和对象之构造函数、析构函数、拷贝构造函数(二)

前言&#xff1a;在上一篇我们对于C中类和对象有了一个初步的了解&#xff0c;今天我们将进一步的学习&#xff0c;今天我们目标是对构造函数、析构函数、拷贝构造函数进行一个初步学习在后面也会进一步的学习&#xff0c;一起加油呐&#xff01; &#x1f496; 博主CSDN主页:卫…