较大分组的位置
难度:
标签:
题目描述
代码结果
运行时间: 22 ms, 内存: 16.0 MB
// 思路:
// 使用Stream API处理字符串,找到所有由连续相同字符组成的分组。
// 如果分组长度大于等于3,则将其起始和终止下标添加到结果列表中。
// 返回结果列表。
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class Solution {
public List<List<Integer>> largeGroupPositions(String s) {
List<List<Integer>> result = new ArrayList<>();
IntStream.range(0, s.length())
.collect(ArrayList::new, (list, i) -> {
if (list.isEmpty() || s.charAt(list.get(list.size() - 1)) != s.charAt(i)) {
list.add(i);
}
}, ArrayList::addAll)
.stream()
.collect(Collectors.toList())
.stream()
.map(start -> {
int end = start;
while (end < s.length() && s.charAt(end) == s.charAt(start)) {
end++;
}
return new int[]{start, end - 1};
})
.filter(pair -> pair[1] - pair[0] >= 2)
.forEach(pair -> result.add(List.of(pair[0], pair[1])));
return result;
}
}
解释
方法:
这个题解采用了双指针的思路。使用 left 和 right 两个指针分别表示当前分组的起始和结束位置。遍历字符串,如果当前字符与前一个字符相同,则 right 指针向右移动;否则,判断 left 和 right 之间的长度是否大于等于3,如果是则将 [left, right] 加入结果,并将 left 和 right 都置为当前位置 i,表示开始一个新的分组。最后再判断最后一个分组是否满足条件。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在代码实现中,如何确保在字符串最后一个字符后正确处理边界情况,尤其是当最后一个分组是较大分组时?
▷🦆
代码中使用了`now_char = s[i]`来更新当前字符,这种更新是否有可能导致某些情况下分组不准确,比如连续字符在更新点断开?
▷🦆
在判断`if right - left + 1 >= 3`时,为什么选择这个条件来确定是否是较大分组,这里的'1'是如何计算的?
▷🦆
示例输出显示边界闭合的区间[3,6],但在代码中`right`指针是如何处理以确保正确表示分组的结束位置?
▷