代码编织梦想

 目录链接:

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目:

https://github.com/September26/java-algorithms

原题链接:力扣


描述:

给你一个区间数组 intervals ,其中 intervals[i] = [starti, endi] ,且每个 starti 都 不同 。

区间 i 的 右侧区间 可以记作区间 j ,并满足 startj >= endi ,且 startj 最小化 。

返回一个由每个区间 i 的 右侧区间 的最小起始位置组成的数组。如果某个区间 i 不存在对应的 右侧区间 ,则下标 i 处的值设为 -1 。

 
示例 1:

输入:intervals = [[1,2]]
输出:[-1]
解释:集合中只有一个区间,所以输出-1。
示例 2:

输入:intervals = [[3,4],[2,3],[1,2]]
输出:[-1,0,1]
解释:对于 [3,4] ,没有满足条件的“右侧”区间。
对于 [2,3] ,区间[3,4]具有最小的“右”起点;
对于 [1,2] ,区间[2,3]具有最小的“右”起点。
示例 3:

输入:intervals = [[1,4],[2,3],[3,4]]
输出:[-1,2,-1]
解释:对于区间 [1,4] 和 [3,4] ,没有满足条件的“右侧”区间。
对于 [2,3] ,区间 [3,4] 有最小的“右”起点。
 

提示:

1 <= intervals.length <= 2 * 104
intervals[i].length == 2
-106 <= starti <= endi <= 106
每个间隔的起点都 不相同


来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/find-right-interval
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路:

* 解题思路:
* 这题涉及到两次排序,为了方便理解,我们构建Model来存储这关系。Model记录start,end,和在intervals的位置index。
* 然后分别以start和end排序,生成两个集合startList和endList。
* 然后遍历endList,同时也从startList中取值。如果startList中的start大于endlist中的end。则代表符合,则记录其index。
* 如果找不到,则记录-1

代码:

public class Solution436 {

    public int[] findRightInterval(int[][] intervals) {
        Map<Integer, Model> map = new HashMap<>();
        for (int i = 0; i < intervals.length; i++) {
            Model model = new Model(intervals[i][0], intervals[i][1], i);
            map.put(i, model);
        }
        List<Model> startList = new ArrayList<>(map.values());
        startList.sort(new Comparator<Model>() {
            @Override
            public int compare(Model o1, Model o2) {
                return o1.start - o2.start;
            }
        });
        List<Model> endList = new ArrayList<>(map.values());
        endList.sort(new Comparator<Model>() {
            @Override
            public int compare(Model o1, Model o2) {
                return o1.end - o2.end;
            }
        });

        int[] result = new int[intervals.length];
        int startIndex = 0;
        for (Model endModel : endList) {
            Model startModel = null;
            while (startIndex < startList.size()) {
                Model model = startList.get(startIndex);
                if (model.start >= endModel.end) {
                    startModel = model;
                    break;
                }
                startIndex++;
            }
            if (startModel == null) {
                result[endModel.index] = -1;
            } else {
                result[endModel.index] = startModel.index;
            }
        }
        return result;
    }

    static class Model {
        int start = 0;
        int end = 0;
        int index = 0;

        Model(int start, int end, int index) {
            this.start = start;
            this.end = end;
            this.index = index;
        }
    }

}

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/rzleilei/article/details/124880180

力扣刷题系列——分治算法-爱代码爱编程

分治法的基本思想及算法题 分治法 1.基本思想 (1) 将求解的较大规模的问题分割成k个更小规模的子问题。 (2) 对这k个子问题分别求解。如果子问题的规模仍然不够小,则再划分为k个子问题,如此递归的进行下去,直到问题规模足够小,很容易求出其解为止。 (3) 将求出的小规模的问题的解合并为一个更大规模的问题的解,自底向上逐步求出原来问题的

【算法&面试】分治算法 归并 递归 力扣 493. 翻转对 327. 区间和的个数-爱代码爱编程

分治算法是啥? 分治算法也有动态规划和贪心算法的概念,动态规划:把大问题分解成一步一步的小问题,递归解决。贪心算法:每次得到局部最优解。 分治算法:把大问题分解成小问题,汇总所有小问题的结果。快排、二分查找都是典型的分治算法。 JDK中的Fork-Join就是一个典型的并行的分治框架。它的主要作用是把大任务分割成若干个小任务,再对每个小任务得到的结果

力扣---数组专题I (简单)-爱代码爱编程

题目名称 1.867--转置矩阵--简单2.面试题 17.10. 主要元素3. 977-有序数组的平方4. 628-三个数的最大乘积5. 219-存在重复元素II6. 228-汇总区间7.1-两数之和8.167-两数之和II-输入有序数组 1.867–转置矩阵–简单 (1)题目条件: (2)题解: 该题的目的是对已知矩阵进行转置,由于矩阵的

动态规划解法汇总-爱代码爱编程

