hot150-06-矩阵
...大约 12 分钟
难度说明：🟢简单🟡中等🔴困难
hot150-06-矩阵
🟢01-汇总区间（228）
1.题目内容
给定一个 无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
"a->b"，如果a != b"a"，如果a == b
示例 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"
2.题解思路
分析：数组本身有序，因此题意可以转化为查找连续序列的区间，即通过一次遍历数组进行检索，分组循环概念
- 例如从
[start,i-1]是一段区间，下一段区间从i开始
// 分组循环模板参考
int i, n = len（长度）
while i < n:
start = i
while i < n and ...:
i += 1
# 从 start 到 i-1 是一段
# 下一段从 i 开始，无需 i+=1
👻方法1：一次遍历
- 思路分析：遍历数组元素，当遇到相邻元素之间大于1的情况则得到一个区间（说明连续序列断掉了），每次记录区间的左右值（left，right）（left记录区间起点，right记录区间终点）
- 如果left == right 说明只有1个元素，对应表示为"left"或者"right"
- 如果left < right 说明这是一个区间，对应表示为"left-->right"
- 算法思路：
- 分组循环：记录每个区间的起点和终点（
[start,i-1]为一个区间） - 结构构建：根据区间的起点和终点分别构建结果字符串，并加入结果集
- 分组循环：记录每个区间的起点和终点（
public class Solution1 {
/**
* 题目数组本身有序，不需额外排序，此处可将题意转化为分拆数组中的连续区间段
*/
public List<String> summaryRanges(int[] nums) {
// 定义响应结果
List<String> res = new ArrayList<>();
int i = 0;
int n = nums.length;
while (i < n) {
int left = i;
i++;
while (i < n && (nums[i] - nums[i - 1] == 1)) {
i++;
}
int right = i - 1; // 连续序列断开，区间取值为[left,right]=[start,i-1]
// 构建区间结果（判断left、right）
StringBuffer sb = new StringBuffer();
if (left == right) {
// 说明只有一个元素
sb.append(nums[left]);
} else if (left < right) {
// 说明是一个区间
sb.append(nums[left]).append("-->").append(nums[right]);
}
// 将区间结果加入结果集合
res.add(sb.toString());
}
// 返回结果
return res;
}
}
复杂度分析
时间复杂度：O（n） n为数组长度
空间复杂度：O（1）常数级别空间使用
🟡02-合并区间（56）
1.题目内容
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 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] 可被视为重叠区间。
2.题解思路
👻方法1：排序+滚动比较
- 思路分析：
- （1）排序：将区间按照左阈值进行排序（通过重写Comparable接口实现）
- （2）滚动比较：初始化一个比较区间（即将数组的第一个区间作为比较区间），由于左阈值本身有序，因此在判断合并的时候只需要关注比较区间的右阈值和下一个待合并的区间的关系，确认其是否可以合并
- 初始化比较区间：left、right 分别指向intervals第一个区间的左右阈值
- 滚动比较：从下标1开始，循环比较每一个待合并的区间，确认合并的范围和变化
cur = intervals[i]cur 指向当前待合并的区间，因此需要将right与cur[0],cur[1]区间进行比较right < cur[0]：两个区间没有交集，则可以直接将cur加入结果集，并将比较区间指向cur（表示cur被加入结果集，会作为新的比较区间与下一个待合并的区间进行比较）right >= cur[0]：两个区间存在交集，则进一步判断右边界阈值right > cur[1]：说明当前比较区间覆盖了cur，因此不需要做任何变化，继续下一个区间比较right <= cur[1]：说明cur的区间范围较大，因此需要变更right指向cur[1]（更新比较区间），然后继续下一个区间的比较
- 比较区间处理：当所有的区间遍历完成之后，需要将这个一直滚动比较的区间加入结果集（因为它是在过程中一直比较、变动的），因此需要在最后将其加入结果集
- （3）返回结果集
/**
* 056 合并区间
*/
public class Solution1 {
/**
* 对集合左区间进行排序，随后依次遍历更新区间
*/
public int[][] merge(int[][] intervals) {
// 定义集合存储结果集
List<int[]> res= new ArrayList<>();
// 排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
// 选定一个起始区间进行比较(left\right 始终指向当前最新的比较区间（与遍历的区间元素进行比较）)
int left = intervals[0][0];
int right = intervals[0][1];
/**
* 遍历区间（校验合并）: 左侧区间有序，此处则以右边界为基础进行判断
* right : [cur[0]，cur[1]]
* right < cur[0] 没有可合并的空间，直接将{left,right}加入结果集，并将比较的point指向cur
* right >= cur[0] 存在合并空间，进一步判断cur[1]
* - right <= cur[1] , 合并后为[left,cur[1]]
* - right > cur[1] , 合并后为[left,right] 其作为一个新的区间进入下一个区间比较（即更新比较区间）
*/
for(int i = 0;i<intervals.length;i++){
int[] cur = intervals[i];
if(right<cur[0]){
// 无可合并区间，直接加入结果集，当前比较区间指向cur
res.add(new int[]{left,right});
left = cur[0];
right = cur[1];
}else if(right >= cur[0]){
if(right <= cur[1]){
right = cur[1];
}
}
}
// 遍历完成，将一直滚动比较的比较区间加入结果集
res.add(new int[]{left,right});
// 返回结果
return res.toArray(new int[res.size()][]);
}
}
复杂度分析
时间复杂度：
空间复杂度：
🟡03-插入区间（57）
1.题目内容
给你一个 无重叠的 *，*按照区间起始端点排序的区间列表 intervals，其中 intervals[i] = [starti, endi] 表示第 i 个区间的开始和结束，并且 intervals 按照 starti 升序排列。同样给定一个区间 newInterval = [start, end] 表示另一个区间的开始和结束。
在 intervals 中插入区间 newInterval，使得 intervals 依然按照 starti 升序排列，且区间之间不重叠（如果有必要的话，可以合并区间）。
返回插入之后的 intervals。
注意 你不需要原地修改 intervals。你可以创建一个新数组然后返回它。
2.题解思路
👻方法1：插入+排序+合并
- 思路分析
- 此题实际和【合并区间】是一个类型的考察，可以将构建一个新集合copy源数组，随后将新区间也插入新集合中
- 随后可将题意转化为【合并区间】：排序+合并
- 因为数组本身有序，还有一种思路就是找到插入位置，然后进行插入，确认插入后是否需要合并以及合并带来的联动影响
/**
* 057 插入区间
*/
public class Solution1 {
/**
* 插入区间：intervals按照升序排列，插入一个新区间newInterval，确保插入后区间不重叠，需合并区间
* 1.插入新区间，构建一个新的集合
* 2.对新集合进行合并操作
*/
public int[][] insert(int[][] intervals, int[] newInterval) {
// 获取区间个数
int n = intervals.length;
// 边界条件判断
if(n==0){
return new int[][]{{newInterval[0],newInterval[1]}};
}
// 1.构建新数组，将新区间插入
int[][] tempIntervals = new int[n + 1][intervals[0].length + 1];
System.arraycopy(intervals, 0, tempIntervals, 0, n);
tempIntervals[intervals.length] = newInterval;
// 2.对新的集合进行合并区间操作
/**
* 合并区间：
* 排序：根据left左边界进行排序
* 合并：初始化point（left,right），左边界有序，根据右边界确认是否要进行合并
* right 与 [cur[0],cur[1]]进行比较
* right < cur[0] 无公共部分，直接将cur加入结果集，随后point指向cur（更新指针区间）
* right >= cur[0] 存在公共部分，进一步确定合并缺件
* - right <= cur[1]: cur覆盖范围大，则需更新right，构建新point
* - right > cur[1]:point覆盖范围大，无需操作，继续下一个区间判断
*/
// 左区间排序
Arrays.sort(tempIntervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0];
}
});
List<int[]> res = new ArrayList<>();
// 定义指针区间point 指向当前校验的区间
int left = tempIntervals[0][0];
int right = tempIntervals[0][1];
// 遍历区间元素，校验合并
for (int i = 1; i < tempIntervals.length; i++) {
int[] cur = tempIntervals[i];
if (right < cur[0]) {
res.add(new int[]{left,right});
left = cur[0];
right = cur[1];
} else {
if (right <= cur[1]) {
right = cur[1];
}
}
}
// 遍历完成需将point加入结果集
res.add(new int[]{left, right});
// 返回结果集
return res.toArray(new int[res.size()][]);
}
}
复杂度分析
时间复杂度：
空间复杂度：
🟡04-用最少数量的箭引爆气球（452）
1.题目内容
有一些球形气球贴在一堵用 XY 平面表示的墙面上。墙面上的气球记录在整数数组 points ，其中points[i] = [xstart, xend]表示水平直径在 xstart 和 xend之间的气球。你不知道气球的确切 y 坐标。
一支弓箭可以沿着 x 轴从不同点 完全垂直 地射出。在坐标 x 处射出一支箭，若有一个气球的直径的开始和结束坐标为 xstart，xend， 且满足 xstart≤ x ≤ xend，则该气球会被 引爆 。可以射出的弓箭的数量 没有限制 。 弓箭一旦被射出之后，可以无限地前进。
给你一个数组 points ，返回引爆所有气球所必须射出的 最小 弓箭数
示例 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]。
2.题解思路
👻方法1：右区间排序+右端点射击
思路分析：根据区间结束位置从小到大进行排序，将射击点选择在区间的右端点，判断射击指定区间是否需要消耗箭，则只需要判断待射击区间的左端点是否小于point，如果小于则说明有向右的重合部分，不需要消耗箭，反之没有重叠部分的气球需要消耗一个弓箭，并且更新下一个射击点
- （1）右区间排序：此处要用三目运算符
Arrays.sort(points, (p1, p2) -> p1[1] < p2[1] ? -1 : 1);(如果直接用return p1[1]-p1[2]则可能出现这个值超出Integer.MIN_VALUE导致出错，或者将数组转为long类型) - （2）右端点射击：初始化一个射击点
point（第一个区间的右端点），如果下一个待射击区间cur(cur[0],cur[1])的左端点cur[0]<=point则说明两个区间存在重合部分，因此不需要额外消耗箭。反之则需要消耗箭数，并更新下一个射击点进行比较（将射击点选在交集区间的右端点，则不需要维护整个区间，只需要维护端点）
/** * 452 用最少的箭射击气球 */ public class Solution1 { /** * 思路：右区间排序+右端点射击 * 1.右区间排序（按照区间的结束位置从小到大进行排序） * 2.右端点射击（选定第一个射击点point为第一个区间的右端点，分别和后面的区间cur(cur[0],cur[1])进行比较 * - 如果存在交集（即cur[0]<=point说明存在重合部分，不需要消耗箭数） * - 反之如果cur[0]>point 则说明不存在重合部分，需要消耗1箭，并更新下一个射击点的位置继续进行比较，以此类推 */ public int findMinArrowShots(int[][] points) { int len = points.length; if (len == 1) { return 1; } // 对数组进行排序(按照右侧区间进行排序) // Arrays.sort(points, (p1,p2)->{ return p1[1]<p2[1]?-1:1 ;}); Arrays.sort(points, (o1, o2) -> Integer.compare(o1[1], o2[1])); int count = 1; // 初始化射箭数量 int point = points[0][1]; // 初始化第1个射击点 for (int i = 0; i < points.length; i++) { if (points[i][0] > point) { // 不存在重合区间，需消耗1箭，并更新下一个射击点 count++; point = points[i][1]; // 下一个射击点区间的右端点 } } // 返回结果 return count; } }- （1）右区间排序：此处要用三目运算符
复杂度分析
时间复杂度：
空间复杂度：
// 同理：确定交集区间的一个端点，构建思路
class Solution {
public int findMinArrowShots(int[][] points) {
int len = points.length;
if(len==1) return 1;
Arrays.sort(points,(o1, o2) -> Integer.compare(o2[0], o1[0]));
int count = 1;
int point = points[0][0];
for(int i=1;i<len;i++){
if(point>points[i][1])
{
count++;
point=points[i][0];
}
}
return count;
}
}
Powered by Waline v3.1.3