8000 add 93 problem solution · dycn/awesome-golang-leetcode@870f6ac · GitHub
[go: up one dir, main page]
Skip to content

Commit 870f6ac

Browse files
6boris6boris
committed
add 93 problem solution
1 parent e4654d4 commit 870f6ac

File tree

3 files changed

+82
-33
lines changed

3 files changed

+82
-33
lines changed

‎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) 8000
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
}

0 commit comments

Comments
 (0)
0