0%

题目描述

题目链接

思路

显然,如果整个字符串无重复值,那么字符串的字符个数就是最多划分的区间个数。

如果有重复值,假设a字符有重复,那么所有的a必须划分到同一个区间内,否则a分布不同区间的话,就不满足题目要求了。

同理,其他字符也是类似的逻辑。

我们的整体流程是从左往右遍历字符,当遍历到一个字符的时候,我们需要快速知道这个字符在字符串后续位置是哪里,这样至少知道这个字符串至少应该从哪里开始切。

例如:abdtydfsdfdasbsssrr这个字符串,当遍历到第一个a时候,我们需要马上知道整个字符串后续是否还有a这个字符,此例子中,在字符串的11位置确实还有一个字符a

我们设置一个right变量,用于记录当前刀最少要切到的位置,

当遍历到第一个a字符以后,可以判断第一刀至少要切到11位置,right记录为11,

至于后续是否还需要继续扩散,要继续遍历下一个字符b,如果整个字符串中最右边的b字符没有超过11位置,则第一到继续可以保持到11位置来切,

如果整个字符串中的b的最右位置超过了11,如此例,最右边的b出现在13位置,那么第一刀位置就要从11扩散到13位置,right记录为13

如果遍历到某个字符串的最右边位置正好是right,则可以从这个位置切一刀。

以此类推,直到遍历完整个字符串。

根据以上流程,我们需要对数组进行一次预处理,即,记录每个字符串出现的最右位置,由于题目限定是小写字母,所以可以通过如下方式来保存每个字符的最右位置

1
2
3
4
int[] help = new int[26];
for (int i = 0; i < str.length; i++) {
help[str[i] - 'a'] = i;
}

主流程代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int right = 0;
int pre = right;
List<Integer> ans = new ArrayList<>();
for (int i = 0; i < str.length; i++) {
// 是否可以将right位置扩散
right = Math.max(right, help[str[i] - 'a']);
if(i == right) {
// 当前位置已经是能扩散的最右位置了
// 收集答案
ans.add(right - pre + 1);
pre = right + 1;
}
}
return ans;

pre记录上一刀的位置,便于求每个区间的长度(题目要求), 当前遍历到的位置i如果正好是目前区间能扩散的最右位置right,则结算。

更多

算法和数据结构笔记

参考资料

题目描述

题目链接

思路

题目要求至少移除多少个线段可以保证线段不出现重叠区域,比如以下情况:

image

我们至少需要移走四条线段才能让剩余线段不重叠。移动后的线段如下图

image

我们可以反过来考虑,即求所有非重叠区域的个数,假设是M,线段数量假设是N,那么N-M即为需要移除的线段数量。

主要流程如下,先把所有线段按结尾位置排序,结尾小的排前面,结尾大的排后面。

然后遍历每个线段,如果线段的开始位置超过了前一个线段的结尾位置,说明这两个线段是非重叠的,非重叠个数加1,遍历完毕,用所有线段个数减去非重叠个数,即为需要移除的线段个数。

完整代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
import java.util.Arrays;
import java.util.Comparator;

// 至少移除多少个区间后可以保证线段不重合
// 转换成非重叠区域的个数
public class LeetCode_0435_NonOverlappingIntervals {
public static int eraseOverlapIntervals(int[][] intervals) {
if (null == intervals || intervals.length <= 1) {
return 0;
}
Interval[] arr = new Interval[intervals.length];
int i = 0;
for (int[] interval : intervals) {
arr[i++] = new Interval(interval[0], interval[1]);
}
Arrays.sort(arr, new MyComparator());
// 非重叠区域个数
int notOverlap = 1;
int b = arr[0].end;
for (i = 1; i < arr.length; i++) {
if (arr[i].start >= b) {
notOverlap++;
b = arr[i].end;
}
}
return arr.length - notOverlap;
}

public static class MyComparator implements Comparator<Interval> {

@Override
public int compare(Interval o1, Interval o2) {
return o1.end - o2.end;
}
}

public static class Interval {
public int start;
public int end;

public Interval(int start, int end) {
this.start = start;
this.end = end;
}
}
}

更多

算法和数据结构笔记

参考资料