8000 Merge pull request #101 from kylesliu/develop · dycn/awesome-golang-leetcode@15e1987 · GitHub
[go: up one dir, main page]
Skip to content

Commit 15e1987

Browse files
6boris6boris
authored
Merge pull request 6boris#101 from kylesliu/develop
Develop
2 parents bdfd879 + 870f6ac commit 15e1987

File tree

13 files changed

+337
-37
lines changed

13 files changed

+337
-37
lines changed

‎generate.sh

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ git reset --hard origin/master
88
git pull
99

1010
# GitBook
11+
#npm install gitbook-cli -g
1112
#gitbook serve --config book.json . gitbook
1213
gitbook build --config book.json . gitbook
1314

@@ -16,4 +17,4 @@ gitbook build --config book.json . gitbook
1617
#npm install --save-dev all-contributors-cli
1718
#npm run contributors:generate
1819
#all-contributors add kylesliu code,blog,design,doc
19-
#all-contributors generate
20+
#all-contributors generate

‎src/0093.Restore-IP-Addresses/README.md

Lines changed: 39 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,48 +1,66 @@
1-
# [1. Add Sum][title]
1+
# [93. Restore IP Addresses][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`.
5+
Given a string containing only digits, restore it by returning all possible valid IP address combinations.
86

97
**Example 1:**
108

119
```
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"
10+
Input: "25525511135"
11+
Output: ["255.255.11.135", "255.255.111.35"]
2112
```
2213

2314
**Tags:** Math, String
2415

2516
## 题意
26-
>给你两个二进制串，求其和的二进制串。
17+
> 求2数之和
2718
2819
## 题解
2920

3021
### 思路1
31-
> 按照小学算数那么来做，用 `carry` 表示进位，从后往前算，依次往前，每算出一位就插入到最前面即可，直到把两个二进制串都遍历完即可。
22+
> 直接暴力搜索出所有合法方案。
23+
合法的IP地址由四个0到255的整数组成。我们直接枚举四个整数的位数，然后判断每个数的范围是否在0到255。
24+
时间复杂度分析：一共 nn 个数字，n−1n−1 个数字间隔，相当于从 n−1n−1 个数字间隔中挑3个断点，所以计算量是 O(C3n−1)O(Cn−13)。
3225

3326
```go
27+
func restoreIpAddresses(s string) []string {
28+
var result []string
29+
dfs(s, []string{}, &result)
30+
return result
31+
}
32+
33+
func dfs(s string, temp []string, result *[]string) {
34+
if len(temp) == 4 && len(s) == 0 {
35+
*result = append(*result, strings.Join(temp, "."))
36+
return
37+
}
38+
39+
if len(temp) == 4 || len(s) > 3*(4-len(temp)) || len(s) < (4-len(temp)) {
40+
return
41+
}
42+
43+
for i := 1; i <= 3; i++ {
44+
if i > len(s) {
45+
continue
46+
}
47+
num, _ := strconv.Atoi(s[:i])
48+
if s[:i] != strconv.Itoa(num) || num > 255 {
49+
continue
50+
}
51+
52+
temp = append(temp, s[:i])
53+
dfs(s[i:], temp, result)
54+
temp = temp[:len(temp)-1]
55+
}
56+
}
3457

3558
```
3659

37-
### 思路2
38-
> 思路2
39-
```go
40-
41-
```
4260

4361
## 结语
4462

4563
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
4664

47-
[title]: https://leetcode.com/problems/two-sum/description/
65+
[title]: https://leetcode.com/problems/restore-ip-addresses/
4866
[me]: https://github.com/kylesliu/awesome-golang-leetcode

‎src/0093.Restore-IP-Addresses/Solution.go

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

