【LeetCode】830. Positions of Large Groups 解题报告（Python）
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/positions-of-large-groups/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
题目大意
一个长字符串可以按照字符的连续出现，分组。每个组内都是一段连续的，字符相同的子字符串。
要求，长度不小于3的所有组的字符串起始和结束位置。
解题方法
直接暴力求解即可！从左到右遍历字符串，只要后面的字符和该组起始的字符相同，那么就是属于同一个组；否则，开辟一个新组，并且判断之前的这个组长度是否>=3，是的话进行保存。
第一遍提交没通过的原因是忘了判断，当字符串结束的时候也是一个组终止的标志。比如字符串"aaa"。
class Solution:
def largeGroupPositions(self, S):
"""
:type S: str
:rtype: List[List[int]]
"""
groups = []
before_index, before_char = 0, S[0]
for i, s in enumerate(S):
if s != before_char:
if i - before_index >= 3:
groups.append([before_index, i - 1])
before_index = i
before_char = s
if i - before_index >= 2:
groups.append([before_index, i])
return groups
二刷的时候，对结尾的判断是添加了一个大写字符，这样的话在不打扰之前小写字符串的基础上，增加了结束符号。
class Solution:
def largeGroupPositions(self, S):
"""
:type S: str
:rtype: List[List[int]]
"""
S = S + "A"
groups = []
previndex, prevc = 0, ""
for i, c in enumerate(S):
if not prevc:
prevc = c
previndex = i
elif prevc != c:
if i - previndex >= 3:
groups.append([previndex, i - 1])
previndex = i
prevc = c
return groups
日期
2018 年 5 月 27 日 ———— 周末的天气很好～
2018 年 11 月 16 日 —— 又到周五了！
最新文章
- XCode8目录整理后的几个警告消除,Missing file
- Django 1.10 中文文档------3.2.1 模型Models
- 使用Linux碎解二
- 《笨办法学C》笔记之基础语法
- HBase的快照技术
- 2016年10月30日 星期日 --出埃及记 Exodus 19:15
- 【Spring学习笔记-MVC-3.1】SpringMVC返回Json数据-方式1-扩展
- 调用DEDE日期时间格式整理大全
- Cloudcraft: 云架构图形可视化(智能AWS图表)
- 纯 Swift 封装的 SQLite 框架：SQLite.swift
- Window下Jenkins的安装
- 基于netcore实现mongodb和ElasticSearch之间的数据实时同步的工具（Mongo2Es）
- C# 使用 HttpClient 调用 WebService 提示 NoSOAPAction
- cordova获取app版本信息插件的使用：cordova-plugin-app-version
- [转]VS中的路径宏 OutDir、ProjectDir、SolutionDir各种路径含义
- Asp.net Webform的页面生命周期
- （微信小程序）一 ： 初识微信小程序
- C#把数组中的某个元素取出来放到第一个位置
- 虚拟机VMware中的CentOS字符界面和图形界面切换
- Mac系统下adb工具的配置