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

Commit870f6ac

Browse files
committed
add 93 problem solution
1 parente4654d4 commit870f6ac

File tree

3 files changed

+82
-33
lines changed

3 files changed

+82
-33
lines changed
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
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp