Skip to content

Commit 71b030c

Browse files
halfrosthalfrost
committed
Add solution 830
1 parent 0735a68 commit 71b030c

File tree

6 files changed

+234
-1
lines changed

6 files changed

+234
-1
lines changed

‎leetcode/0146.LRU-Cache/146. LRU Cache_test.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ import (
55
"testing"
66
)
77

8-
func Test_Problem147(t *testing.T) {
8+
func Test_Problem146(t *testing.T) {
99
obj := Constructor(2)
1010
fmt.Printf("obj = %v\n", MList2Ints(&obj))
1111
obj.Put(1, 1)

‎leetcode/0830.Positions-of-Large-Groups/830. Positions of Large Groups.go

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
package leetcode
2+
3+
func largeGroupPositions(S string) [][]int {
4+
res, end := [][]int{}, 0
5+
for end < len(S) {
6+
start, str := end, S[end]
7+
for end < len(S) && S[end] == str {
8+
end++
9+
}
10+
if end-start >= 3 {
11+
res = append(res, []int{start, end - 1})
12+
}
13+
}
14+
return res
15+
}

‎leetcode/0830.Positions-of-Large-Groups/830. Positions of Large Groups_test.go

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question830 struct {
9+
para830
10+
ans830
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para830 struct {
16+
S string
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans830 struct {
22+
one [][]int
23+
}
24+
25+
func Test_Problem830(t *testing.T) {
26+
27+
qs := []question830{
28+
29+
{
30+
para830{"abbxxxxzzy"},
31+
ans830{[][]int{{3, 6}}},
32+
},
33+
34+
{
35+
para830{"abc"},
36+
ans830{[][]int{{}}},
37+
},
38+
39+
{
40+
para830{"abcdddeeeeaabbbcd"},
41+
ans830{[][]int{{3, 5}, {6, 9}, {12, 14}}},
42+
},
43+
44+
{
45+
para830{"aba"},
46+
ans830{[][]int{{}}},
47+
},
48+
}
49+
50+
fmt.Printf("------------------------Leetcode Problem 830------------------------\n")
51+
52+
for _, q := range qs {
53+
_, p := q.ans830, q.para830
54+
fmt.Printf("【input】:%v 【output】:%v\n", p, largeGroupPositions(p.S))
55+
}
56+
fmt.Printf("\n\n\n")
57+
}

‎leetcode/0830.Positions-of-Large-Groups/README.md

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
# [830. Positions of Large Groups](https://leetcode.com/problems/positions-of-large-groups/)
2+
3+
4+
## 题目
5+
6+
In a string `s` of lowercase letters, these letters form consecutive groups of the same character.
7+
8+
For example, a string like `s = "abbxxxxzyy"` has the groups `"a"`, `"bb"`, `"xxxx"`, `"z"`, and `"yy"`.
9+
10+
A group is identified by an interval `[start, end]`, where `start` and `end` denote the start and end indices (inclusive) of the group. In the above example, `"xxxx"` has the interval `[3,6]`.
11+
12+
A group is considered **large** if it has 3 or more characters.
13+
14+
Return *the intervals of every **large** group sorted in **increasing order by start index***.
15+
16+
**Example 1:**
17+
18+
```
19+
Input: s = "abbxxxxzzy"
20+
Output: [[3,6]]
21+
Explanation: "xxxx" is the only large group with start index 3 and end index 6.
22+
```
23+
24+
**Example 2:**
25+
26+
```
27+
Input: s = "abc"
28+
Output: []
29+
Explanation: We have groups "a", "b", and "c", none of which are large groups.
30+
```
31+
32+
**Example 3:**
33+
34+
```
35+
Input: s = "abcdddeeeeaabbbcd"
36+
Output: [[3,5],[6,9],[12,14]]
37+
Explanation: The large groups are "ddd", "eeee", and "bbb".
38+
```
39+
40+
**Example 4:**
41+
42+
```
43+
Input: s = "aba"
44+
Output: []
45+
```
46+
47+
**Constraints:**
48+
49+
- `1 <= s.length <= 1000`
50+
- `s` contains lower-case English letters only.
51+
52+
## 题目大意
53+
54+
在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。我们称所有包含大于或等于三个连续字符的分组为 较大分组 。
55+
56+
找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。
57+
58+
## 解题思路
59+
60+
- 简单题。利用滑动窗口的思想，先扩大窗口的右边界，找到能相同字母且能到达的最右边。记录左右边界。再将窗口的左边界移动到上一次的右边界处。以此类推，重复扩大窗口的右边界，直至扫完整个字符串。最终所有满足题意的较大分组区间都在数组中了。
61+
62+
## 代码
63+
64+
```go
65+
package leetcode
66+
67+
func largeGroupPositions(S string) [][]int {
68+
res, end := [][]int{}, 0
69+
for end < len(S) {
70+
start, str := end, S[end]
71+
for end < len(S) && S[end] == str {
72+
end++
73+
}
74+
if end-start >= 3 {
75+
res = append(res, []int{start, end - 1})
76+
}
77+
}
78+
return res
79+
}
80+
```

‎website/content/ChapterFour/0830.Positions-of-Large-Groups.md

Lines changed: 80 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,80 @@
1+
# [830. Positions of Large Groups](https://leetcode.com/problems/positions-of-large-groups/)
2+
3+
4+
## 题目
5+
6+
In a string `s` of lowercase letters, these letters form consecutive groups of the same character.
7+
8+
For example, a string like `s = "abbxxxxzyy"` has the groups `"a"`, `"bb"`, `"xxxx"`, `"z"`, and `"yy"`.
9+
10+
A group is identified by an interval `[start, end]`, where `start` and `end` denote the start and end indices (inclusive) of the group. In the above example, `"xxxx"` has the interval `[3,6]`.
11+
12+
A group is considered **large** if it has 3 or more characters.
13+
14+
Return *the intervals of every **large** group sorted in **increasing order by start index***.
15+
16+
**Example 1:**
17+
18+
```
19+
Input: s = "abbxxxxzzy"
20+
Output: [[3,6]]
21+
Explanation: "xxxx" is the only large group with start index 3 and end index 6.
22+
```
23+
24+
**Example 2:**
25+
26+
```
27+
Input: s = "abc"
28+
Output: []
29+
Explanation: We have groups "a", "b", and "c", none of which are large groups.
30+
```
31+
32+
**Example 3:**
33+
34+
```
35+
Input: s = "abcdddeeeeaabbbcd"
36+
Output: [[3,5],[6,9],[12,14]]
37+
Explanation: The large groups are "ddd", "eeee", and "bbb".
38+
```
39+
40+
**Example 4:**
41+
42+
```
43+
Input: s = "aba"
44+
Output: []
45+
```
46+
47+
**Constraints:**
48+
49+
- `1 <= s.length <= 1000`
50+
- `s` contains lower-case English letters only.
51+
52+
## 题目大意
53+
54+
在一个由小写字母构成的字符串 s 中，包含由一些连续的相同字符所构成的分组。例如，在字符串 s = "abbxxxxzyy" 中，就含有 "a", "bb", "xxxx", "z" 和 "yy" 这样的一些分组。分组可以用区间 [start, end] 表示，其中 start 和 end 分别表示该分组的起始和终止位置的下标。上例中的 "xxxx" 分组用区间表示为 [3,6] 。我们称所有包含大于或等于三个连续字符的分组为 较大分组 。
55+
56+
找到每一个 较大分组 的区间，按起始位置下标递增顺序排序后，返回结果。
57+
58+
## 解题思路
59+
60+
- 简单题。利用滑动窗口的思想，先扩大窗口的右边界，找到能相同字母且能到达的最右边。记录左右边界。再将窗口的左边界移动到上一次的右边界处。以此类推，重复扩大窗口的右边界，直至扫完整个字符串。最终所有满足题意的较大分组区间都在数组中了。
61+
62+
## 代码
63+
64+
```go
65+
package leetcode
66+
67+
func largeGroupPositions(S string) [][]int {
68+
res, end := [][]int{}, 0
69+
for end < len(S) {
70+
start, str := end, S[end]
71+
for end < len(S) && S[end] == str {
72+
end++
73+
}
74+
if end-start >= 3 {
75+
res = append(res, []int{start, end - 1})
76+
}
77+
}
78+
return res
79+
}
80+
```

‎website/content/menu/index.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -396,6 +396,7 @@ headless: true
396396
- [0819.Most-Common-Word]({{< relref "/ChapterFour/0819.Most-Common-Word.md" >}})
397397
- [0826.Most-Profit-Assigning-Work]({{< relref "/ChapterFour/0826.Most-Profit-Assigning-Work.md" >}})
398398
- [0828.COPYRIGHT-PROBLEM-XXX]({{< relref "/ChapterFour/0828.COPYRIGHT-PROBLEM-XXX.md" >}})
399+
- [0830.Positions-of-Large-Groups]({{< relref "/ChapterFour/0830.Positions-of-Large-Groups.md" >}})
399400
- [0832.Flipping-an-Image]({{< relref "/ChapterFour/0832.Flipping-an-Image.md" >}})
400401
- [0834.Sum-of-Distances-in-Tree]({{< relref "/ChapterFour/0834.Sum-of-Distances-in-Tree.md" >}})
401402
- [0836.Rectangle-Overlap]({{< relref "/ChapterFour/0836.Rectangle-Overlap.md" >}})

0 commit comments

Comments
 (0)