Skip to content

Commit c90926c

Browse files
halfrosthalfrost
committed
Add solution 1641
1 parent 05f5618 commit c90926c

28 files changed

+1089
-778
lines changed

‎README.md

Lines changed: 606 additions & 600 deletions
Large diffs are not rendered by default.

‎ctl/command.go

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -25,5 +25,6 @@ func init() {
2525
newBuildCommand(),
2626
newLabelCommand(),
2727
newPDFCommand(),
28+
newRefresh(),
2829
)
2930
}

‎ctl/refresh.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package main
2+
3+
import (
4+
"github.com/spf13/cobra"
5+
)
6+
7+
func newRefresh() *cobra.Command {
8+
cmd := &cobra.Command{
9+
Use: "refresh",
10+
Short: "Refresh all document",
11+
Run: func(cmd *cobra.Command, args []string) {
12+
refresh()
13+
},
14+
}
15+
// cmd.Flags().StringVar(&alias, "alias", "", "alias")
16+
// cmd.Flags().StringVar(&appId, "appid", "", "appid")
17+
return cmd
18+
}
19+
20+
func refresh() {
21+
delPreNext()
22+
buildREADME()
23+
buildChapterTwo(true)
24+
addPreNext()
25+
}

‎leetcode/1641.Count-Sorted-Vowel-Strings/1641. Count Sorted Vowel Strings.go

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package leetcode
2+
3+
// 解法一 打表
4+
func countVowelStrings(n int) int {
5+
res := []int{1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316251}
6+
return res[n]
7+
}
8+
9+
func makeTable() []int {
10+
res, array := 0, []int{}
11+
for i := 0; i < 51; i++ {
12+
countVowelStringsDFS(i, 0, []string{}, []string{"a", "e", "i", "o", "u"}, &res)
13+
array = append(array, res)
14+
res = 0
15+
}
16+
return array
17+
}
18+
19+
func countVowelStringsDFS(n, index int, cur []string, vowels []string, res *int) {
20+
vowels = vowels[index:]
21+
if len(cur) == n {
22+
(*res)++
23+
return
24+
}
25+
for i := 0; i < len(vowels); i++ {
26+
cur = append(cur, vowels[i])
27+
countVowelStringsDFS(n, i, cur, vowels, res)
28+
cur = cur[:len(cur)-1]
29+
}
30+
}
31+
32+
// 解法二 数学方法 —— 组合
33+
func countVowelStrings1(n int) int {
34+
return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24
35+
}

‎leetcode/1641.Count-Sorted-Vowel-Strings/1641. Count Sorted Vowel Strings_test.go

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

‎leetcode/1641.Count-Sorted-Vowel-Strings/README.md

