LeetCode算法题-Positions of Large Groups(Java实现)

这是悦乐书的第323次更新,第346篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第193题(顺位题号是830)。在由小写字母组成的字符串S中,那些相同的连续字符会组成集合。例如,诸如S =“abbxxxxzyy”的字符串具有集合“a”,“bb”,“xxxx”,“z”和“yy”。

如果集合有3个或更多字符,称之为大集合,要求找到每个大集合的起点和终点,以数组形式返回,以从前往后顺序。例如:


输入:“abbxxxxzzy”

输出:[[3,6]]

说明:“xxxx”是具有起始位置3和结束位置6的单个大集合。


输入:“abc”

输出:[]

说明:我们有“a”,“b”和“c”,但没有大集合。


输入:“abcdddeeeeaabbbcd”

输出:[[3,5],[6,9],[12,14]]


注意:1 <= S.length <= 1000

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 解题

题目的意思很明确,要求找到字母连续出现3次及以上且字母相同的子串,取其起始索引,作为数组返回,并且只能是从前往后的顺序。在遍历字符串中的字母时,还需要记数,判断出现次数,满足条件就取开始索引、结束索引存入List中。

第一步,初始化结果数组,S的长度n。

第二步,遍历S中的字符,定义两个变量,count统计出现次数,index记录开始索引。使用一个循环,从当前位置开始往后遍历查找,遇到相同字符,count加1,直到遇上不相等的字符或者遍历完右边剩下的字符。接着判断,如果count大于等于3,说明符合题目条件,新创建一个List,将起始索引add进去,再将List添加进结果数组中去。

第三步,返回结果数组。

public List<List<Integer>> largeGroupPositions(String S) {
    List<List<Integer>> result = new ArrayList<List<Integer>>();
    int n = S.length();
    for (int i=0; i<n-1; i++) {
        int count = 1;
        int index = i;
        while (i+1 < n && S.charAt(i) == S.charAt(i+1)) {
            count++;
            i++;        
        }
        if (count >= 3) {
            List<Integer> list = new ArrayList<Integer>();
            list.add(index);
            list.add(i);
            result.add(list);
        }
    } 
    return result;
}


03 小结

算法专题目前已日更超过五个月,算法题文章193+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

上一篇:2020-5杂题选做


下一篇:POJ2126——Prime Path(BFS)