较大分组位置
较大分组位置
830. 较大分组的位置,这是一道简单题,题目如下:
1 |
|
分析题目可以得出以下几点:
- 连续相同字符串为一组
- 答案记录每一组的起点和终点,即
[start, end]
- 较大分组条件为分组的长度大于等于3,即
end - start >= 3
- 答案结果以其实下标递增顺序排序,即start小的在前,例:
[[3,5],[6,9],[12,14]]
从上面几点可以看出我们需要遍历字符串,并找出“较大分组”的起点和终点,那么我们需要一个变量来记录分组起点,一个列表记录答案。
接着从条件上看,我们使用一个移动指针来表示现在扫描的位置,与起点的字符相等,则说明该分组还没结束。如果不相等,则说明前一个位置是分组的结束位置,检查长度是否满足end - start >= 3
的要求,满足要求记录下这个分组的位置,并将起始点移动到当前位置,进行下一轮的扫描。由于起始点是从0开始的,因此很自然地满足了第4点要求。实现代码如下:
1 |
|
较大分组位置
http://codebro.cn/posts/journey/algorithm/Bigger_Group.html