Java教程

java leetcode之[中等]986. 区间列表的交集

本文主要是介绍java leetcode之[中等]986. 区间列表的交集,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

题目的链接在这里:https://leetcode-cn.com/problems/interval-list-intersections/

目录

  • 题目大意
  • 一、示意图
  • 二、解题思路
    • 正常逻辑


题目大意

给定两个由一些 闭区间 组成的列表,firstList 和 secondList ,其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的,并且 已经排序 。

返回这 两个区间列表的交集 。

形式上,闭区间 [a, b](其中 a <= b)表示实数 x 的集合,而 a <= x <= b 。

两个闭区间的 交集 是一组实数,要么为空集,要么为闭区间。例如,[1, 3] 和 [2, 4] 的交集为 [2, 3] 。


一、示意图

在这里插入图片描述

二、解题思路

正常逻辑

正常逻辑

代码如下:

class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        //先进行边界判断
        if(firstList.length==0||secondList.length==0){
            return new int[0][];
        }
        //参考昨天的方法 先写一个存储的数组
        List<int[]> res=new LinkedList<>();
        int fir=0;
        int sed=0;
        while (fir<firstList.length&&sed<secondList.length){
            //需要进行四个比较吗 头和头 头和尾 尾和头 尾和尾
            //直接判断 first的尾巴在不在 sec的头尾之间?
            if(firstList[fir][1]>=secondList[sed][0]&&firstList[fir][1]<=secondList[sed][1]){
                //说明在 头尾之间 那就需要判断fir的头和sec的头之间的大小了
                if(firstList[fir][0]>=secondList[sed][0]){
                    //说明firs更大
                    //那他们的交集肯定是 那就是需要fir的头和尾
                    //然后怎么改进呢
                    res.add(new int[]{firstList[fir][0], firstList[fir][1]});
                    //这两个都说明 first比sec要小了
                    fir++;
                    //sec不要移动吧
                }else{
                    //那肯定就是 那就说明是 sec的更大了 而更大表示范围更小
                    if(secondList[sed][0]<=firstList[fir][1]){
                        res.add(new int[]{secondList[sed][0], firstList[fir][1]});
                    }
                    fir++;
                }
            }else if(firstList[fir][1]<secondList[sed][0]){
                //那就说明fir都远远离开sec
                fir++;
            }else if(firstList[fir][1]>secondList[sed][1]){
                //这里出现了判断 很有可能头尾都不接 那就直接头尾进行判断吧
                //那就说明first至少包括了当前的sec
                if(firstList[fir][0]>=secondList[sed][0]){
                    //如果first 比较大的话 更好证明 fir的范围更小
                    if(firstList[fir][0]<=secondList[sed][1]) {
                        res.add(new int[]{firstList[fir][0], secondList[sed][1]});
                    }
                    //然后进行修改
                    sed++;
                }else{
                    //这才说明是 sec的头尾
                        res.add(new int[]{secondList[sed][0], secondList[sed][1]});
                    sed++;
                }
            }
        }
        /**
         * list的toArray 方法:里面有参数 res是一个list 他每一个都有一个数组 相当于他是数组的第一列 而每一列存储的 就是 数组对应的值
         * 相当于 最后返回的 就是这个 new出来的Int 而这个int中存在 res对应的值
         *   public <T> T[] toArray(T[] a) {
         *         if (a.length < size)
         *             a = (T[])java.lang.reflect.Array.newInstance(
         *                                 a.getClass().getComponentType(), size);
         *         int i = 0;
         *         Object[] result = a;
         *         for (Node<E> x = first; x != null; x = x.next)
         *             result[i++] = x.item;
         *
         *         if (a.length > size)
         *             a[size] = null;
         *
         *         return a;
         *     }
         */
        return res.toArray(new int[res.size()][]);
    }
}

在这里插入图片描述

这篇关于java leetcode之[中等]986. 区间列表的交集的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!