整数数组区间的插入与删除

这篇具有很好参考价值的文章主要介绍了整数数组区间的插入与删除。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

相似题参考:

56. Merge Intervals - 力扣(LeetCode)合并区间

57. 插入区间 - 力扣(LeetCode)

1272. 删除区间文章来源地址https://www.toymoban.com/news/detail-663437.html

package Jerry;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

// Task: Implement a class named 'RangeList'
// A pair of integers define a range, for example: [1, 5). This range includes integers: 1, 2, 3, and 4.
// A range list is an aggregate of these ranges: [1, 5), [10, 11), [100, 201)


public class RangeList {
    // 结果
    private List<int[]> intervals = new ArrayList<>();

    // toString 使用的静态常量
    private static final String LEFT = "[";
    private static final String RIGHT = ")";
    private static final String FLAG = ", ";
    private static final String BLANK = " ";

    /**
     * junit单元测试
     */
    @Test
    public void test() {
        RangeList rl = new RangeList();
        System.out.println(rl.toString()); // Should be ""
        Assert.assertEquals(rl.toString(), "");
        rl.add(1, 5);
        //rl.add(new int[]{1, 5});
        System.out.println(rl.toString()); // Should be: "[1, 5)"
        Assert.assertEquals(rl.toString(), "[1, 5)");
        rl.add(10, 20);
        System.out.println(rl.toString()); // Should be: "[1, 5) [10, 20)"
        Assert.assertEquals(rl.toString(), "[1, 5) [10, 20)");
        rl.add(20, 20);
        System.out.println(rl.toString()); // Should be: "[1, 5) [10, 20)"
        Assert.assertEquals(rl.toString(), "[1, 5) [10, 20)");
        rl.add(20, 21);
        System.out.println(rl.toString()); // Should be: "[1, 5) [10, 21)"
        Assert.assertEquals(rl.toString(), "[1, 5) [10, 21)");
        rl.add(2, 4);
        System.out.println(rl.toString()); // Should be: "[1, 5) [10, 21)"
        Assert.assertEquals(rl.toString(), "[1, 5) [10, 21)");
        rl.add(3, 8);
        System.out.println(rl.toString()); // Should be: "[1, 8) [10, 21)"
        Assert.assertEquals(rl.toString(), "[1, 8) [10, 21)");
        rl.remove(10, 10);
        System.out.println(rl.toString()); // Should be: "[1, 8) [10, 21)"
        Assert.assertEquals(rl.toString(), "[1, 8) [10, 21)");
        rl.remove(10, 11);
        System.out.println(rl.toString()); // Should be: "[1, 8) [11, 21)"
        Assert.assertEquals(rl.toString(), "[1, 8) [11, 21)");
        rl.remove(15, 17);
        System.out.println(rl.toString()); // Should be: "[1, 8) [11, 15) [17, 21)"
        Assert.assertEquals(rl.toString(), "[1, 8) [11, 15) [17, 21)");
        rl.remove(3, 19);
        System.out.println(rl.toString()); // Should be: "[1, 3) [19, 21)"
        Assert.assertEquals(rl.toString(), "[1, 3) [19, 21)");
        // 新增移除区间不存在的情况
        rl.remove(4, 18);
        System.out.println(rl.toString()); // Should be: "[1, 3) [19, 21)"
        Assert.assertEquals(rl.toString(), "[1, 3) [19, 21)");
        // 新增添加区间覆盖所有分区的情况
        rl.add(1, 21);
        System.out.println(rl.toString()); // Should be: "[1, 21)"
        Assert.assertEquals(rl.toString(), "[1, 21)");
        // 新增移除区间覆盖所有分区的情况
        rl.remove(1, 21);
        System.out.println(rl.toString()); // Should be: ""
        Assert.assertEquals(rl.toString(), "");
    }


    void add(int start, int end) {
        add(new int[]{start, end});
    }