Lines changed: 90 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,90 @@
1+
# [1641. Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)
2+
3+
4+
## 题目
5+
6+
Given an integer `n`, return *the number of strings of length* `n` *that consist only of vowels (*`a`*,* `e`*,* `i`*,* `o`*,* `u`*) and are **lexicographically sorted**.*
7+
8+
A string `s` is **lexicographically sorted** if for all valid `i`, `s[i]` is the same as or comes before `s[i+1]` in the alphabet.
9+
10+
**Example 1:**
11+
12+
```
13+
Input: n = 1
14+
Output: 5
15+
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].
16+
```
17+
18+
**Example 2:**
19+
20+
```
21+
Input: n = 2
22+
Output: 15
23+
Explanation: The 15 sorted strings that consist of vowels only are
24+
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
25+
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.
26+
27+
```
28+
29+
**Example 3:**
30+
31+
```
32+
Input: n = 33
33+
Output: 66045
34+
35+
```
36+
37+
**Constraints:**
38+
39+
- `1 <= n <= 50`
40+
41+
## 题目大意
42+
43+
给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
44+
45+
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
46+
47+
## 解题思路
48+
49+
- 题目给的数据量并不大，第一个思路是利用 DFS 遍历打表法。时间复杂度 O(1)，空间复杂度 O(1)。
50+
- 第二个思路是利用数学中的组合公式计算结果。题目等价于假设现在有 n 个字母，要求取 4 次球（可以选择不取）将字母分为 5 堆，问有几种取法。确定了取法以后，`a`，`e`，`i`，`o`，`u`，每个字母的个数就确定了，据题意要求按照字母序排序，那么最终字符串也就确定了。现在关注解决这个组合问题就可以了。把问题再转化一次，等价于，有 n+4 个字母，取 4 次，问有几种取法。+4 代表 4 个空操作，取走它们意味着不取。根据组合的数学定义，答案为 C(n+4,4)。
51+
52+
## 代码
53+
54+
```go
55+
package leetcode
56+
57+
// 解法一 打表
58+
func countVowelStrings(n int) int {
59+
res := []int{1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316251}
60+
return res[n]
61+
}
62+
63+
func makeTable() []int {
64+
res, array := 0, []int{}
65+
for i := 0; i < 51; i++ {
66+
countVowelStringsDFS(i, 0, []string{}, []string{"a", "e", "i", "o", "u"}, &res)
67+
array = append(array, res)
68+
res = 0
69+
}
70+
return array
71+
}
72+
73+
func countVowelStringsDFS(n, index int, cur []string, vowels []string, res *int) {
74+
vowels = vowels[index:]
75+
if len(cur) == n {
76+
(*res)++
77+
return
78+
}
79+
for i := 0; i < len(vowels); i++ {
80+
cur = append(cur, vowels[i])
81+
countVowelStringsDFS(n, i, cur, vowels, res)
82+
cur = cur[:len(cur)-1]
83+
}
84+
}
85+
86+
// 解法二 数学方法 —— 组合
87+
func countVowelStrings1(n int) int {
88+
return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24
89+
}
90+
```

