使用双指针方法背后的直觉
我在LeetCode.com上解决一个问题
给出了一个小写英文字母的字符串S。我们希望将该字符串划分为尽可能多的部分，以便每个字母最多出现在一个部分中，并返回表示这些部分大小的整数列表。 输入："ababcbacadefegdehijhklij“输出为: 9,7,8
高升压溶液如下所示：
public List<Integer> partitionLabels(String S) {
if(S == null || S.length() == 0){
return null;
}
List<Integer> list = new ArrayList<>();
int[] map = new int[26]; // record the last index of the each char
for(int i = 0; i < S.length(); i++){
map[S.charAt(i)-'a'] = i;
}
// record the end index of the current sub string
int last = 0;
int start = 0;
for(int i = 0; i < S.length(); i++){
last = Math.max(last, map[S.charAt(i)-'a']);
if(last == i){
list.add(last - start + 1);
start = last + 1;
}
}
return list;
}我理解我们在第一个for循环中所做的事情(我们只是存储一个字符最后一次出现的索引)，但是对于第二个循环，我不太确定：
为什么我们要计算max()并比较last==i
它如何帮助我们实现我们所寻求的--在上面的例子中，当我们在8位置(0索引)遇到8时，我们不会遇到什么保证，比如b，在一个比8更大的位置？因为，如果我们这样做，那么考虑8作为我们的子字符串的结束位置是不正确的。
谢谢!
回答 2
Stack Overflow用户
发布于 2020-07-23 05:22:29
如果我们遇到一个字符S[i]，我们只能在字符串最后出现之后才剪断它，因此是map[S.charAt(i)-'a']。我们最大化了last中的值，因为我们需要确保所有处理过的字符在前缀中都有它们的最后出现，所以我们查看了这些索引的最右边，因此是max。如果遇到一个字符S[i]，使得i是最后一次出现，而所有字符在i之前都有最后出现，那么我们可以将子字符串start..i添加到结果中，并为下一个子字符串设置start = i + 1。
Stack Overflow用户
发布于 2020-07-23 05:22:40
想法是这样的。每当最后一次出现特定字符与当前索引匹配时，这意味着此特定字符仅出现在此部分中。
要更好地理解这件事，就这么做吧。
int last = 0;
int start = 0;
for(int i = 0; i < S.length(); i++){
last = Math.max(last, map[S.charAt(i)-'a']);
System.out.println(last+" "+i);
if(last == i){
list.add(last - start + 1);
start = last + 1;
}
}以字符串"ababcbacadefegdehijhklij"为例。
现在，输出将是
8 0
8 1
8 2
8 3
8 4
8 5
8 6
8 7
8 8
14 9
15 10
15 11
15 12
15 13
15 14
15 15
19 16
22 17
23 18
23 19
23 20
23 21
23 22
23 23a的最后一次出现在第8位。现在我们在第0位。所以，直到我们到达第八位，我们不能确定每个部分最多包含一个字符。假设下一个字符是b，它最终出现在第10位，那么我们需要确认到第10位。
if(last == i){
}上面的if只是确认这个部分已经结束，我们可以从下一个索引开始一个新的部分。在此之前，我们要将当前部件的长度添加到输出中。
https://stackoverflow.com/questions/63047202
复制相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号