devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

Day36:LeedCode 435. 无重叠区间 763.划分字母区间 56. 合并区间 蓝桥杯 管道

作者：繁依Fanyi0 | 2024-04-11 12:17:29

赞

踩

Day36:LeedCode 435. 无重叠区间 763.划分字母区间 56. 合并区间 蓝桥杯 管道

435. 无重叠区间

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。

思路:

本题与LeedCode452.用最少数量的箭引爆气球非常相似,弓箭的数量就是未交叉的气球的数量,只要把弓箭那道题目代码里射爆气球的判断条件加个等号（本题认为[0，1][1，2]不是相邻区间）,

然后用总区间数减去弓箭数量 就是要移除的区间数量了。Day35 LeedCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球-CSDN博客

代码参考:

  1. class Solution {
  2.     public int eraseOverlapIntervals(int[][] intervals) {
  3.         if(intervals.length==0)return 0;
  4.           Arrays.sort(intervals,(o1,o2)->{return o1[0]-o2[0];});
  5.           int count=1;//从第二个气球开始,至少一箭
  6.           for(int i=1;i<intervals.length;i++){
  7.             if(intervals[i][0]>=intervals[i-1][1]){
  8.                 //没有重叠
  9.                 count++;
  10.             }else{
  11.                 //有重叠
  12.                 intervals[i][1]=Math.min(intervals[i][1],intervals[i-1][1]);
  13.             }
  14.           }
  15.           return intervals.length-count;
  16.     }
  17. }

763. 划分字母区间

给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。

返回一个表示每个字符串片段的长度的列表。

示例 1：

输入：s = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca"、"defegde"、"hijhklij" 。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 这样的划分是错误的，因为划分的片段数较少。

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

可以分为如下两步：

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

代码参考:

  1. class Solution {
  2.     public List<Integer> partitionLabels(String s) {
  3.       int[] hash=new int[26];
  4.       for(int i=0;i<s.length();i++){
  5.         hash[s.charAt(i)-'a']=i;//记录每个字母的最后出现位置
  6.       }
  7.     List<Integer>result=new ArrayList<>();
  8.     int left=0;
  9.     int right=0;
  10.     for(int i=0;i<s.length();i++){
  11.       right=Math.max(right,hash[s.charAt(i)-'a']);//更新最远分割距离
  12.       if(i==right){
  13.         result.add(right-left+1);
  14.         left=right+1;
  15.  
  16.       }
  17.     }
  18.     return result;
  19.     }
  20. }

 

56. 合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

思路:本题与LeedCode452.用最少数量的箭引爆气球和 435. 无重叠区间很像,都是区间覆盖的问题,需要先将区间按照左边界从小到大排序,intervals[i][0] <= intervals[i - 1][1],即intervals[i]的左边界 <= intervals[i - 1]的右边界，则一定有重叠。（本题相邻区间也算重贴，所以是<=）

Day35 LeedCode 860.柠檬水找零 406.根据身高重建队列 452. 用最少数量的箭引爆气球-CSDN博客

代码参考:

  1. class Solution {
  2.     public int[][] merge(int[][] intervals) {
  3.     List<int[]> result=new ArrayList<>();
  4.     //按照左边界从小往大排序
  5.     Arrays.sort(intervals,(o1,o2)->{return o1[0]-o2[0];});
  6.     //start,end记录上一区间,如果下一个区间和它重叠,更新这个区间范围,如果不重叠,将它加入结果集,并用下一区间代替它
  7.     int start=intervals[0][0];
  8.     int end=intervals[0][1];
  9.     for(int i=1;i<intervals.length;i++ ){
  10.      if(intervals[i][0]>end){
  11.         //如果没有重叠  //将上一区间加入结果集合
  12.         result.add(new int[]{start,end});
  13.        //更新上一区间
  14.        start=intervals[i][0];
  15.        end=intervals[i][1];
  16.      }else{
  17.         //更新区间最大右边界
  18.         end=Math.max(intervals[i][1],end);
  19.      }
  20.     }
  21.      result.add(new int[]{start,end});
  22.     return result.toArray(new int[result.size()][]);
  23.     }
  24. }

 

90. 管道

时间限制：1.000S  空间限制：256MB

题目描述

有一根长度为 len 的横向的管道，该管道按照单位长度分为 len 段，每一段的中央有一个可开关的阀门和一个检测水流的传感器。 一开始管道是空的，位于 Li 的阀门会在 Si 时刻打开，并不断让水流入管道。 

对于位于 Li 的阀门，它流入的水在 Ti (Ti ≥ Si) 时刻会使得从第 Li−(Ti − Si) 段到第 Li + (Ti − Si) 段的传感器检测到水流。 求管道中每一段中间的传感器都检测到有水流的最早时间。

输入描述

输入的第一行包含两个整数 n, len，用一个空格分隔，分别表示会打开的阀门数和管道长度。 

接下来 n 行每行包含两个整数 Li , Si，用一个空格分隔，表示位于第 Li 段 管道中央的阀门会在 Si 时刻打开。

