代码随想录算法训练营第二十九天 | leetcode：无重叠区间,划分字母区间,合并区间
0 / 0 / 创建于 11个月前 /
_zzh 的个人博客
435. 无重叠区间
Tips
写这题的时候看了下别人的解法，发现多维数组排序，使用array_multisort(array_column($intervals, “0”), $intervals);
会比昨天引爆气球题目使用的usort($intervals,”compare”)的方式要快很多，具体原理还没明白，先标记下。
解题方法
与昨天引爆气球题目同类型的题目，重点还是在处理重叠区间上面。但是也不要被移除字样给误导了。同样的判断区间重叠只需要做标记++即可。重点不同是在与引爆气球题目是不重叠需要标记++，而这题则是判断重叠时候标记++，因为重叠需要移除。
复杂度
时间复杂度
O(n)
空间复杂度
O(1)
code
class Solution {
/**
* @param Integer[][] $intervals
* @return Integer
*/
function eraseOverlapIntervals($intervals) {
//按区间左边界更新（实验了一下左右都可以，甚至右边界还更快）
array_multisort(array_column($intervals, "0"), $intervals);
$result = 0;
for($i = 1; $i < count($intervals); $i++){
//如果存在区间重叠则移除数量++，更新当前区间的右边界
if($intervals[$i][0] < $intervals[$i-1][1]){
$result++;
//重叠则更新最小右边界，判断下一个区间是否重叠
$intervals[$i][1] = min($intervals[$i][1], $intervals[$i-1][1]);
}
}
return $result;
}
}763. 划分字母区间
解题方法
- 使用数组构建每个出现字母的最远距离hash参照。
- 遍历数组，不断更新遇到字母的最大距离，直到i==最大距离，表示当前区间是包括了前面出现过的字母了。
复杂度
时间复杂度
O(n)
空间复杂度
O(1)，使用的hash数组是固定大小最多26个。
code
class Solution {
/**
* @param String $s
* @return Integer[]
*/
function partitionLabels($s) {
if(strlen($s) == 1) return 1;
$maxPos = [];//获取每个元素最远出现位置
for($i = 0; $i < strlen($s); $i++){
$maxPos[$s[$i]] = $i;
}
$result = [];
$left = $right = 0;//区间左右边界
for($i = 0; $i < strlen($s); $i++){
//更新最大右边界
$right = max($right, $maxPos[$s[$i]]);
if($i == $right){
//当i走到最大右边界时收集结果
$result[] = $right - $left + 1;
//更新左边界
$left = $i + 1;
}
}
return $result;
}
}56. 合并区间
注意的地方
本题相邻区间也算重叠，例如[1, 3] [3, 5]也是重叠区间，需要更新为[1, 5]。
解题方法
- 重叠区间标准操作，先使用array_multisort按左边界排序。
- 判断存在重叠则更新右边界为最大右边界（因为要合并，这里不取最小）。这里可以自定义左右边界各自处理，只不过会稍微麻烦一点。这里使用新数组newArr，初始化插入intervals[0]，这样就初始化了左右边界了，判断的时候，就用新数组的最后区间右边界与intervals[i]的左边界判断是否重叠，重叠的话更新新数组右边界为 新数组右边界与intervals[i]右边界的最大值。如果不存在重叠则把intervals[i]插入新数组。相当于本来应该与intervals[i-1]作比较的，但是变成了与newArr最后元素的右边界作比较。
复杂度
时间复杂度
O(nlogn)
空间复杂度
O(logn)，排序需要的空间开销
code
class Solution {
/**
* @param Integer[][] $intervals
* @return Integer[][]
*/
function merge($intervals) {
if(count($intervals) == 1) return $intervals;
$newArr = [];
//按左边界排序
array_multisort(array_column($intervals, "0"), $intervals);
//初始化
$newArr[] = $intervals[0];
for($i = 1; $i < count($intervals); $i++){
//取新区间的最后下标
$len = count($newArr) - 1;
//当前遍历区间的左边界与新数组最后区间的右边界作比较
if($newArr[$len][1] >= $intervals[$i][0]){
//有重叠则更新新数组最后区间的右边界
$newArr[$len][1] = max($newArr[$len][1], $intervals[$i][1]);
}else{
//与新数组最后区间无重叠则插入新数组
$newArr[] = $intervals[$i];
}
}
return $newArr;
}
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号