1.最长不重复子串 自己一开始想的建一个int[] res;res[i]代表以第i个字符开头的字符串的最长字串长度,但是写起来其实就是暴力搜索,最后超时了。 题解: 状态定义: 设动态规划列表 dp ,dp[j] 代表以字符 s[j]为结尾的 “最长不重复子字符串” 的长度。 转移方程: 固定右边界 j ,即字符串一定包含字符s[j],设字符 s

Leetcode-228.汇总区间-爱代码爱编程

题目背景 给定一个无重复元素的有序整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出: “a->b” ,如果 a != b “a”

力扣【剑指offer】题目汇总与总结-爱代码爱编程

本文为《剑指offer》刷题笔记的总结,花费不到两个月的时间将力扣上《剑指offer》的75道题刷了一遍,遇到不会的知识点或者应该做一些记录的题目都将其写在了往日的博客里。 整体来看,这75道题,涉及到常用的数据结构:数组、字符串、链表、栈、队列、树、图,还有一些常用的数据操作和算法:二分法、哈希表、递归、排序、查找、位运算、动态规划、回溯、滑动窗口、双

​力扣解法汇总689-三个无重叠子数组的最大和-爱代码爱编程

原题链接:力扣 描述: 给你一个整数数组 nums 和一个整数 k ,找出三个长度为 k 、互不重叠、且全部数字和(3 * k 项)最大的子数组,并返回这三个子数组。 以下标的数组形式返回结果,数组中的每一项分别指示每个子数组的起始位置(下标从 0 开始)。如果有多个结果,返回字典序最小的一个。 示例 1: 输入:nums = [1,2,1

力扣解法汇总1610-可见点的最大数目-爱代码爱编程

原题链接:力扣 描述: 给你一个点数组 points 和一个表示角度的整数 angle ,你的位置是 location ,其中 location = [posx, posy] 且 points[i] = [xi, yi] 都表示 X-Y 平面上的整数坐标。 最开始,你面向东方进行观测。你 不能 进行移动改变位置,但可以通过 自转 调整观测角度。换句

​力扣解法汇总1044-最长重复子串-爱代码爱编程

原题链接:力扣 描述: 给你一个字符串 s ,考虑其所有 重复子串 :即,s 的连续子串,在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。 返回 任意一个 具有最长长度的重复子串。如果 s 不含重复子串,那么答案为 "" 。 示例 1: 输入:s = "banana" 输出:"ana" 示例 2: 输入:s = "abcd" 输

力扣解法汇总33-搜索旋转排序数组-爱代码爱编程

原题链接:力扣 描述: 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k

力扣解法汇总41-缺失的第一个正数-爱代码爱编程

原题链接:力扣 描述: 给你一个未排序的整数数组 nums ,请你找出其中没有出现的最小的正整数。 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。   示例 1: 输入:nums = [1,2,0] 输出:3 示例 2: 输入:nums = [3,4,-1,1] 输出:2 示例 3: 输入:nums = [7,8,9

python 常用排序-爱代码爱编程

目录 list自带排序一维二维方法一方法二:需要按多个key排序的时候可以用lambdadic 自带排序快速排序堆排序归并排序归并排序在链表排序中的应用归并排序在统计逆序对上的应用 list自带排序 一维 reverse = True 降序, reverse = False 升序(默认) 不需要返回值,nums就可以被修改 nums.so

汇总区间Python解法-爱代码爱编程

给定一个 无重复元素 的 有序 整数数组 nums 。 返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说,nums 的每个元素都恰好被某个区间范围所覆盖,并且不存在属于某个范围但不属于 nums 的数字 x 。 列表中的每个区间范围 [a,b] 应该按如下格式输出: "a->b" ,如果 a != b "a" ,如果 a =

力扣相似题目汇总-爱代码爱编程

数组数字、字符串相加、相乘 相加 1两数之和 15三数之和 16最接近的三数之和 18. 四数之和 2. 两数相加 67. 二进制求和​​​​​​ 415. 字符串相加 29. 两数相除 未写 445两数相加|| 371两整数之和 相乘 43. 字符串相乘 整数转变 7. 整数反转 (涉及 越界问题,官方给的是

力扣解法汇总2100-适合打劫银行的日子-爱代码爱编程

原题链接:力扣 描述: 你和一群强盗准备打劫银行。给你一个下标从 0 开始的整数数组 security ,其中 security[i] 是第 i 天执勤警卫的数量。日子从 0 开始编号。同时给你一个整数 time 。 如果第 i 天满足以下所有条件,我们称它为一个适合打劫银行的日子: 第 i 天前和后都分别至少有 time 天。 第 i 天前连续

力扣刷题记录-爱代码爱编程

目录 力扣 222. 完全二叉树的节点个数力扣 110. 平衡二叉树力扣 257. 二叉树的所有路径力扣 404. 左叶子之和力扣 513. 找树左下角的值力扣 112. 路径总和力扣 113. 路径总和 II