Leetcode 435.无重叠区间

题目：435.无重叠区间

初始思路

没思路

代码

  1. var eraseOverlapIntervals = function (intervals) {
  2.     // 按照右边界从小到大排序
  3.     intervals.sort((a, b) => {
  4.         return a[1] - b[1]
  5.     })
  6.     // 记录非交叉区间的个数
  7.     let count = 1
  8.     // 记录区间分割点
  9.     let end = intervals[0][1]
  10.     for (let i = 1; i < intervals.length; i++){
  11.         let temp = intervals[i]
  12.         if (temp[0] >= end) {
  13.             // 如果区间不交叉更新分割点
  14.             end = temp[1]
  15.             count++
  16.         }
  17.     }
  18.     // 区间总数减去非交叉区间就是需要移除的区间个数
  19.     return intervals.length - count
  20. };

感想

  1. 按照右边界排序，就要从左向右遍历，因为右边界越小越好，只要右边界越小，留给下一个区间的空间就越大，所以从左向右遍历，优先选右边界小的。
  2. 按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。
  3. image.png

Leetcode 763.划分字母区间

题目：763.划分字母区间

初始思路

找最远下标可以用lastIndexOf，不停遍历更新也可以。

代码

  1. var partitionLabels = function (s) {
  2.     let hash = {}
  3.     for (let i = 0; i < s.length; i++){
  4.         // 获得最远下标
  5.         hash[s[i]] = i
  6.     }
  7.     let res = []
  8.     let left = 0
  9.     let right = 0
  10.     for (let i = 0; i < s.length; i++){
  11.         // 当前右区间和最远下标作比较
  12.         right = Math.max(right, hash[s[i]])
  13.         // 如果右区间到了最远坐标就可以分割了
  14.         if (right === i) {
  15.             // 加入这段区间的长度
  16.             res.push(right - left + 1)
  17.             // 开始下一段区间的寻找
  18.             left = i + 1
  19.         }
  20.     }
  21.     return res
  22. };

感想

  1. 在遍历的过程中相当于是要找每一个字母的边界，如果找到之前遍历过的所有字母的最远边界，说明这个边界就是分割点了。此时前面出现过所有字母，最远也就到这个边界了。
  2. image.png

Leetcode 56.合并区间

题目：56.合并区间

初始思路

重叠区间左区间取两者最小值，右区间取两者最大值。

代码

  1. var merge = function (intervals) {
  2.     // 按照左边界从小到大排序
  3.     intervals.sort((a, b) => {
  4.         return a[0] - b[0]
  5.     })
  6.     let prev = intervals[0]
  7.     let res = []
  8.     for (let i = 0; i < intervals.length; i++){
  9.         let temp = intervals[i]
  10.         if (temp[0] > prev[1]) {
  11.             // 如果区间不重叠，直接把前一个区间加进去
  12.             res.push(prev)
  13.             // 进入下一个区间开始比较
  14.             prev = temp
  15.         } else {
  16.             // 如果重叠的话，右区间取两者最大值
  17.             prev[1] = Math.max(temp[1], prev[1])
  18.         }
  19.     }
  20.     // 加入最后一个区间
  21.     res.push(prev)
  22.     return res
  23. };

感想

  1. 按照左边界排序，排序之后局部最优：每次合并都取最大的右边界，这样就可以合并更多的区间了，整体最优：合并所有重叠的区间。
  2. 按照左边界从小到大排序之后，如果 intervals[i][0] < intervals[i - 1][1] 即intervals[i]左边界 < intervals[i - 1]右边界，则一定有重复，因为intervals[i]的左边界一定是大于等于intervals[i - 1]的左边界。
  3. 即：intervals[i]的左边界在intervals[i - 1]左边界和右边界的范围内，那么一定有重复！
  4. image.png