区间部分
- 1. 汇总区间
- 2. 合并区间
- 3. 插入区间
- 4. 用最少数量的箭引爆气球
1. 汇总区间
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
解题思路： 遍历数组，用i记开头，用j记结尾。看看当前元素位置+1的数和当前元素+1的数是不是相同，如果相同则说明是连续的，就让j++即可，如果不连续，判断开头和结尾是不是一样的，如果是一样的，则说明他就是单个，直接放入list，如果不连续，则按规定，加个箭头 i -> j。然后让j继续++,让i = j的位置。重启另一个开头
此外，需要判断一下最后一个值，因为上面有个判断条件，是当前元素位置+1的数和当前元素+1的数是不是相同，最后一个元素不能这么用，所以得另外写，同样看看i和j是不是相等，如果相等则单个，如果不相等，就写i ——> j
class Solution {
public List<String> summaryRanges(int[] nums) {
int i = 0;
int j = 0;
List<String> list = new ArrayList<String>();
while(j < nums.length-1){
if(nums[j+1] == nums[j] + 1){
j++;
}else{
if(j == i){
list.add(String.valueOf(nums[i]));
}else{
list.add(nums[i] + "->" + nums[j]);
}
j++;
i = j;
}
}
if(j == nums.length - 1){
if(i == j){
list.add(String.valueOf(nums[i]));
}else{
list.add(nums[i] + "->" + nums[j]);
}
}
return list;
}
}
2. 合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
解题思路： 本质是一个n*2的数组，先把第一列排序，注意排序器的写法：Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
然后按行遍历这个数组，判断上一行第二个元素是不是大于等于当前行的第一个的第一个元素，然后判断当前行的第二个元素是否大于等于上一行的第二个元素。有了这两个判断条件，才能让end去更新坐标，也就是记录当前的最大值。
否则，也就是上一行第二个元素是不是小于当前行的第一个的第一个元素，此时就得先记录这个区间，也就是开始行的第一个元素作为头，结束行和最后一个元素作为尾巴。并记录到list集合中。然后更新开始行和结束行。
需要处理一个特殊情况，就是最后一个元素如果是连续的，无法写入到list中，所以需要判断，判断条件就是开始行是不是等于行的总长度，如果不相等则说明没写进去，就把两个元素写进即可
最后用toArray得出结果。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<int[]>();
if(intervals.length == 0){
return new int[0][2];
}
int[] start = {0,0};
int[] end = {0,1};
for(int i = 1 ; i < intervals.length; i++){
if(intervals[i][0] <= intervals[end[0]][end[1]]){
if(intervals[i][1] >= intervals[end[0]][end[1]]){
end[0] = i;
end[1] = 1;
}
}else{
int[] res = new int[2];
res[0] = intervals[start[0]][0];
res[1] = intervals[end[0]][1];
merged.add(res);
start[0] = i;
end[0] = i;
}
}
if(start[0] != intervals.length ){
int[] res = new int[2];
res[0] = intervals[start[0]][0];
res[1] = intervals[end[0]][1];
merged.add(res);
}
return merged.toArray(new int[merged.size()][]);
}
}
3. 插入区间
给你一个 无重叠的 ，按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
解题思路： 用上面合并区间的思路，只需要把要插入的区间插入到一个新数组中，然后执行刚才的区间合并的方法，就可以得到最终结论。 注意用法 拷贝一个数组
int[][] re = Arrays.copyOf(intervals,指定长度)。
class Solution {
public int[][] merge(int[][] intervals) {
Arrays.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));
List<int[]> merged = new ArrayList<int[]>();
if(intervals.length == 0){
return new int[0][2];
}
int[] start = {0,0};
int[] end = {0,1};
for(int i = 1 ; i < intervals.length; i++){
if(intervals[i][0] <= intervals[end[0]][end[1]]){
if(intervals[i][1] >= intervals[end[0]][end[1]]){
end[0] = i;
end[1] = 1;
}
}else{
int[] res = new int[2];
res[0] = intervals[start[0]][0];
res[1] = intervals[end[0]][1];
merged.add(res);
start[0] = i;
end[0] = i;
}
}
if(start[0] != intervals.length){
int[] res = new int[2];
res[0] = intervals[start[0]][0];
res[1] = intervals[end[0]][1];
merged.add(res);
}
return merged.toArray(new int[merged.size()][]);
}
public int[][] insert(int[][] intervals, int[] newInterval) {
int[][] re = Arrays.copyOf(intervals,intervals.length + 1);
re[intervals.length] = newInterval;
return merge(re);
}
}
4. 用最少数量的箭引爆气球
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend] 表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart ≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数 。
解题思路： 本质就是找重合区间的最小重合区间，然后看看有多少个最小重合区间。
首先按第一列数字排序。
按行遍历整个数组，第一列取最大值，记录最小重合区间，判断最小重合区间的最大值是否大于等于当前行的最小值，如果大于了则说明该行在最小区间内，则进行最小区间计算，区间最小值取两数最大，区间最大值取两数最小。
否则，则说明这个最小区间没办法覆盖这一行区间，则记录一次最小区间，再继续执行。
特殊情况，遍历到最后一个，如果是连续最小区间，则没办法添加，如果不是连续最小区间，也没办法添加，所以需要再多添加一个x。
最后返回 list,size()。
class Solution {
// 找最小重合度
public int findMinArrowShots(int[][] points) {
List<int[]> res = new ArrayList<int[]>();
Arrays.sort(points,(a,b)->Integer.compare(a[0],b[0]));
int[] x = points[0];
for(int i = 1 ;i < points.length; i++){
if(x[1] >= points[i][0]){
x[0] = Math.max(x[0],points[i][0]);
x[1] = Math.min(x[1],points[i][1]);
}else{
res.add(x);
x = points[i];
}
}
res.add(x);
return res.size();
}
}
