代码随想录训练营第三十六天 | 无重叠区间&&划分字母区间&&合并区间

435.无重叠区间

文章：18. 无重叠区间

题目：435. 无重叠区间

【思路】

左边界排序：

和上一次射箭非常相似，都是先排序，然后通过比较前一个数的右边界是否大于当前数值的左边界来判断她们有没有重叠；没有重叠不做处理，重叠的话就count++、并且更新最右边界（前一数的右边界和当前值的右边界比较）。

相当于删除了重叠靠右的区间。

  • Java实现

sort函数默认是升序排序，使用lamda表达式是使用了比较器Integer.compare(a[0],b[0])来指定了是使用intervals[0]的值来比较排列

1
2
3
Arrays.sort(intervals,(a,b)->{
            return Integer.compare(a[0],b[0]);
        });
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals,(a,b)->{
            return Integer.compare(a[0],b[0]);
        });
        int count =0;
        for(int i = 1;i<intervals.length;i++){
            if(intervals[i][0] < intervals[i-1][1]){
                intervals[i][1] = Math.min(intervals[i-1][1],intervals[i][1]);
                count++;
            }
        }
        return count;
    }
}
  • Go实现

这里同样使用了排序，使用了sort.Slice函数来对数组进行排序。

less函数允许对切片进行排序。其中slice 是待排序切片，less是用于比较两个元素大小的自定义函数。less函数接收两个参数i和j，表示切片中的索引位置，根据返回值决定i是否应该排在j前面。**less 函数会返回一个布尔值，当返回值为 true 时，表示元素 i 应该排在元素 j 之前，即 nums[i] 小于 nums[j]。当返回值为 false 时，表示元素 i 不应该排在元素 j 之前，即 nums[i] 大于等于 nums[j]。**<是升序，>是降序。

1
func Slice(slice interface{}, less func(i, j int) bool)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func eraseOverlapIntervals(intervals [][]int) int {
    sort.Slice(intervals,func(a,b int)bool{
        return intervals[a][1] < intervals[b][1]
    })
    res :=0
    for i:=1;i < len(intervals);i++{
        if intervals[i][0] < intervals[i-1][1]{
            intervals[i][1] = min(intervals[i][1],intervals[i-1][1])
            res++
        }
    }
    return res 
}
func min(a,b int)int{
    if a < b{
        return a
    }
    return b
}

763.划分字母区间

文章：19. 划分字母区间

题目：763. 划分字母区间

【思路】

用最远出现举例模拟了圈字符的行为。

1.使用一个数组来存储字符串每个字符最后出现的位置下标。

2.根据最远出现位置来决定区间划线在哪里。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<Integer> partitionLabels(String s) {
        if(s.length() == 0)return new ArrayList<Integer>();
        int[]index = new int[26];
        for(int i = 0 ; i < s.length();i++){
            index[s.charAt(i) - 'a'] = i;
        }
        int left = 0;
        int right = 0;
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = 0;i < s.length();i++){
            right = Math.max(right,index[s.charAt(i) - 'a']);
            if(right == i){
                list.add(right-left+1);
                left = i+1;
            }
        }
        return list;
    }
}
  • Go实现
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
func partitionLabels(s string) []int {
    if len(s) == 0{
        return []int{}
    }
    var indexs [26]int
    for i :=0 ; i < len(s);i++{
        indexs[s[i]-'a']= i
    }
    res := make([]int,0)
    right := 0
    left :=0 
    for i :=0 ; i < len(s);i++{
        right = maxFunc(indexs[s[i]-'a'],right)
        if right == i{
            res = append(res,right-left+1)
            left = i+1
        }
    }
    return res
}

func maxFunc(a,b int)int{
    if a>b{
        return a
    }
    return b
}

56.合并区间

文章：20. 合并区间

题目：56. 合并区间

【思路】

凡是有重叠的区间都将其进行合并。

  • Java实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[][] merge(int[][] intervals) {
        List<int[]>  res = new LinkedList<>();
        Arrays.sort(intervals,(a,b)->{
            return Integer.compare(a[0],b[0]);
        });
        int start = intervals[0][0];
        int right = intervals[0][1];
        for(int i = 1 ; i < intervals.length;i++){
            if(intervals[i][0] > right){
                res.add(new int[]{start,right});
                start = intervals[i][0];
                right = intervals[i][1];
            }else{
                right = Math.max(right,intervals[i][1]);
            }
        }
        res.add(new int[]{start,right});
        return res.toArray(new int[res.size()][]);

    }
}
  • Go实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func merge(intervals [][]int) [][]int {
    sort.Slice(intervals,func(i,j int)bool{
        return intervals[i][0] < intervals[j][0]
    })
    res := make([][]int,0,len(intervals))
    left ,right :=intervals[0][0] ,intervals[0][1]
    for i := 1;i < len(intervals);i++{
        if intervals[i][0] > right{
            res = append(res,[]int{left,right})
            left ,right = intervals[i][0],intervals[i][1]
        }else{
            right = max(intervals[i][1],right)
        }
        
    }
    res = append(res,[]int{left,right})
        return res 
}
func max(a,b int)int{
    if a > b{
        return a
    }
    return b
}

【算法总结】

  • 无重叠区间、划分字母区间、合并区间：其实三道题目都蛮像的，就是排序+具体细节处理，个人认为最重要的是如何自定义排序。

【语法总结】

  • Java实现
1
2
3
Arrays.sort(intervals,(a,b)->{
            return Integer.compare(a[0],b[0]);
        });
  • Go实现
1
2
3
sort.Slice(intervals,func(i,j int)bool{
    return intervals[i][0] < intervals[j][0]
})