PositionsOfLargeGroups [source code]

public class PositionsOfLargeGroups {
static
/****************************************************************************/
class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> lss = new ArrayList<> ();
        Character anchor = S.charAt (0);
        int anchor_idx = 0;
        for (int i = 0; i < S.length (); i++) {
            if (S.charAt (i) != anchor) {
                int len = i - anchor_idx;
                if (len >= 3) {
                    List<Integer> ls = new ArrayList<> ();
                    ls.add (anchor_idx);
                    ls.add (i - 1);
                    lss.add (ls);
                }
                anchor = S.charAt (i);
                anchor_idx = i;
            }
        }
        if (S.length () - anchor_idx >= 3) {
            List<Integer> ls = new ArrayList<> ();
            ls.add (anchor_idx); ls.add (S.length () - 1);
            lss.add (ls);
        }
        return lss;
    }
}
/****************************************************************************/

    public static void main(String[] args) {
        PositionsOfLargeGroups.Solution tester = new PositionsOfLargeGroups.Solution();
        String[] inputs = {
            "abbxxxxzzy",
            "abc",
            "abcdddeeeeaabbbcd",
            "aaa",
        };
        String[] answers = {
            "[[3,6]]",
            "[]",
            "[[3,5],[6,9],[12,14]]",
            "[[0,2]]",
        };
        for (int i = 0; i < inputs.length; i++) {
            System.out.println (Printer.separator ());
            String S = inputs[i];
            List<List<Integer>> output = tester.largeGroupPositions (S);
            String output_str = output.toString ().replaceAll ("\\s+", ""), ans_str = answers[i];
            System.out.printf ("%s\n%s\n%s\n", 
                S, Printer.wrap (output_str, output_str.equals (ans_str) ? 92 : 91), ans_str
            );
        }
    }
}

简单的分段算法;

java> Integer i = 1  
java.lang.Integer i = 1  
java> i == null  
java.lang.Boolean res1 = false  
java> null == i  
java.lang.Boolean res2 = false

null可以作为比较的右值和左值;

java> String s = "abc"  
java.lang.String s = "abc"  
java> Character c = null  
java.lang.Character c = null  
java> s.charAt (0) == c  
java.lang.NullPointerException

但是这个又不行了; 太乱了, 还是defensive一点算了;

注意循环中间len >= 3这一段, 不要把anchor的更新也包进去了; 粗心的错误;

速度是17(NA).

算法本身写的时候, 因为是用anchor写法, 所以初始化稍微注意一点;anchor写法, 一个比较好的初始化思路就是直接初始化到[0]. 后面的主循环从0开始还是1开始都无所谓, 因为这里是一个判断下降沿的做法;

UNFINISHED

editorial

Approach #1: Two Pointer [Accepted]

Intuition

We scan through the string to identify the start and end of each group. If the size of the group is at least 3, we add it to the answer.

Algorithm

Maintain pointers i, j with i <= j. The i pointer will represent the start of the current group, and we will increment j forward until it reaches the end of the group.

换了一个叫法, 他以前就管这个i叫做anchor的;

We know that we have reached the end of the group when j is at the end of the string, or S[j] != S[j+1]. At this point, we have some group [i, j]; and after, we will update i = j+1, the start of the next group.

class Solution {  
    public List<List<Integer>> largeGroupPositions(String S) {  
        List<List<Integer>> ans = new ArrayList();  
        int i = 0, N = S.length(); // i is the start of each group  
        for (int j = 0; j < N; ++j) {  
            if (j == N-1 || S.charAt(j) != S.charAt(j+1)) {  
                // Here, [i, j] represents a group.  
                if (j-i+1 >= 3)  
                    ans.add(Arrays.asList(new Integer[]{i, j}));  
                i = j + 1;  
            }  
        }  

        return ans;  
    }  
}

j == N-1 || S.charAt(j) != S.charAt(j+1) 这个也是awice标志性的写法, 他也喜欢用下降沿来写分段算法, 不过他不喜欢explicit的收尾, 而是把收尾or在主循环里面一起解决;
这个是有优势的: 你看这题, 最后的收尾是要判断长度至少是3才进行的, 所以实际上最后有很多重复代码; 合在一起是有利的;

另外他这里的j实际上是一个当前run的end, 而不是next run's start, 我自己的写法用的是后者, 这个感觉差别应该不大;

另外这里确实只要维护一个anchor index就行了; 我用的是当前char不等于anchor的值来进行一个下降沿判断; 而他的方法更直接, 用当前char不等于下一个char的值, 这不就是变化了吗; 所以他只维护一个index就行了;

基本没有啥幺蛾子了;

uwi: 2min:

class Solution {  
    public List<List<Integer>> largeGroupPositions(String S) {  
        List<List<Integer>> ret = new ArrayList<>();  
        for(int i = 0;i < S.length();){  
            int j = i;  
            while(j < S.length() && S.charAt(i) == S.charAt(j))j++;  

            if(j-i >= 3){  
                List<Integer> item = new ArrayList<>();  
                item.add(i);  
                item.add(j-1);  
                ret.add(item);  
            }  

            i = j;  
        }  
        return ret;  
    }  
}

eager 循环写法, 看里面的while;

这个也可以说是分段的一种写法吧; 毕竟这里的分段找的就是一个等值, 等值搜索的小循环你应该很熟悉了; eager内循环 + 跳步, 是一个很好的代码pattern; 事实上, 这种看起来多一层循环的eager写法, 往往写出来的代码最后更加简单;

Problem 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]]

Note: 1 <= S.length <= 1000

Difficulty:Easy
Total Accepted:1.6K
Total Submissions:3.1K
Contributor:awice

Companies
google
Related Topics
array