Skip to content

Commit 2e796fe

Browse files
halfrosthalfrost
committed
Add solution 1573、1684、1685、1688、1689
1 parent 75e5a7e commit 2e796fe

21 files changed

+1219
-0
lines changed

‎leetcode/1573.Number-of-Ways-to-Split-a-String/1573. Number of Ways to Split a String.go

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package leetcode
2+
3+
func numWays(s string) int {
4+
ones := 0
5+
for _, c := range s {
6+
if c == '1' {
7+
ones++
8+
}
9+
}
10+
if ones%3 != 0 {
11+
return 0
12+
}
13+
if ones == 0 {
14+
return (len(s) - 1) * (len(s) - 2) / 2 % 1000000007
15+
}
16+
N, a, b, c, d, count := ones/3, 0, 0, 0, 0, 0
17+
for i, letter := range s {
18+
if letter == '0' {
19+
continue
20+
}
21+
if letter == '1' {
22+
count++
23+
}
24+
if count == N {
25+
a = i
26+
}
27+
if count == N+1 {
28+
b = i
29+
}
30+
if count == 2*N {
31+
c = i
32+
}
33+
if count == 2*N+1 {
34+
d = i
35+
}
36+
}
37+
return (b - a) * (d - c) % 1000000007
38+
}

‎leetcode/1573.Number-of-Ways-to-Split-a-String/1573. Number of Ways to Split a String_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 question1573 struct {
9+
para1573
10+
ans1573
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para1573 struct {
16+
s string
17+
}
18+
19+
// ans 是答案
20+
// one 代表第一个答案
21+
type ans1573 struct {
22+
one int
23+
}
24+
25+
func Test_Problem1573(t *testing.T) {
26+
27+
qs := []question1573{
28+
29+
{
30+
para1573{"10101"},
31+
ans1573{4},
32+
},
33+
34+
{
35+
para1573{"1001"},
36+
ans1573{0},
37+
},
38+
39+
{
40+
para1573{"0000"},
41+
ans1573{3},
42+
},
43+
44+
{
45+
para1573{"100100010100110"},
46+
ans1573{12},
47+
},
48+
}
49+
50+
fmt.Printf("------------------------Leetcode Problem 1573------------------------\n")
51+
52+
for _, q := range qs {
53+
_, p := q.ans1573, q.para1573
54+
fmt.Printf("【input】:%v 【output】:%v \n", p, numWays(p.s))
55+
}
56+
fmt.Printf("\n\n\n")
57+
}

‎leetcode/1573.Number-of-Ways-to-Split-a-String/README.md

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,108 @@
1+
# [1573. Number of Ways to Split a String](https://leetcode.com/problems/number-of-ways-to-split-a-string/)
2+
3+
4+
## 题目
5+
6+
Given a binary string `s` (a string consisting only of '0's and '1's), we can split `s` into 3 **non-empty** strings s1, s2, s3 (s1+ s2+ s3 = s).
7+
8+
Return the number of ways `s` can be split such that the number of characters '1' is the same in s1, s2, and s3.
9+
10+
Since the answer may be too large, return it modulo 10^9 + 7.
11+
12+
**Example 1:**
13+
14+
```
15+
Input: s = "10101"
16+
Output: 4
17+
Explanation: There are four ways to split s in 3 parts where each part contain the same number of letters '1'.
18+
"1|010|1"
19+
"1|01|01"
20+
"10|10|1"
21+
"10|1|01"
22+
23+
```
24+
25+
**Example 2:**
26+
27+
```
28+
Input: s = "1001"
29+
Output: 0
30+
31+
```
32+
33+
**Example 3:**
34+
35+
```
36+
Input: s = "0000"
37+
Output: 3
38+
Explanation: There are three ways to split s in 3 parts.
39+
"0|0|00"
40+
"0|00|0"
41+
"00|0|0"
42+
43+
```
44+
45+
**Example 4:**
46+
47+
```
48+
Input: s = "100100010100110"
49+
Output: 12
50+
51+
```
52+
53+
**Constraints:**
54+
55+
- `3 <= s.length <= 10^5`
56+
- `s[i]` is `'0'` or `'1'`.
57+
58+
## 题目大意
59+
60+
给你一个二进制串 s  （一个只包含 0 和 1 的字符串），我们可以将 s 分割成 3 个 非空 字符串 s1, s2, s3 （s1 + s2 + s3 = s）。请你返回分割 s 的方案数，满足 s1，s2 和 s3 中字符 '1' 的数目相同。由于答案可能很大，请将它对 10^9 + 7 取余后返回。
61+
62+
## 解题思路
63+
64+
- 这一题是考察的排列组合的知识。根据题意，如果 1 的个数不是 3 的倍数，直接返回 -1。如果字符串里面没有 1，那么切分的方案就是组合，在 n-1 个字母里面选出 2 个位置。利用组合的计算方法，组合数是 (n-1) * (n-2) / 2 。
65+
- 剩下的是 3 的倍数的情况。在字符串中选 2 个位置隔成 3 段。从第一段最后一个 1 到第二段第一个 1 之间的 0 的个数为 m1，从第二段最后一个 1 到第三段第一个 1 之间的 0 的个数为 m2。利用乘法原理，方案数为 m1 * m2。
66+
67+
## 代码
68+
69+
```go
70+
package leetcode
71+
72+
func numWays(s string) int {
73+
ones := 0
74+
for _, c := range s {
75+
if c == '1' {
76+
ones++
77+
}
78+
}
79+
if ones%3 != 0 {
80+
return 0
81+
}
82+
if ones == 0 {
83+
return (len(s) - 1) * (len(s) - 2) / 2 % 1000000007
84+
}
85+
N, a, b, c, d, count := ones/3, 0, 0, 0, 0, 0
86+
for i, letter := range s {
87+
if letter == '0' {
88+
continue
89+
}
90+
if letter == '1' {
91+
count++
92+
}
93+
if count == N {
94+
a = i
95+
}
96+
if count == N+1 {
97+
b = i
98+
}
99+
if count == 2*N {
100+
c = i
101+
}
102+
if count == 2*N+1 {
103+
d = i
104+
}
105+
}
106+
return (b - a) * (d - c) % 1000000007
107+
}
108+
```

‎leetcode/1684.Count-the-Number-of-Consistent-Strings/1684. Count the Number of Consistent Strings.go

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package leetcode
2+
3+
func countConsistentStrings(allowed string, words []string) int {
4+
allowedMap, res, flag := map[rune]int{}, 0, true
5+
for _, str := range allowed {
6+
allowedMap[str]++
7+
}
8+
for i := 0; i < len(words); i++ {
9+
flag = true
10+
for j := 0; j < len(words[i]); j++ {
11+
if _, ok := allowedMap[rune(words[i][j])]; !ok {
12+
flag = false
13+
break
14+
}
15+
}
16+
if flag {
17+
res++
18+
}
19+
}
20+
return res
21+
}

‎leetcode/1684.Count-the-Number-of-Consistent-Strings/1684. Count the Number of Consistent Strings_test.go

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package leetcode
2+
3+
import (
4+
"fmt"
5+
"testing"
6+
)
7+
8+
type question1684 struct {
9+
para1684
10+
ans1684
11+
}
12+
13+
// para 是参数
14+
// one 代表第一个参数
15+
type para1684 struct {
16+
allowed string
17+
words []string
18+
}
19+
20+
// ans 是答案
21+
// one 代表第一个答案
22+
type ans1684 struct {
23+
one int
24+
}
25+
26+
func Test_Problem1684(t *testing.T) {
27+
28+
qs := []question1684{
29+
30+
{
31+
para1684{"ab", []string{"ad", "bd", "aaab", "baa", "badab"}},
32+
ans1684{2},
33+
},
34+
35+
{
36+
para1684{"abc", []string{"a", "b", "c", "ab", "ac", "bc", "abc"}},
37+
ans1684{7},
38+
},
39+
40+
{
41+
para1684{"cad", []string{"cc", "acd", "b", "ba", "bac", "bad", "ac", "d"}},
42+
ans1684{4},
43+
},
44+
}
45+
46+
fmt.Printf("------------------------Leetcode Problem 1684------------------------\n")
47+
48+
for _, q := range qs {
49+
_, p := q.ans1684, q.para1684
50+
fmt.Printf("【input】:%v 【output】:%v\n", p, countConsistentStrings(p.allowed, p.words))
51+
}
52+
fmt.Printf("\n\n\n")
53+
}

‎leetcode/1684.Count-the-Number-of-Consistent-Strings/README.md

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
# [1684. Count the Number of Consistent Strings](https://leetcode.com/problems/count-the-number-of-consistent-strings/)
2+
3+
4+
## 题目
5+
6+
You are given a string `allowed` consisting of **distinct** characters and an array of strings `words`. A string is **consistent** if all characters in the string appear in the string `allowed`.
7+
8+
Return *the number of **consistent** strings in the array* `words`.
9+
10+
**Example 1:**
11+
12+
```
13+
Input: allowed = "ab", words = ["ad","bd","aaab","baa","badab"]
14+
Output: 2
15+
Explanation: Strings "aaab" and "baa" are consistent since they only contain characters 'a' and 'b'.
16+
17+
```
18+
19+
**Example 2:**
20+
21+
```
22+
Input: allowed = "abc", words = ["a","b","c","ab","ac","bc","abc"]
23+
Output: 7
24+
Explanation: All strings are consistent.
25+
26+
```
27+
28+
**Example 3:**
29+
30+
```
31+
Input: allowed = "cad", words = ["cc","acd","b","ba","bac","bad","ac","d"]
32+
Output: 4
33+
Explanation: Strings "cc", "acd", "ac", and "d" are consistent.
34+
35+
```
36+
37+
**Constraints:**
38+
39+
- `1 <= words.length <= 104`
40+
- `1 <= allowed.length <= 26`
41+
- `1 <= words[i].length <= 10`
42+
- The characters in `allowed` are **distinct**.
43+
- `words[i]` and `allowed` contain only lowercase English letters.
44+
45+
## 题目大意
46+
47+
给你一个由不同字符组成的字符串 `allowed` 和一个字符串数组 `words` 。如果一个字符串的每一个字符都在 `allowed` 中，就称这个字符串是 一致字符串 。
48+
49+
请你返回 `words` 数组中 一致字符串 的数目。
50+
51+
## 解题思路
52+
53+
- 简单题。先将 `allowed` 转化成 map。将 `words` 数组中每个单词的字符都在 map 中查找一遍，如果都存在就累加 res。如果有不存在的字母，不累加。最终输出 res 即可。
54+
55+
## 代码
56+
57+
```go
58+
package leetcode
59+
60+
func countConsistentStrings(allowed string, words []string) int {
61+
allowedMap, res, flag := map[rune]int{}, 0, true
62+
for _, str := range allowed {
63+
allowedMap[str]++
64+
}
65+
for i := 0; i < len(words); i++ {
66+
flag = true
67+
for j := 0; j < len(words[i]); j++ {
68+
if _, ok := allowedMap[rune(words[i][j])]; !ok {
69+
flag = false
70+
break
71+
}
72+
}
73+
if flag {
74+
res++
75+
}
76+
}
77+
return res
78+
}
79+
```

0 commit comments

Comments
 (0)