leetcode 笔记


题目描述

在一个由小写字母构成的字符串 s 中,包含由一些连续的相同字符所构成的分组。

例如,在字符串 s = “abbxxxxzyy” 中,就含有 “a”, “bb”, “xxxx”, “z” 和 “yy” 这样的一些分组。

分组可以用区间 [start, end] 表示,其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 “xxxx” 分组用区间表示为 [3,6] 。

我们称所有包含大于或等于三个连续字符的分组为 较大分组 。

找到每一个 较大分组 的区间,按起始位置下标递增顺序排序后,返回结果。

 

示例 1

输入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"
输出[]
 
提示

1 <= s.length <= 1000
s 仅含小写英文字母

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/positions-of-large-groups
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

code

  • c++

class Solution {
 public:
  vector<vector<int>> largeGroupPositions(string s) {
    vector<vector<int>> ans;
    for (int i = 1, start = 0, size = s.size(); i <= size; i++)
      if (i == size || s[i] != s[i - 1]) {
        if (i - start >= 3) ans.push_back({start, i - 1});
        start = i;
      }
    return ans;
  }
};
  • kotlin

一刀流

fun largeGroupPositions(s: String): List<List<Int>> = (1..s.length).fold(mutableListOf<List<Int>>() to 0) { (acc, pre), i -> if (i == s.length || s[i] != s[i - 1]) { acc.apply { if (i - pre >= 3) this += listOf(pre, i - 1) } to i } else acc to pre }.first
class Solution {
    fun largeGroupPositions(s: String): List<List<Int>> =
        (1..s.length).fold(mutableListOf<List<Int>>() to 0) { (acc, pre), i ->
            if (i == s.length || s[i] != s[i - 1]) {
                acc.apply { if (i - pre >= 3) this += listOf(pre, i - 1) } to i
            } else
                acc to pre
        }.first
}
  • scala

def largeGroupPositions(s: String): List[List[Int]] = (1 to s.length).foldLeft(List[List[Int]]() -> 0) { (acc, i) => if (i == s.length || s(i) != s(i - 1)) (if (i - acc._2 >= 3) acc._1 :+ List(acc._2, i - 1) else acc._1) -> i else acc}._1
object Solution {
  def largeGroupPositions(s: String): List[List[Int]] =
    (1 to s.length).foldLeft(List[List[Int]]() -> 0) { (acc, i) =>
      if (i == s.length || s(i) != s(i - 1))
        (if (i - acc._2 >= 3) acc._1 :+ List(acc._2, i - 1) else acc._1) -> i
      else
        acc
    }._1
}
  • Rust

pub fn large_group_positions(s: String) -> Vec<Vec<i32>> {(1..=s.len()).fold((vec![], 0usize), |(mut acc, pre), i|if i == s.len() || s.as_bytes()[i] != s.as_bytes()[i - 1] {if i - pre >= 3 {acc.push(vec![pre as i32, i as i32 - 1])} (acc, i)} else {(acc, pre)}).0}
impl Solution {
    pub fn large_group_positions(s: String) -> Vec<Vec<i32>> {
        (1..=s.len())
            .fold((vec![], 0usize), |(mut acc, pre), i| {
                if i == s.len() || s.as_bytes()[i] != s.as_bytes()[i - 1] {
                    if i - pre >= 3 {
                        acc.push(vec![pre as i32, i as i32 - 1])
                    }
                    (acc, i)
                } else {
                    (acc, pre)
                }
            })
            .0
    }
}