    /**
     * 新增一个区间到区间列表中
     *
     * @param range - 整数数组
     */
    void add(int[] range) {
        // 参数检查
        if (!checkParams(range)) {
            return;
        }
        // 原来的区间为空
        if (intervals.isEmpty()) {
            intervals.add(range);
        }
        // 存储新增&合并后的结果
        ArrayList<int[]> res = new ArrayList<>();
        // 记录res是否已经add输入的区间
        boolean hadInsert = false;
        for (int[] item : intervals) {
            // 1 不相交,后续元素存在相交可能性
            // 新增区间 = [10,12)
            // 遍历节点item = [6,8)
            if (item[1] < range[0]) {
                res.add(item);
                continue;
            }
            // 2 不相交,当前遍历节点start比输入的end大,在当前节点item前插入新节点,然后中止插入流程
            // 新增区间 = [1,3)
            // 遍历节点item = [6,8)
            if (item[0] > range[1]) {
                if (!hadInsert) {
                    res.add(range);
                    hadInsert = true;
                }
                res.add(item);
                continue;
            }
            // 3 以下是相交的情况
            // 3.1 新增区间完全包含覆盖遍历的节点item区间,丢弃或移除遍历节点
            // 新增区间 = [5,10)
            // 遍历节点item = [6,8)
            if (item[0] > range[0] && item[1] < range[1]) {
                continue;
            }
            // 3.2 新增区间前半部分与遍历的节点item相交,扩展新增区间start的范围至item[0]
            // 新增区间(原来) = [5,10)
            // 遍历节点item = [4, 6)
            // 新增区间(更新后) = [4,10)
            if (item[0] < range[0]) {
                range[0] = item[0];
            }
            // 3.3 新增区间后半部分与遍历的节点item相交,扩充新增区间end的范围至item[1]
            // 新增区间(原来) = [5,10)
            // 遍历节点item = [8, 12)
            // 新增区间(更新后) = [5,12)
            if (item[1] > range[1]) {
                range[1] = item[1];
            }
        }
        // 4 边界处理,可能需要把新增区间插入到结果列表中
        int[] last = res.size() == 0 ? range : res.get(res.size() - 1);
        if (res.size() == 0 || last[1] < range[0]) {
            res.add(range);
        }
        intervals = res;
    }

    void remove(int start, int end) {
        remove(new int[]{start, end});
    }

    /**
     * 从区间列表中移除一个区间
     *
     * @param range 移除区间
     */
    void remove(int[] range) {
        // 参数检查
        if (!checkParams(range)) {
            return;
        }
        // 原来的区间为空
        if (intervals.isEmpty()) {
            return;
        }
        // 存储新增&合并后的结果
        ArrayList<int[]> res = new ArrayList<>();
        for (int[] item : intervals) {
            // 1 不相交,直接加入到结果集中
            // 移除区间range = [10,12)
            // 遍历节点item = [6,8) 或 [14,15)
            if (range[1] <= item[0] || range[0] >= item[1]) {
                res.add(item);
                continue;
            }
            // 2 以下是相交的情况
            // 2.1 完全移除:移除区间range完全包含或覆盖遍历的节点item区间
            // 移除区间range = [5,10)
            // 遍历节点item = [6,8)
            if (range[0] <= item[0] && range[1] >= item[1]) {
                continue;
            }
            // 移除部分区间
            if (range[0] <= item[1]) {
                if (range[1] >= item[1]) {
                    // 2.2 移除后部分:移除区间range前部与遍历的节点item后部相交,缩短遍历节点item的end范围至range[0]
                    // 移除区间range =      [5,10)
                    // 遍历节点item =       [4,6)
                    // 遍历节点item(更新后) = [4,5)
                    item[1] = range[0];
                    res.add(item);
                } else {
                    // 2.3 移除中间部分:原来区间拆分成[item[0], range[0])与[range[1], item[1]) 2部分
                    // 移除区间range =      [5,10)
                    // 遍历节点item =          [4,10)
                    // 遍历节点item(更新后) =   [7,8)
                    // 遍历节点拆分成2部分 =     [4,7) [8,10)
                    if (range[0] > item[0]) {
                        res.add(new int[]{item[0], range[0]});
                    }
                    res.add(new int[]{range[1], item[1]});
                }
                continue;
            }
            // 2.4 移除前部分:移除区间range后部分与遍历的节点item前部相交,缩短遍历节点start范围至range[1]
            // 移除区间range =      [5,10)
            // 遍历节点item =       [8,12)
            // 遍历节点item(更新后)= [10,12)
            if (range[1] > item[0]) {
                item[0] = range[1];
                res.add(item);
            }
        }
        intervals = res;
    }

    /**
     * 把区间列表转换成字符串
     *
     * @return string
     */
    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        if (intervals.isEmpty()) {
            return builder.toString();
        }
        for (int i = 0; i < intervals.size(); i++) {
            int[] item = intervals.get(i);
            // 非第1个元素前面需要加1个空格
            if (i >= 1) {
                builder.append(BLANK);
            }
            builder.append(LEFT).append(item[0]).append(FLAG).append(item[1]).append(RIGHT);
        }

