830. Positions of Large Groups
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]]
public List<List<Integer>> largeGroupPositions(String S) {
List<List<Integer>> res = new ArrayList<>();
if (S == null || S.length() < 3) return res;
char[] chars = S.toCharArray();
int i = 0, j = 1 ;
while (j<=chars.length){
System.out.println(j);
if (j ==chars.length) {
if (j - i >= 3){
res.add(new ArrayList<>(Arrays.asList(i,j-1)));
}
break;
}
if (chars[j] != chars[i]){
if (j - i >= 3){
res.add(new ArrayList<>(Arrays.asList(i,j-1)));
}
i = j;
j++;
}else {
j++;
continue;
}
}
return res;
}
public List<List<Integer>> largeGroupPositions(String S) {
List<List<Integer>> res = new ArrayList<>();
int left = 0 , right = 1 , count = 1;
char[] chars = S.toCharArray();
for (int i = 0; i <chars.length ;i++ ){
left = i ;
right = left+1;
while (right<chars.length && chars[left] == chars[right]){
right++;
count++;
}
// 上面的循环结束后,right指向一个新的不重复的字符,这里right--,让right指向最后一个重复的字符
//如果上面的循环没有执行,这里right--了也不要紧,因为在下一轮的循环开始,right会被重新赋值,覆盖原来的值
right--;
if (count>=3) {
res.add(new ArrayList<>(Arrays.asList(left,right)));
i = right;
// 这里将i设为right,在下一个for循环中还有个i++;
// 让i指向下一个新的字符。这就是为什么不让i= right+1;
}
count = 1;
}
return res;
}
总结:本题属于双指针的问题,一个标记重复字符串的左,一个标记右,从字符串的头部滑动到尾部,遇到满足一部要求的解后,加入res。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系 cloudcommunity@tencent.com 删除。