3-
func Solution(x bool) bool {
4-
return x
3+
import (
4+
"strconv"
5+
"strings"
6+
)
7+
8+
func restoreIpAddresses(s string) []string {
9+
var result []string
10+
dfs(s, []string{}, &result)
11+
return result
12+
}
13+
14+
func dfs(s string, temp []string, result *[]string) {
15+
if len(temp) == 4 && len(s) == 0 {
16+
*result = append(*result, strings.Join(temp, "."))
17+
return
18+
}
19+
20+
if len(temp) == 4 || len(s) > 3*(4-len(temp)) || len(s) < (4-len(temp)) {
21+
return
22+
}
23+
24+
for i := 1; i <= 3; i++ {
25+
if i > len(s) {
26+
continue
27+
}
28+
num, _ := strconv.Atoi(s[:i])
29+
if s[:i] != strconv.Itoa(num) || num > 255 {
30+
continue
31+
}
32+
33+
temp = append(temp, s[:i])
34+
dfs(s[i:], temp, result)
35+
temp = temp[:len(temp)-1]
36+
}
537
}

‎src/0093.Restore-IP-Addresses/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", "25525511135", []string{"255.255.11.135", "255.255.111.35"}},
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 := restoreIpAddresses(c.inputs)
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/0111.Minimum-Depth-of-Binary-Tree/Solution.go

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -10,15 +10,15 @@ func minDepth(root *TreeNode) int {
1010
if root == nil {
1111
return 0
1212
}
13-
13+
// 左边为空只计算右边
1414
if root.Left == nil {
1515
return minDepth(root.Right) + 1
1616
}
17-
17+
// 右边为空只计算左边
1818
if root.Right == nil {
1919
return minDepth(root.Left) + 1
2020
}
21-
21+
// 正常计算左右2个子树
2222
return min(minDepth(root.Left), minDepth(root.Right)) + 1
2323
}
2424

‎src/0112.Path-Sum/README.md

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
# [112. Path Sum][title]
2+
3+
## Description
4+
5+
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
6+
7+
Note: A leaf is a node with no children.
8+
9+
**Example 1:**
10+
Given the below binary tree and sum = 22,
11+
12+
```
13+
5
14+
/ \
15+
4 8
16+
/ / \
17+
11 13 4
18+
/ \ \
19+
7 2 1
20+
```
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/0112.Path-Sum/Solution.go

Lines changed: 13 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,13 @@
1+
package Solution
2+
3+
// 递归
4+
func hasPathSum(root *TreeNode, sum int) bool {
5+
if root == nil {
6+
return false
7+
}
8+
if root.Left == nil && root.Right == nil {
9+
return root.Val == sum
10+
}
11+
return hasPathSum(root.Left, sum-root.Val) || hasPathSum(root.Right, sum-root.Val)
12+
}
13+

‎src/0112.Path-Sum/Solution_test.go

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

‎src/0112.Path-Sum/TreeNode.go

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,7 @@
1+
package Solution
2+
3+
type TreeNode struct {
4+
Val int
5+
Left *TreeNode
6+
Right *TreeNode
7+
}

‎src/0113.Path-Sum-II/README.md

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
# [113. Path Sum II][title]
2+
3+
## Description
4+
5+
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
6+
7+
Note: A leaf is a node with no children.
8+
9+
**Example 1:**
10+
Given the below binary tree and sum = 22,
11+
12+
```
13+
5
14+
/ \
15+
4 8
16+
/ / \
17+
11 13 4
18+
/ \ / \
19+
7 2 5 1
20+
```
21+
22+
```java
23+
[
24+
[5,4,11,2],
25+
[5,8,4,5]
26+
]
27+
```
28+
29+
**Tags:** Math, String
30+
31+
## 题意
32+
> 求2数之和
33+
34+
## 题解
35+
36+
### 思路1
37+
> 。。。。
38+
39+
```go
40+
41+
```
42+
43+
### 思路2
44+
> 思路2
45+
```go
46+
47+
```
48+
49+
## 结语
50+
51+
如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-golang-leetcode][me]
52+
53+
[title]: https://leetcode.com/problems/two-sum/description/
54+
[me]: https://github.com/kylesliu/awesome-golang-leetcode

0 commit comments

Comments
 (0)
0