Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit15e1987

Browse files
authored
Merge pull request6boris#101 from kylesliu/develop
Develop
2 parentsbdfd879 +870f6ac commit15e1987

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
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+
funcrestoreIpAddresses(sstring) []string {
28+
varresult []string
29+
dfs(s, []string{}, &result)
30+
return result
31+
}
32+
33+
funcdfs(sstring,temp []string,result *[]string) {
34+
iflen(temp) ==4 &&len(s) ==0 {
35+
*result =append(*result, strings.Join(temp,"."))
36+
return
37+
}
38+
39+
iflen(temp) ==4 ||len(s) >3*(4-len(temp)) ||len(s) < (4-len(temp)) {
40+
return
41+
}
42+
43+
fori:=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
Lines changed: 34 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,37 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
import (
4+
"strconv"
5+
"strings"
6+
)
7+
8+
funcrestoreIpAddresses(sstring) []string {
9+
varresult []string
10+
dfs(s, []string{},&result)
11+
returnresult
12+
}
13+
14+
funcdfs(sstring,temp []string,result*[]string) {
15+
iflen(temp)==4&&len(s)==0 {
16+
*result=append(*result,strings.Join(temp,"."))
17+
return
18+
}
19+
20+
iflen(temp)==4||len(s)>3*(4-len(temp))||len(s)< (4-len(temp)) {
21+
return
22+
}
23+
24+
fori:=1;i<=3;i++ {
25+
ifi>len(s) {
26+
continue
27+
}
28+
num,_:=strconv.Atoi(s[:i])
29+
ifs[: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
funcTestSolution(t*testing.T) {
910
//测试用例
1011
cases:= []struct {
1112
namestring
12-
inputsbool
13-
expectbool
13+
inputsstring
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:=rangecases {
22-
t.Run(c.name,func(t*testing.T) {
23-
ret:=Solution(c.inputs)
24-
if!reflect.DeepEqual(ret,c.expect) {
20+
fori,c:=rangecases {
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
ifroot==nil {
1111
return0
1212
}
13-
13+
//左边为空只计算右边
1414
ifroot.Left==nil {
1515
returnminDepth(root.Right)+1
1616
}
17-
17+
//右边为空只计算左边
1818
ifroot.Right==nil {
1919
returnminDepth(root.Left)+1
2020
}
21-
21+
//正常计算左右2个子树
2222
returnmin(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+
funchasPathSum(root*TreeNode,sumint)bool {
5+
ifroot==nil {
6+
returnfalse
7+
}
8+
ifroot.Left==nil&&root.Right==nil {
9+
returnroot.Val==sum
10+
}
11+
returnhasPathSum(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+
funcTestSolution(t*testing.T) {
11+
//测试用例
12+
cases:= []struct {
13+
namestring
14+
inputs*TreeNode
15+
sumint
16+
expectbool
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+
fori,c:=rangecases {
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+
funcBenchmarkSolution(b*testing.B) {
43+
44+
}
45+
46+
//使用案列
47+
funcExampleSolution() {
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+
typeTreeNodestruct {
4+
Valint
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)
[8]ページ先頭
©2009-2025 Movatter.jp