输出描述

输出一行包含一个整数表示答案。

输入示例
  1. 3 10
  2. 1 1
  3. 6 5
  4. 10 2
输出示例
5
提示信息

对于 30% 的评测用例，n ≤ 200，Si, len ≤ 3000；
对于 70% 的评测用例，n ≤ 5000，Si, len ≤ 105；
对于所有评测用例，1 ≤ n ≤ 105，1 ≤ Si , len ≤ 109，1 ≤ Li ≤ len，Li−1 < Li

思路:时间越长,越有可能让所有管道都感应到水流,用二分查找,在可能的时间里找到能让所有水管响应的那个时间,时间至少为1,最大时间一定在只在端点开一个水管的时候,1 + (Ti − 10^5)>=10^9

所以Ti>=10^5+10^9-1

确定Ti在[1,1000100000)区间内,用不同的Ti去试

checkRange函数:确定该时间点,整个管道是否感应到水流,如果你做了上面一题,很容易写出这个函数,就是给你很多区间,让你找到合并区间,找到最大范围,如果这个范围是整个管道,那么该时间点是可以让所有水管感应到的

注意:不是该段水管打开了才能感应到水流,就是该段水管没有打开,也能因为旁边其他水管而感应到水流的,所以TI不一定是大于等于所有管道的最大打开阀门时间,收集区间时,如何Ti<开阀门时间,我们将不收集这段水管的区间,因为这段区间是不合法的

代码参考:

  1.  
  2.   
  3. import java.util.*;
  4.   
  5. import com.sun.org.apache.bcel.internal.generic.NEW;
  6.   
  7.   
  8. import java.util.*;
  9.   
  10. public class Main {
  11.     static int n, len;
  12.     static Map<Integer, Integer> map = new HashMap<>();//记录每个水管的li,si
  13.   
  14.     static boolean checkRange(long time) {
  15.   
  16.   
  17.         // Li−(Ti − Si) 段到第 Li + (Ti − Si)
  18.         //收集所有区间
  19.         List<A> temp = new ArrayList<>();
  20.         int left, right;
  21.         for (Integer key : map.keySet()) {
  22.             //(Ti ≥ Si)
  23.             if (time >= map.get(key)) {
  24.                 left = (int) Math.max(1, key - time + map.get(key));
  25.                 right = (int) Math.min(len, key + time - map.get(key));
  26.                 temp.add(new A(left, right));
  27.             }
  28.         }
  29.         //区间排序,按照区间的左端从小到大排序
  30.         //在使用Arrays.sort()方法时
  31.         // 要特别注意排序的对象中是否会存在null，如果存在null，则程序会报 空指针的错误.
  32.         temp.sort((o1, o2) -> {
  33.             return o1.compareTo(o2);
  34.         });
  35.   
  36.         // 记录最大范围
  37.         int start = temp.get(0).l;
  38.         int end = temp.get(0).r;
  39.         for (int j = 1; j < temp.size(); j++) {
  40.             if (temp.get(j).l <= end + 1) {
  41.                 //如果区间有重叠,[5,6][7,8]算重叠
  42.                 end = Math.max(end, temp.get(j).r);
  43.             } else {
  44.                 //如果没有重叠
  45.                 break;
  46.             }
  47.         }
  48.   
  49.         return end == len && start == 1;
  50.     }
  51.   
  52.   
  53.     public static void main(String args[]) {
  54.         Scanner in = new Scanner(System.in);
  55.         n = in.nextInt();
  56.         len = in.nextInt();
  57.         int nums = n;
  58.         while (nums-- > 0) {
  59.             //输入 Li , Si，
  60.             map.put(in.nextInt(), in.nextInt());
  61.         }
  62.         //r没有超过long所能表达的数据范围 报错的原因是java默认数据类型是int,要在数据后加l表示是long类型
  63.         long l = 1, r = (long) 1000100000;
  64.         while (l <r) {
  65.             long mid = (l + r) / 2;
  66.             if (checkRange(mid)) {
  67.                 r = mid;
  68.             } else {
  69.                 l = mid + 1;
  70.             }
  71.         }
  72.         System.out.println(r);
  73.     }
  74.   
  75.    
  76.   
  77. }
  78. class A implements Comparable<A> {
  79.     int l;
  80.     int r;
  81.   
  82.     A(int a, int b) {
  83.         l = a;
  84.         r = b;
  85.     }
  86.   
  87.     public int compareTo(A b) {
  88.         return this.l - b.l;
  89.     }
  90.   
  91.     public int getL() {
  92.         return l;
  93.     }
  94.   
  95.     public int getR() {
  96.         return r;
  97.     }
  98.   
  99.     @Override
  100.     public String toString() {
  101.         return "A{" +
  102.                 "l=" + l +
  103.                 ", r=" + r +
  104.                 '}';
  105.     }
  106. }

这段代码运行超过时间限制了,本人才疏学浅,只是给大家提供一个思路,如果大家有更好的方法,欢迎留言 !

 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/404952
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号