算法练习——较大分组位置

2021年1月5日的LeetCode每日一题为较大分组位置,这一题的难度为简单,确实也是如此,从题目上我们就能知道,这一题只需要扫描一次这个字符串即可,运用双指针来完成整个字符串的扫描,从题目中也知道了只有在左指针和右指针之间的间隔大于等于3的时候才满足题设要求,因此就得到了两条信息,一个是满足答案的条件,一个是每一轮结束的条件。但是还不够,想想当右指针到达边界时,刚好满足答案条件,我们也应该将这个答案加入组中。

综上所述,当右指针到达结尾的时候,需要判断与左指针的距离是否满足答案条件,或者当每一轮结束的时候判断两个指针之间的距离是否满足答案条件即可。代码如下所示:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public List<List<Integer>> largeGroupPositions(String s) {
List<List<Integer>> ret = new ArrayList<List<Integer>>();
char[] chars = s.toCharArray();
for (int i = 0, j = 0; j <= chars.length; j++) {
if (j == chars.length || chars[j] != chars[i]) {
if (j - i >= 3) {
ret.add(Arrays.asList(i, j - 1));
}
i = j;
}
}
return ret;
}
}

今天的练习是比较简单的,只要搞清楚这几个条件,题目自然就解决了。做算法题训练思维,目的就在于解题和学习思维,能解题的就是好思路,学习各种各样的解题思路来磨练自己的算法思维。