文章目录
- Day 35
- 01. 无重叠区间（No. 435）
- <1> 题目
- <2> 笔记
- <3> 代码
- 02. 划分字母区间（No. 763）
- <1> 题目
- <2> 笔记
- <3> 代码
- 03. 合并区间（No. 56）
- <1> 题目
- <2> 笔记
- <3> 代码
Day 35
01. 无重叠区间（No. 435）
题目链接
代码随想录题解
<1> 题目
给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。
示例 1:
输入: intervals = [[1,2],[2,3],[3,4],[1,3]]
输出: 1
解释: 移除 [1,3] 后，剩下的区间没有重叠。
示例 2:
输入: intervals = [ [1,2], [1,2], [1,2] ]
输出: 2
解释: 你需要移除两个 [1,2] 来使剩下的区间没有重叠。
示例 3:
输入: intervals = [ [1,2], [2,3] ]
输出: 0
解释: 你不需要移除任何区间，因为它们已经是无重叠的了。
提示:
1 <= intervals.length <= 105intervals[i].length == 2-5 * 104 <= starti < endi <= 5 * 104
<2> 笔记
本题和昨天的用最少的箭引爆气球比较类似
代码随想录刷题笔记 DAY 34 | 柠檬水找零 No.860 | 根据身高重建队伍 No.406 | 用最少的箭引爆气球 No.452
首先，如果要找到删除哪些段能够使得这个数组没有重叠的部分，首先需要 想办法将最有可能重叠的段聚集起来，所以先按照 起点的大小 进行递增排序，这样排序过后可能重叠的段就在一起了。
现在来思考如何判断两个段是否重合呢？
答案是当发现上一段的 right 是大于下一段的 left 的时候说明两端是重合的，因为经过排序以后上一段的 起点一定小于等于下一段的起点。
这时候为了使得没有重叠是 一定要删除其中的一段的，那删除那一段好呢？
答案是删除 right 最大的段，因为这种段的 覆盖面积 最大；所以可以得到这样的策略：遍历数组时当发现有重叠后就删除两段之中 right 最大的段。
所以在上一张图中，删除的就是第二个段，找不出反例，试试贪心。
首先对数组进行排序
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
然后去循环遍历整个数组，当遇到重叠的部分就删除 最大 的那个
int maxRight = intervals[0][1];
int res = 0;
for (int i = 0; i < intervals.length; i++) {
// 说明这两个节点是重叠的
if (intervals[i][0] < maxRight) {
res++;
maxRight = Math.min(intervals[i][1], maxRight); // 删除掉最宽的哪一个
} else {
// 此时不是重叠的，切换 right
maxRight = intervals[i][1];
}
}
但是此时的数组是从 0 开始遍历的，所以在第一次遍历的时候会多加上一个 1，返回结果的时候应该返回 res - 1。
<3> 代码
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
return Integer.compare(o1[0], o2[0]);
}
});
int maxRight = intervals[0][1];
int res = 0;
for (int i = 0; i < intervals.length; i++) {
// 说明这两个节点是重叠的
if (intervals[i][0] < maxRight) {
res++;
maxRight = Math.min(intervals[i][1], maxRight); // 删除掉最宽的哪一个
} else {
maxRight = intervals[i][1];
}
}
return res - 1;
}
}
02. 划分字母区间（No. 763）
题目链接
代码随想录题解
<1> 题目
给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。
注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s 。
返回一个表示每个字符串片段的长度的列表。
示例 1：
输入：s =
输出：[9,7,8]
解释：
划分结果为 “ababcbaca”、“defegde”、“hijhklij” 。
每个字母最多出现在一个片段中。
像 “ababcbacadefegde”, “hijhklij” 这样的划分是错误的，因为划分的片段数较少。
示例 2：
输入：s = “eccbbbbdec”
输出：[10]
提示：
1 <= s.length <= 500s仅由小写英文字母组成
<2> 笔记
要保证每一段中都包括一个字母的所有出现的位置，那么 划分出来这一段的终点必须要在这个字母最后出现位置或者右边；比如题目中的字符串
如果要包含所有的 a，这一段终点大于等于 a 最后出现的位置。
所以在划分的时候，一旦发现包含某个字母，那它的终点就必须在最后出现的位置的右边。
来举个例子，为了简化讲解这里举一个简单的例子
蓝色表示每个字母最后出现的位置。
当遍历到第一个字母 a 的时候 就决定了终点大于等于 a 最后出现的位置，题目中的下标为 8
遍历到第二个字母 b 终点要大于等于 6
继续遍历到 c 终点要大于等于 7
直到遍历到下标为 8 的 a 的时候可以切割了，因为此时满足上面的所有条件；总结一下切割的位置，也就是此时终点的 maxRight 要等于此时节点的下标；那么对于后面的 d e f 其都符合上述条件，所以这个例子可以分为四段。
所以要通过一次遍历将所有节点的 最终位置 找出，然后逐渐遍历并且更新 maxRight 直到 maxRight == i 的时候进行切割，这就是本题的贪心策略。
<3> 代码
class Solution {
List<Integer> res = new ArrayList<>();
public List<Integer> partitionLabels(String s) {
int[] hash = new int[26]; // 统计每个字符最后出现的位置
for (int i = 0; i < s.length(); i++) {
hash[s.charAt(i) - 97] = i;
}
int left = 0;
int right = 0;
for (int i = 0; i < s.length(); i++) {
right = Math.max(right, hash[s.charAt(i) - 97]);
if (i == right) {
res.add(right - left + 1);
left = i+1;
}
}
return res;
}
}
03. 合并区间（No. 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] 可被视为重叠区间。
提示：
1 <= intervals.length <= 104intervals[i].length == 20 <= starti <= endi <= 104
<2> 笔记
又是一个关于区间的题目，本题和前面的思路非常类似，既然要合并所有的区间那就需要将所有可能重叠的区间聚集在一起，所以和前面相同用到排列，这里用 lambda 表达式来书写
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
比如说这个案例，第一段和第二段还有第三段都是重叠的，但是发现第三段到第四段没有重叠，此时就需要将前三段合并。
但与前面不同的是，此时是合并所有的重叠情况，比如说 1 与 2 和 3 都重叠，但是 2 与 3 不重叠，最终也是将这三段合并，这也就导致了，取得 right 是 极大值。
if (intervals[i][0] > rightmostRightBound) {
//加入区间 并且更新start
res.add(new int[]{start, rightmostRightBound});
start = intervals[i][0];
rightmostRightBound = intervals[i][1];
} else {
//更新最大右边界
rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
}
<3> 代码
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new LinkedList<>();
//按照左边界排序
Arrays.sort(intervals, (x, y) -> Integer.compare(x[0], y[0]));
//initial start 是最小左边界
int start = intervals[0][0];
int rightmostRightBound = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
//如果左边界大于最大右边界
if (intervals[i][0] > rightmostRightBound) {
//加入区间 并且更新start
res.add(new int[]{start, rightmostRightBound});
start = intervals[i][0];
rightmostRightBound = intervals[i][1];
} else {
//更新最大右边界
rightmostRightBound = Math.max(rightmostRightBound, intervals[i][1]);
}
}
res.add(new int[]{start, rightmostRightBound});
return res.toArray(new int[res.size()][]);
}
}