‎website/content/ChapterFour/1640.Check-Array-Formation-Through-Concatenation.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -98,5 +98,5 @@ func canFormArray(arr []int, pieces [][]int) bool {
9898
----------------------------------------------
9999
<div style="display: flex;justify-content: space-between;align-items: center;">
100100
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1573.Number-of-Ways-to-Split-a-String/">⬅️上一页</a></p>
101-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1646.Get-Maximum-in-Generated-Array/">下一页➡️</a></p>
101+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1641.Count-Sorted-Vowel-Strings/">下一页➡️</a></p>
102102
</div>

‎website/content/ChapterFour/1641.Count-Sorted-Vowel-Strings.md

Lines changed: 97 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,97 @@
1+
# [1641. Count Sorted Vowel Strings](https://leetcode.com/problems/count-sorted-vowel-strings/)
2+
3+
4+
## 题目
5+
6+
Given an integer `n`, return *the number of strings of length* `n` *that consist only of vowels (*`a`*,* `e`*,* `i`*,* `o`*,* `u`*) and are **lexicographically sorted**.*
7+
8+
A string `s` is **lexicographically sorted** if for all valid `i`, `s[i]` is the same as or comes before `s[i+1]` in the alphabet.
9+
10+
**Example 1:**
11+
12+
```
13+
Input: n = 1
14+
Output: 5
15+
Explanation: The 5 sorted strings that consist of vowels only are ["a","e","i","o","u"].
16+
```
17+
18+
**Example 2:**
19+
20+
```
21+
Input: n = 2
22+
Output: 15
23+
Explanation: The 15 sorted strings that consist of vowels only are
24+
["aa","ae","ai","ao","au","ee","ei","eo","eu","ii","io","iu","oo","ou","uu"].
25+
Note that "ea" is not a valid string since 'e' comes after 'a' in the alphabet.
26+
27+
```
28+
29+
**Example 3:**
30+
31+
```
32+
Input: n = 33
33+
Output: 66045
34+
35+
```
36+
37+
**Constraints:**
38+
39+
- `1 <= n <= 50`
40+
41+
## 题目大意
42+
43+
给你一个整数 n，请返回长度为 n 、仅由元音 (a, e, i, o, u) 组成且按 字典序排列 的字符串数量。
44+
45+
字符串 s 按 字典序排列 需要满足：对于所有有效的 i，s[i] 在字母表中的位置总是与 s[i+1] 相同或在 s[i+1] 之前。
46+
47+
## 解题思路
48+
49+
- 题目给的数据量并不大，第一个思路是利用 DFS 遍历打表法。时间复杂度 O(1)，空间复杂度 O(1)。
50+
- 第二个思路是利用数学中的组合公式计算结果。题目等价于假设现在有 n 个字母，要求取 4 次球（可以选择不取）将字母分为 5 堆，问有几种取法。确定了取法以后，`a`，`e`，`i`，`o`，`u`，每个字母的个数就确定了，据题意要求按照字母序排序，那么最终字符串也就确定了。现在关注解决这个组合问题就可以了。把问题再转化一次，等价于，有 n+4 个字母，取 4 次，问有几种取法。+4 代表 4 个空操作，取走它们意味着不取。根据组合的数学定义，答案为 C(n+4,4)。
51+
52+
## 代码
53+
54+
```go
55+
package leetcode
56+
57+
// 解法一 打表
58+
func countVowelStrings(n int) int {
59+
res := []int{1, 5, 15, 35, 70, 126, 210, 330, 495, 715, 1001, 1365, 1820, 2380, 3060, 3876, 4845, 5985, 7315, 8855, 10626, 12650, 14950, 17550, 20475, 23751, 27405, 31465, 35960, 40920, 46376, 52360, 58905, 66045, 73815, 82251, 91390, 101270, 111930, 123410, 135751, 148995, 163185, 178365, 194580, 211876, 230300, 249900, 270725, 292825, 316251}
60+
return res[n]
61+
}
62+
63+
func makeTable() []int {
64+
res, array := 0, []int{}
65+
for i := 0; i < 51; i++ {
66+
countVowelStringsDFS(i, 0, []string{}, []string{"a", "e", "i", "o", "u"}, &res)
67+
array = append(array, res)
68+
res = 0
69+
}
70+
return array
71+
}
72+
73+
func countVowelStringsDFS(n, index int, cur []string, vowels []string, res *int) {
74+
vowels = vowels[index:]
75+
if len(cur) == n {
76+
(*res)++
77+
return
78+
}
79+
for i := 0; i < len(vowels); i++ {
80+
cur = append(cur, vowels[i])
81+
countVowelStringsDFS(n, i, cur, vowels, res)
82+
cur = cur[:len(cur)-1]
83+
}
84+
}
85+
86+
// 解法二 数学方法 —— 组合
87+
func countVowelStrings1(n int) int {
88+
return (n + 1) * (n + 2) * (n + 3) * (n + 4) / 24
89+
}
90+
```
91+
92+
93+
----------------------------------------------
94+
<div style="display: flex;justify-content: space-between;align-items: center;">
95+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1640.Check-Array-Formation-Through-Concatenation/">⬅️上一页</a></p>
96+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1646.Get-Maximum-in-Generated-Array/">下一页➡️</a></p>
97+
</div>

‎website/content/ChapterFour/1646.Get-Maximum-in-Generated-Array.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -98,6 +98,6 @@ func getMaximumGenerated(n int) int {
9898

9999
----------------------------------------------
100100
<div style="display: flex;justify-content: space-between;align-items: center;">
101-
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1640.Check-Array-Formation-Through-Concatenation/">⬅️上一页</a></p>
101+
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1641.Count-Sorted-Vowel-Strings/">⬅️上一页</a></p>
102102
<p><a href="https://books.halfrost.com/leetcode/ChapterFour/1647.Minimum-Deletions-to-Make-Character-Frequencies-Unique/">下一页➡️</a></p>
103103
</div>

0 commit comments

Comments
 (0)