手记

leetcode每日一题:830. 较大分组的位置

一起刷题吧

一、题意分析

输入:字符串
输出:相同且连续的字符数量超过 3 的所有串的起始位置组成的列表
难度:简单

示例一
输入:s = "abbxxxxzzy"
输出:[[3,6]]
解释:“xxxx” 是一个起始于 3 且终止于 6 的较大分组。

示例 2
输入:s = "abc"
输出:[]
解释:“a”,“b” 和 “c” 均不是符合要求的较大分组。

示例 3
输入:s = "abcdddeeeeaabbbcd"
输出:[[3,5],[6,9],[12,14]]
解释:较大分组为 “ddd”, “eeee” 和 “bbb”

示例 4
输入:s = "aba"
输出:[]

二、参考答案

此题比较简单,其实基本就是按照题目意思遍历一遍即可。时间复杂度为 O(N)。

需要注意一些细节,比如示例代码中的最后一个测试用例:

from typing import List


class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        if not s:
            return []

        result = []
        pre = s[0]
        count = 1
        for i in range(1, len(s)):
            if s[i] == pre:
                count += 1
            else:
                if count >= 3:
                    result.append([i-count, i-1])
                pre = s[i]
                count = 1
        if count >= 3:
            result.append([i-count+1, i])
        return result

s = Solution()
print(s.largeGroupPositions("abbxxxxzzy"))
print(s.largeGroupPositions("abc"))
print(s.largeGroupPositions("abcdddeeeeaabbbcd"))
print(s.largeGroupPositions("aaa"))

参考了一下官方的代码,官方代码更加的简洁,且少去了最后对于aaa这种特殊情况的判断。这里贴上官方代码做为学习:

class Solution:
    def largeGroupPositions(self, s: str) -> List[List[int]]:
        ret = list()
        n, num = len(s), 1

        for i in range(n):
            # i == n-1 为最后一种测试用例的情况
            # 通过 s[i] 与 s[i+1] 对比,这样不需要像上面参考代码一样,从 1 开始初始化,也少了变量 pre 的记录
            if i == n - 1 or s[i] != s[i + 1]:
                if num >= 3:
                    ret.append([i - num + 1, i])
                num = 1
            else:
                num += 1
        
        return ret

# 作者:LeetCode-Solution
# 链接:https://leetcode-cn.com/problems/positions-of-large-groups/solution/jiao-da-fen-zu-de-wei-zhi-by-leetcode-so-fi3n/
# 来源:力扣(LeetCode)
# 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

附上家中胖橘一枚,点个赞吧~

1人推荐
随时随地看视频
慕课网APP

热门评论

http://img.mukewang.com/5ff46f650001bd4e03440344.jpg

查看全部评论