8000 feat: 131 todo · chenshiwei-io/leetcode@631a2e8 · GitHub
[go: up one dir, main page]
Skip to content

Commit 631a2e8

Browse files
author
陈世伟
committed
feat: 131 todo
1 parent 462af17 commit 631a2e8

File tree

3 files changed

+135
-0
lines changed

3 files changed

+135
-0
lines changed

‎leetcode/131.分割回文串/partition.go

Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package _31_分割回文串
2+
3+
func partition(s string) [][]string {
4+
var (
5+
paths [][]string
6+
path []string
7+
fn func(s string, startIdx int)
8+
)
9+
if s == "" {
10+
return nil
11+
}
12+
13+
fn = func(s string, startIdx int) {
14+
15+
if startIdx >= len(s) {
16+
tmp := make([]string, len(path))
17+
copy(tmp, path)
18+
paths = append(paths, tmp)
19+
return
20+
}
21+
for i := startIdx; i < len(s); i++ {
22+
if !isPalindrome(s, startIdx, i) {
23+
continue
24+
}
25+
path = append(path, s[startIdx:i+1])
26+
fn(s, i+1)
27+
path = path[:len(path)-1]
28+
}
29+
}
30+
fn(s, 0)
31+
32+
return paths
33+
}
34+
35+
func isPalindrome(s string, start, end int) bool {
36+
for start < end {
37+
if s[start] != s[end] {
38+
return false
39+
}
40+
start++
41+
end--
42+
}
43+
return true
44+
}

‎leetcode/93.复原IP地址/restoreIpAddresses.go

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
package _3_复原IP地址
2+
3+
import "fmt"
4+
5+
func restoreIpAddresses(s string) []string {
6+
var (
7+
paths []string
8+
fn func(s string, startIdx int, n int)
9+
)
10+
11+
fn = func(s string, startIdx int, n int) {
12+
if n == 3 {
13+
fmt.Println("==3", n, s, s[startIdx:], isValidIP(s, startIdx, len(s)-1))
14+
if isValidIP(s, startIdx, len(s)-1) {
15+
fmt.Println("append", s)
16+
paths = append(paths, s)
17+
}
18+
return
19+
}
20+
21+
for i := startIdx; i < len(s); i++ {
22+
fmt.Println("isValidIP", string(s[startIdx:i+1]), isValidIP(s, startIdx, i))
23+
if !isValidIP(s, startIdx, i) {
24+
continue
25+
}
26+
s = s[:startIdx+i+1] + "." + s[startIdx+i+1:]
27+
n++
28+
fn(s, i+2, n)
29+
n--
30+
s = s[:startIdx+i+1] + s[startIdx+i+2:]
31+
}
32+
}
33+
fn(s, 0, 0)
34+
return paths
35+
}
36+
37+
// 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
38+
func isValidIP(s string, start, end int) bool {
39+
fmt.Println(s, start, end)
40+
if start > end {
41+
return false
42+
}
43+
44+
// 有前导 0
45+
if s[start] == '0' && start != end {
46+
return false
47+
}
48+
49+
var num uint8 = 0
50+
for i := start; i <= end; i++ {
51+
if s[i] > '9' || s[i] < '0' {
52+
return false
53+
}
54+
// 累加
55+
num = num*10 + (s[i] - '0')
56+
if num > 255 {
57+
return false
58+
}
59+
}
60+
61+
return true
62+
}

‎leetcode/93.复原IP地址/restoreIpAddresses_test.go

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package _3_复原IP地址
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_restoreIpAddresses(t *testing.T) {
9+
type args struct {
10+
s string
11+
}
12+
tests := []struct {
13+
name string
14+
args args
15+
want []string
16+
}{
17+
{name: `输入：s = "25525511135"
18+
输出：["255.255.11.135","255.255.111.35"]`, args: args{s: "25525511135"}, want: []string{
19+
"255.255.11.135", "255.255.111.35",
20+
}},
21+
}
22+
for _, tt := range tests {
23+
t.Run(tt.name, func(t *testing.T) {
24+
if got := restoreIpAddresses(tt.args.s); !reflect.DeepEqual(got, tt.want) {
25+
t.Errorf("restoreIpAddresses() = %v, want %v", got, tt.want)
26+
}
27+
})
28+
}
29+
}

0 commit comments

Comments
 (0)
0