代码随想录第31天 | 435. 无重叠区间 ● 763.划分字母区间 ● 56. 合并区间

435. 无重叠区间

/**
 * @param {number[][]} intervals
 * @return {number}
 */
var eraseOverlapIntervals = function(intervals) {
    intervals.sort((x,y)=>
        (x[1]-y[1])
    )
    let r=1
    for(let i=0;i<intervals.length-1;i++){
       //重叠
      if(intervals[i][1]>intervals[i+1][0]){
          intervals[i+1][1]=intervals[i][1]<intervals[i+1][1]?intervals[i][1]:intervals[i+1][1];
      }
       //不重叠 
       else{
           r++
       }   
    }
    return intervals.length-r
    };


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

想法

按照右边界排序，从左向右记录非交叉区间的个数。最后用区间总数减去非交叉区间的个数就是需要移除的区间个数了。

763.划分字母区间

/**
 * @param {string} s
 * @return {number[]}
 */
var partitionLabels = function(s) {
     let ok=new Array(26)
     //哈希，写出每一个字母对应的节点
     for(let i=0;i<s.length;i++){
         ok[s.charCodeAt(i)-97]=i
     }
     //结果
     let c=[]
     //记录当前区间最大值
     let max=-1
     for(let i=0;i<s.length;i++){
           //更新max
          if(ok[s.charCodeAt(i)-97]>max)
           max=ok[s.charCodeAt(i)-97]
         //最大值等于当前字母的值，找到一个
         if(i===max)
           //  c.push(c.length===0?max+1:max-c[c.length-1]+1)
        c.push(i+1)
     }
     if(c.length===1)
     return c
    for(let i=c.length-1;i>0;i--){
         c[i]=c[i]-c[i-1]
     }
     return c
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

想法

### 困难 * ok[s.charCodeAt(i)-97]=i >s.charCodeAt(i)是char转为

56. 合并区间

/**
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals){
  intervals.sort((x,y)=>(x[0]-y[0]))
  //按开始节点排序
  let r=0;
  let c=[];
  let les=intervals[0][0];
  let end=intervals[0][1];
  let max=intervals[0][1];
  for(let i=0;i<intervals.length-1;i++){
      //不重叠
   if(max<intervals[i+1][0]){
       c.push([les,max])
       les=intervals[i+1][0]
        max=intervals[i+1][1]
   }
  //有重叠,合并
  if(max>=intervals[i+1][0]){
      max=intervals[i+1][1]>max?intervals[i+1][1]:max}
      }
      c.push([les,max])
      return c
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26