830. Positions of Large Groups@python

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:

Input: "abcdddeeeeaabbbcd"

Output: [[3,5],[6,9],[12,14]]

原题地址: Positions of Large Groups

题意: 将数组分组,标记每一组的首尾索引值,返回分组长度等于3的索引值

难度: Easy

思路:

(1)遍历数组并用count数组标记,注意首尾边界

(2)遍历count,找出长度大于等于3的分组

代码:

class Solution(object):

    def largeGroupPositions(self, S):

        """

        :type S: str

        :rtype: List[List[int]]

        """

        count = []

        i = 0

        j = 1

        while j <= len(S):

            if j == len(S):

                count.append([i, j-1])

                break

            if S[i] == S[j]:

                j += 1

            else:

                count.append([i, j-1])

                i = j

        res = []

        for c in count:

            if c[1] - c[0] + 1 >= 3:

                res.append(c)

        return res

时间复杂度: O(n)

空间复杂度: O(n)

在上面的基础上优化一下,一次变量即可

代码:

class Solution(object):

    def largeGroupPositions(self, S):

        """

        :type S: str

        :rtype: List[List[int]]

        """

        res = []

        i, j = 0, 1

        n = len(S)

        while j < n:

            if S[j] != S[j-1]:   # 找到不相等的值

                count = j - i

                if count >= 3:

                    res.append([i, j-1])

                i = j

            j += 1

        if j - i >= 3:         # 处理边界问题

            res.append([i, j-1])

        return res

巴特西

830. Positions of Large Groups@python

最新文章

热门文章