昆明网站建设咨询,百度推广自己怎么做,域名到期如何续费,河南商务网站建设区间
228. 汇总区间
题目
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说#xff0c;nums 的每个元素都恰好被某个区间范围所覆盖#xff0c;并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中…区间
228. 汇总区间
题目
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说nums 的每个元素都恰好被某个区间范围所覆盖并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出
a-b 如果 a ! b
a 如果 a b
提示
0 nums.length 20
-2^31 nums[i] 2^31 - 1
nums 中的所有值都 互不相同
nums 按升序排列
示例 1
输入nums [0,1,2,4,5,7]
输出[0-2,4-5,7]
解释区间范围是
[0,2] -- 0-2
[4,5] -- 4-5
[7,7] -- 7示例 2
输入nums [0,2,3,4,6,8,9]
输出[0,2-4,6,8-9]
解释区间范围是
[0,0] -- 0
[2,4] -- 2-4
[6,6] -- 6
[8,9] -- 8-9解析
因为是有序数组直接按照题意模拟即可。
遍历数组连续则继续不连续就断开记录。
代码
class Solution {public ListString summaryRanges(int[] nums) {int nnums.length;boolean flagfalse;int l-1,r-1;ArrayListString ans new ArrayList();for (int i0;in;i){if (!flag) {lnums[i];rl;flagtrue;}else{if (nums[i]nums[i-1]1){rnums[i];}else{if (lr) ans.add(r);else ans.add(l-r);i--;flagfalse;}}}if (flag) {if (lr) ans.add(r);else ans.add(l-r);}return ans;}
}56. 合并区间
题目
以数组 intervals 表示若干个区间的集合其中单个区间为 intervals[i] [starti, endi] 。
请你合并所有重叠的区间并返回 一个不重叠的区间数组该数组需恰好覆盖输入中的所有区间 。
提示
1 intervals.length 1e4
intervals[i].length 2
0 starti endi 1e4
示例 1
输入intervals [[1,3],[2,6],[8,10],[15,18]]
输出[[1,6],[8,10],[15,18]]
解释区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].示例 2
输入intervals [[1,4],[4,5]]
输出[[1,5]]
解释区间 [1,4] 和 [4,5] 可被视为重叠区间。解析
首先先对二维数组进行排序按照左端点从小到大排序
之后就是判断上个区间的右端点和下个区间的左端点是否能接上能接上就说明是同一个区间的继续遍历否则就断开将上个区间的左端点和右端点记录在答案中
之后就是处理其他问题如判断最后的一块区间是否已经在答案中答案的格式转化等。
代码
class Solution {public int[][] merge(int[][] intervals) {int nintervals.length;Arrays.sort(intervals,(a,b)-{if (a[0]!b[0]) return a[0]-b[0];return a[1]-b[1];});int l-1,r-1,l1-1,r1-1;ArrayListListInteger res new ArrayList();for (int i0;in;i){int aintervals[i][0],bintervals[i][1];if (ra){if (l-1){la;rb;}else{res.add(List.of(l,r));l1l;r1r;la;rb;}}else {rMath.max(r,b);}}if (r1!r){res.add(List.of(l,r));}int[][] ans new int[res.size()][];for (int i0;ires.size();i){var kres.get(i);ans[i]new int[k.size()];for (int j0;jk.size();j){ans[i][j]k.get(j);}}
// for (int i0;ires.size();i){
// for (int j0;j2;j) System.out.print(ans[i][j] );
// System.out.println();
// }return ans;}
}57. 插入区间
题目
给你一个 无重叠的 按照区间起始端点排序的区间列表 intervals其中 intervals[i] [starti, endi] 表示第 i 个区间的开始和结束并且 intervals 按照 starti 升序排列。
同样给定一个区间 newInterval [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval使得 intervals 依然按照 starti 升序排列且区间之间不重叠如果有必要的话可以合并区间。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
提示
0 intervals.length 1e4
intervals[i].length 2
0 starti endi 1e5
intervals 根据 starti 按 升序 排列
newInterval.length 2
0 start end 1e5
示例 1
输入intervals [[1,3],[6,9]], newInterval [2,5]
输出[[1,5],[6,9]]示例 2
输入intervals [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval [4,8]
输出[[1,2],[3,10],[12,16]]
解释这是因为新的区间 [4,8] 与 [3,5],[6,7],[8,10] 重叠。解析
因为这个一个按照左端点从小到大排序好的数组所以不需要我们排序了。
遍历数组一共就3种情况。假设newInterval的值是l和r。
遍历数组时数组的右端点小于l说明数组第i区间与[l,r]无重叠
之后可能会出现lintervals[i][1]的情况根据这种情况有判断好几种可能性部分重叠完全覆盖不重叠。但是有一个共同特点如果有覆盖的地方那么r一定在第i区间的左端点的右边(可以相等)此时判断一下判断成功就更新l和r继续遍历
直到r小于一个区间的左端点此时后续的空间就跟[l,r]无关了。
代码
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {Listint[] ans new ArrayList();int lnewInterval[0],rnewInterval[1];int nintervals.length;boolean flagtrue;for (int i0;in;i){if (!flag) {int[] anew int[2];aintervals[i];ans.add(a);continue; }if (lintervals[i][1]){int[] anew int[2];aintervals[i];ans.add(a);continue;}if (rintervals[i][0]){lMath.min(l,intervals[i][0]);rMath.max(r,intervals[i][1]);continue;}int[] a{l,r};ans.add(a);flagfalse;i--;}if (flag){int[] a{l,r};ans.add(a);}return ans.toArray(new int[ans.size()][]);}
}452. 用最少数量的箭引爆气球
题目
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points 其中points[i] [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭若有一个气球的直径的开始和结束坐标为 xstartxend 且满足 xstart ≤ x ≤ xend则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后可以无限地前进。
给你一个数组 points 返回引爆所有气球所必须射出的 最小 弓箭数 。
提示:
1 points.length 1e5
points[i].length 2
-2^31 xstart xend 2^31 - 1
示例 1
输入points [[10,16],[2,8],[1,6],[7,12]]
输出2
解释气球可以用2支箭来爆破:
-在x 6处射出箭击破气球[2,8]和[1,6]。
-在x 11处发射箭击破气球[10,16]和[7,12]。示例 2
输入points [[1,2],[3,4],[5,6],[7,8]]
输出4
解释每个气球需要射出一支箭总共需要4支箭。示例 3
输入points [[1,2],[2,3],[3,4],[4,5]]
输出2
解释气球可以用2支箭来爆破:
- 在x 2处发射箭击破气球[1,2]和[2,3]。
- 在x 4处射出箭击破气球[3,4]和[4,5]。解析
这是个贪心题按照左端点从小到大排好序后观察区间的特点就可以发现如果上个区间的右端点比这个区间的左端点大(可以相等),这两个区间就可以被一条箭引爆左端点就没有考虑的必要了都排序好了。之后就是将上个区间右端点不断更新和这个区间的左端点不断地比较直到不合法了就结束上一个区间将现在的区间作为新的“起点” !
但有一个问题就是将数组排序的问题有点坑人因为数据范围进行比较时不能在int的类型下进行做差比较可能会出现溢出的情况。所以可以转化为Long型做差比较或者Integer.compare()方法进行比较。
代码
class Solution {public int findMinArrowShots(int[][] points) {int npoints.length;Arrays.sort(points,(s1,s2)-{if (s1[0]!s2[0])return Integer.compare(s1[0], s2[0]);return Integer.compare(s1[1], s2[1]);});int l-1,r-1;int cnt0;for (int i0;in;i){if (i0){cnt;rpoints[i][1];continue;}if (rpoints[i][0]){rMath.min(r,points[i][1]);}else{cnt;rpoints[i][1];}}return cnt;}
}
