Description:
In a string S
of lowercase letters, these letters form consecutive groups of the same character.
For example, a string like S = "abbxxxxzyy"
has the groups "a"
, "bb"
, "xxxx"
, "z"
and "yy"
.
Call a group large if it has 3 or more characters. We would like the starting and ending positions of every large group.
The final answer should be in lexicographic order.
Example 1:
Input: "abbxxxxzzy"
Output: [[3,6]]
Explanation: "xxxx" is the single large group with starting 3 and ending positions 6.
Example 2:
Input: "abc"
Output: []
Explanation: We have "a","b" and "c" but no large group.
Example 3:
Input: "abcdddeeeeaabbbcd"
Output: [[3,5],[6,9],[12,14]]
思路:本题要求统计小写字母序列中连续出现大于或等于三次的下标起始位置。可以考虑使用双指针,一个指针指向重复部分的开头,一个往后遍历计数,只要不相同了就停止,然后看次数是否大于等 3,是就将双指针位置存入结果 res 中,并更新指针。
C++ 代码
class Solution {
public:
vector<vector<int>> largeGroupPositions(string S) {
vector<vector<int>> res;
int n = S.size(), start = 0;
for (int i = 1; i <= n; ++i) {
if (i < n && S[i] == S[start])
continue;
if (i - start >= 3)
res.push_back({start, i - 1});
start = i;
}
return res;
}
};
运行时间:8ms
运行内存:9.2M
欢迎来到这里!
我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。
注册 关于