1. question: 划分字母区间（中等）
字符串 S 由小写字母组成。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。返回一个表示每个字符串片段的长度的列表。
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/partition-labels
示例：
1
2
3
4
5
6
| 输入：S = "ababcbacadefegdehijhklij"
输出：[9,7,8]
解释：
划分结果为 "ababcbaca", "defegde", "hijhklij"。
每个字母最多出现在一个片段中。
像 "ababcbacadefegde", "hijhklij" 的划分是错误的，因为划分的片段数较少。
|
提示：
1
2
| S的长度在[1, 500]之间。
S只包含小写字母 'a' 到 'z' 。
|
2. answers
这道题有两个关键点：
- 划分为尽可能多的字符串
- 同一字符最多出现在一个片段中
对于第一个点，因此划分的每个字符串长度应该尽可能小，应该每遇到一个字符就判断是否满足关键点2。
对于第二点，首先需要判断后续是否还有该字符，怎么判断呢？先遍历一遍，保存每个字符的数量（因为题目中是小写字母a-z，可采取26长度的数组）。如果该字符的数量不为0（注意要减去当前字符1），那么就说明后续还有该字符。因此需要继续遍历，不能在此处分割。但是遍历的时候，就会引入其他字符，因此，遍历的时候，26数组中对应的个数应该也要减去遇到的字符。
同时也要注意，后续判断的时候，应该判断后续是否还有当前字符子串中的任意字符。因此，在遍历的时候，应该保存子串中的字符种类list，用于后续判断。
只有当list中的对应字符在26数组中都为0时，才满足要求，即划分子串。
代码如下所示：
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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| public class Solution_0106 {
public List<Integer> partitionLabels(String s) {
List<Integer> result = new ArrayList<>();
char[] chars = s.toCharArray();
HashMap<Character, Integer> hashMap = new HashMap<>();
for (char aChar : chars) {
Integer orDefault = hashMap.getOrDefault(aChar, 0);
hashMap.put(aChar, orDefault + 1);
}
int start = 0;
for (int i = 0; i < chars.length; i++) {
List<Character> list = new ArrayList<>();
for (int j = start; j < chars.length; j++) {
if(!list.contains(chars[j])) list.add(chars[j]);
int remain = hashMap.get(chars[j]) - 1;
hashMap.put(chars[j], remain);
if(remain != 0) continue;
boolean tag = true;
for (Character c: list) {
if(hashMap.get(c) != 0) {
tag = false;
break;
}
}
if(tag) {
result.add(j - start + 1);
start = j + 1;
break;
}
}
}
return result;
}
public static void main(String[] args) {
System.out.println();
Solution_0106 s = new Solution_0106();
String S = "ababcbacadefegdehijhklij";
List<Integer> list = s.partitionLabels(S);
for(Integer i: list)
System.out.print(i + "\t");
}
}
|
参考题解，其实没必要保存字符的数量。还是两个关键点：
- 划分为尽可能多的字符串
- 同一字符最多出现在一个片段中
第一个点，就是遇到字符之后，如果满足条件2，那么就赶紧切分。那么对于条件2，可存储字符的最远下标（保证了后面没有该字符）。只需要判断当前遍历的下标是否该字符的最远下标即可。
注意，那么如果不满足，肯定会出现子串，那么子串中的其他字符该怎么办呢？上面的判断标准可以改变一下，遍历的时候，保存子串中所有字符的最远下标，即asdf，如果f的最远下标是所有字符中最大的，那么就保存f的下标。然后判断当前下标是否是f即可。因为f满足了，而其他字符的最远下标都小于f，必定也满足了。因此，只需要判断当前下标是否是当前子串中最远的下标即可。代码如下所示：
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
| public List<Integer> partitionLabels(String s) {
List<Integer> result = new ArrayList<>();
int[] hash = new int[26];
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
hash[chars[i] - 'a'] = i;
}
int maxIndex = Integer.MIN_VALUE;
int start = 0;
for (int i = 0; i < chars.length; i++) {
maxIndex = Math.max(maxIndex, hash[chars[i] - 'a']);
if(i == maxIndex) {
result.add(i - start + 1);
start = i + 1;
maxIndex = Integer.MIN_VALUE;
}
}
return result;
}
|
3. 备注
参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。
