较大分组位置

较大分组位置

830. 较大分组的位置,这是一道简单题,题目如下:

1
2
3
4
5
6
7
8
9
在一个由小写字母构成的字符串 s 中,包含由一些连续的相同字符所构成的分组。

例如,在字符串 s = "abbxxxxzyy" 中,就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。

分组可以用区间 [start, end] 表示,其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间,按起始位置下标递增顺序排序后,返回结果。

分析题目可以得出以下几点:

  • 连续相同字符串为一组
  • 答案记录每一组的起点和终点,即[start, end]
  • 较大分组条件为分组的长度大于等于3,即end - start >= 3
  • 答案结果以其实下标递增顺序排序,即start小的在前,例:[[3,5],[6,9],[12,14]]

从上面几点可以看出我们需要遍历字符串,并找出“较大分组”的起点和终点,那么我们需要一个变量来记录分组起点,一个列表记录答案。

接着从条件上看,我们使用一个移动指针来表示现在扫描的位置,与起点的字符相等,则说明该分组还没结束。如果不相等,则说明前一个位置是分组的结束位置,检查长度是否满足end - start >= 3的要求,满足要求记录下这个分组的位置,并将起始点移动到当前位置,进行下一轮的扫描。由于起始点是从0开始的,因此很自然地满足了第4点要求。实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public List<List<Integer>> largeGroupPositions(String s) {
int l = 0, n = s.length();
List<List<Integer>> ans = new ArrayList<>();
for(int r = 1; r <= n; r++) {
if(r == n || s.charAt(l) != s.charAt(r)) {
if(r - l >= 3) {
ans.add(Arrays.asList(l, r - 1));
}
l = r;
}
}
return ans;
}
}

较大分组位置
http://codebro.cn/posts/journey/algorithm/Bigger_Group.html
作者
Vector
发布于
2021年1月5日
许可协议