        return builder.toString();
    }

    /**
     * 参数校验
     *
     * @param range 数组区间
     * @return boolean true=校验通过,false=校验不通过
     */
    private boolean checkParams(int[] range) {
        // 参数及长度核验
        if (range == null || range.length < 2) {
            return false;
        }
        // 参数值核验
        return range[0] <= range[1];
    }
}

        

到了这里,关于整数数组区间的插入与删除的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 算法leetcode|57. 插入区间(rust重拳出击)

    给你一个 无重叠的 ,按照区间起始端点排序的区间列表。 在列表中插入一个新的区间,你需要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。 0 = intervals.length = 10 4 intervals[i].length == 2 0 = intervals[i][0] = intervals[i][1] = 10 5 intervals 根据 intervals[i][0] 按

    2024年02月09日
    浏览(51)
  • JAVA实现存在更新不存在插入与及多余的进行删除(三)

    这个版本,主要是迭代重载了下save方法,不废话,直接上代码: 具体实现类对应的重载方法如下: 然后就是头部加多了 implements ICudDataServiceT, ApplicationContextAware。 通过这个ApplicationContextAware获取到所有bean服务,肤浅地以实体类拼凑一下服务名,找到bean服务就作为这个调用的

    2024年02月13日
    浏览(47)
  • 数组低效的“插入”和“删除”

    插入操作 假设数组的长度为 n,现在,如果我们需要将一个数据插入到数组中的第 k 个位置。为了把第 k 个位置腾出来,给新来的数据,我们需要将第 k~n 这部分的元素都顺序地往后挪一位。那插入操作的时间复杂度是多少呢? 如果在数组的末尾插入元素,那就不需要移动

    2024年02月03日
    浏览(43)
  • Python 算法基础篇之数组和列表:创建、访问、添加和删除元素

    在算法和数据结构中,数组和列表是常见的数据结构,用于存储和操作一组数据。在 Python

    2024年02月16日
    浏览(41)
  • 【华为OD机考 统一考试机试C卷】寻找连续区间/数组连续和(C++ Java JavaScript Python C语言)

    目前在考C卷,经过两个月的收集整理, C卷真题已基本整理完毕 抽到原题的概率为2/3到3/3, 也就是最少抽到两道原题。 请注意:大家刷完C卷真题,最好要把B卷的真题刷一下,因为C卷的部分真题来自B卷。 另外订阅专栏还可以联系笔者开通在线OJ进行刷题,提高刷题效率。

    2024年02月19日
    浏览(43)
  • 2023华为OD机试真题【区间交叠/贪心算法】【Python Java】

    给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。 输入描述 第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”, x和y 分别表示起点和终点,取值范围是

    2024年02月13日
    浏览(47)
  • 2023华为OD机试真题【区间交叠/贪心算法】【Python Java C++】

    给定坐标轴上的一组线段,线段的起点和终点均为整数并且长度不小于1,请你从中找到最少数量的线段,这些线段可以覆盖住所有线段。 输入描述 第一行输入为所有线段的数量,不超过10000,后面每行表示一条线段,格式为”x,y”, x和y 分别表示起点和终点,取值范围是

    2024年02月13日
    浏览(56)
  • Excel处理控件Aspose.Cells教程:Java 在 Excel 中插入和删除行和列

    Aspose.Cells 是Excel电子表格编程API,可加快电子表格的管理和处理任务,支持构建能够生成,修改,转换,呈现和打印电子表格的跨平台应用程序。同时不依赖于Microsoft Excel或任何Microsoft Office Interop组件, Aspose API 支持旗下产品覆盖文档、图表、PDF、条码、OCR、CAD、HTML、电子

    2024年02月01日
    浏览(45)
  • LeetCode-Java:26.删除有序数组的重复项

    给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k ,你需要做以下事情确保你的题解可以被通过

    2024年02月05日
    浏览(45)
  • Java高级语言实现插入排序算法

    【引言】 插入排序算法是一种简单且常用的排序算法。它通过依次将未排序的元素插入已排序序列中的正确位置来达到排序的目的。本文将使用Java高级语言实现插入排序算法,并讲解其核心思想和代码实现。 【算法思想】 插入排序的核心思想是通过构建有序序列,对于未排

    2024年02月11日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包