Skip to content

Commit 30b208b

Browse files
6boris6boris
committed
add the Concurrent problem
1 parent 8d6d0c4 commit 30b208b

File tree

18 files changed

+517
-37
lines changed

18 files changed

+517
-37
lines changed

‎README.md

Lines changed: 0 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -31,9 +31,6 @@ LeetCode of algorithms with golang solution(updating:smiley:).
3131
</a>
3232
</p>
3333

34-
## Stargazers over time
35-
36-
[![Stargazers over time](https://starcharts.herokuapp.com/kylesliu/awesome-golang-leetcode.svg)](https://starcharts.herokuapp.com/kylesliu/awesome-golang-leetcode)
3734

3835
## Summary
3936

‎src/0076.Minimum-Window-Substring/README.md

Lines changed: 17 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -1,43 +1,38 @@
1-
# [1. Add Sum][title]
1+
# [76. Minimum Window Substring][title]
22

33
## Description
44

5-
Given two binary strings, return their sum (also a binary string).
6-
7-
The input strings are both **non-empty** and contains only characters `1` or `0`.
8-
5+
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
96
**Example 1:**
107

118
```
12-
Input: a = "11", b = "1"
13-
Output: "100"
9+
Input: S = "ADOBECODEBANC", T = "ABC"
10+
Output: "BANC"
1411
```
1512

16-
**Example 2:**
17-
18-
```
19-
Input: a = "1010", b = "1011"
20-
Output: "10101"
21-
```
2213

2314
**Tags:** Math, String
2415

2516
## 题意
26-
>给你两个二进制串，求其和的二进制串。
17+
>给定两个字符串：SS 和 TT，请找到 SS 中最短的一段，包含 TT 中所有字符。
18+
19+
- 注意
20+
如果 SS 中不存在这样的方案，则返回 ""；
21+
如果 SS 中存在这样的方案，则数据保证答案一定唯一；
2722

2823
## 题解
2924

3025
### 思路1
31-
> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
32-
33-
```go
26+
> (滑动窗口) O(n)
3427
3528
```
36-
37-
### 思路2
38-
> 思路2
39-
```go
40-
29+
首先用哈希表统计出 TT 中所有字符出现的次数，哈希表可以用C++中的 unordered_map，不了解用法的同学可以点这里。
30+
然后我们用两个指针 i,j(i≥j)i,j(i≥j)来扫描整个字符串，同时用一个哈希表统计 i,ji,j 之间每种字符出现的次数，每次遍历需要的操作如下：
31+
32+
加入 s[i]s[i]，同时更新哈希表；
33+
检查 s[j]s[j] 是否多余，如果是，则移除 s[j]s[j]；
34+
检查当前窗口是否已经满足 TT 中所有字符，如果是，则更新答案；
35+
时间复杂度分析：两个指针都严格递增，最多移动 nn 次，所以总时间复杂度是 O(n)O(n)。
4136
```
4237

4338
## 结语

‎src/0076.Minimum-Window-Substring/Solution.go

Lines changed: 32 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,35 @@
11
package Solution
22

3-
func Solution(x bool) bool {
4-
return x
3+
import "fmt"
4+
5+
func minWindow(s string, t string) string {
6+
hash := make(map[uint8]int)
7+
cut := 0
8+
9+
for i := 0; i < len(s); i++ {
10+
fmt.Println(s[i])
11+
if _, ok := hash[s[i]]; !ok {
12+
cut++
13+
}
14+
hash[s[i]]++
15+
}
16+
17+
res := ""
18+
for i, j, c := 0, 0, 0; i < len(s); i++ {
19+
if hash[s[i]] == 1 {
20+
c++
21+
}
22+
hash[s[i]]--
23+
for c == cut && hash[s[i]] < 0 {
24+
hash[s[j]]++
25+
j++
26+
}
27+
if c == cut {
28+
if res == "" || len(res) > i-j+1 {
29+
res = s[j : i-j+1]
30+
}
31+
}
32+
33+
}
34+
return res
535
}

‎src/0076.Minimum-Window-Substring/Solution_test.go

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,28 +2,27 @@ package Solution
22

33
import (
44
"reflect"
5+
"strconv"
56
"testing"
67
)
78

89
func TestSolution(t *testing.T) {
910
// 测试用例
1011
cases := []struct {
1112
name string
12-
inputs bool
13-
expect bool
13+
inputs []string
14+
expect string
1415
}{
15-
{"TestCacse 1", true, true},
16-
{"TestCacse 1", true, true},
17-
{"TestCacse 1", false, false},
16+
{"TestCase", []string{"ADOBECODEBANC", "ABC"}, "BANC"},
1817
}
1918

2019
// 开始测试
21-
for _, c := range cases {
22-
t.Run(c.name, func(t *testing.T) {
23-
ret := Solution(c.inputs)
24-
if !reflect.DeepEqual(ret, c.expect) {
20+
for i, c := range cases {
21+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
22+
got := minWindow(c.inputs[0], c.inputs[1])
23+
if !reflect.DeepEqual(got, c.expect) {
2524
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26-
c.expect, ret, c.inputs)
25+
c.expect, got, c.inputs)
2726
}
2827
})
2928
}

‎src/0125.Valid-Palindrome/README.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# [1. Add Sum][title]
2+
3+
## Description
4+
5+
Given two binary strings, return their sum (also a binary string).
6+
7+
The input strings are both **non-empty** and contains only characters `1` or `0`.
8+
9+
**Example 1:**
10+
11+
```
12+
Input: a = "11", b = "1"
13+
Output: "100"
14+
```
15+
16+
**Example 2:**
17+
18+
```
19+
Input: a = "1010", b = "1011"
20+
Output: "10101"
21+
```
22+
23+
**Tags:** Math, String
24+
25+
## 题意
26+
> 求2数之和
27+
28+
## 题解
29+
30+
### 思路1
31+
> 。。。。
32+
33+
```go
34+
35+
```
36+
37+
### 思路2
38+
> 思路2
39+
```go
40+
41+
```
42+
43+
## 结语
44+
45+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
46+
47+
[title]: https://leetcode.com/problems/two-sum/description/
48+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0125.Valid-Palindrome/Solution.go

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
package Solution
2+
3+
func Solution(x bool) bool {
4+
5+
return x
6+
}

‎src/0125.Valid-Palindrome/Solution_test.go

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package Solution
2+
3+
import (
4+
"reflect"
5+
"strconv"
6+
"testing"
7+
)
8+
9+
func TestSolution(t *testing.T) {
10+
// 测试用例
11+
cases := []struct {
12+
name string
13+
inputs bool
14+
expect bool
15+
}{
16+
{"TestCase", true, true},
17+
{"TestCase", true, true},
18+
{"TestCase", false, false},
19+
}
20+
21+
// 开始测试
22+
for i, c := range cases {
23+
t.Run(c.name+" "+strconv.Itoa(i), func(t *testing.T) {
24+
got := Solution(c.inputs)
25+
if !reflect.DeepEqual(got, c.expect) {
26+
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
27+
c.expect, got, c.inputs)
28+
}
29+
})
30+
}
31+
}
32+
33+
// 压力测试
34+
func BenchmarkSolution(b *testing.B) {
35+
36+
}
37+
38+
// 使用案列
39+
func ExampleSolution() {
40+
41+
}

‎src/0195.Tenth-Line/README.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# [1. Add Sum][title]
2+
3+
## Description
4+
5+
Given two binary strings, return their sum (also a binary string).
6+
7+
The input strings are both **non-empty** and contains only characters `1` or `0`.
8+
9+
**Example 1:**
10+
11+
```
12+
Input: a = "11", b = "1"
13+
Output: "100"
14+
```
15+
16+
**Example 2:**
17+
18+
```
19+
Input: a = "1010", b = "1011"
20+
Output: "10101"
21+
```
22+
23+
**Tags:** Math, String
24+
25+
## 题意
26+
> 求2数之和
27+
28+
## 题解
29+
30+
### 思路1
31+
> 。。。。
32+
33+
```go
34+
35+
```
36+
37+
### 思路2
38+
> 思路2
39+
```go
40+
41+
```
42+
43+
## 结语
44+
45+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
46+
47+
[title]: https://leetcode.com/problems/two-sum/description/
48+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0195.Tenth-Line/solution.sh

Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
#!/usr/bin/env bash
2+
3+
cat README.md | awk '{if (NR==10){print $0}}'
4+
5+
# Read from the file file.txt and output the tenth line to stdout.
6+
sed -n '10p' < file.txt

‎src/1114.Print-in-Order/README.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# [1. Add Sum][title]
2+
3+
## Description
4+
5+
Given two binary strings, return their sum (also a binary string).
6+
7+
The input strings are both **non-empty** and contains only characters `1` or `0`.
8+
9+
**Example 1:**
10+
11+
```
12+
Input: a = "11", b = "1"
13+
Output: "100"
14+
```
15+
16+
**Example 2:**
17+
18+
```
19+
Input: a = "1010", b = "1011"
20+
Output: "10101"
21+
```
22+
23+
**Tags:** Math, String
24+
25+
## 题意
26+
> 求2数之和
27+
28+
## 题解
29+
30+
### 思路1
31+
> 。。。。
32+
33+
```go
34+
35+
```
36+
37+
### 思路2
38+
> 思路2
39+
```go
40+
41+
```
42+
43+
## 结语
44+
45+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
46+
47+
[title]: https://leetcode.com/problems/two-sum/description/
48+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

0 commit comments

Comments
 (0)