8000 feat: 回溯 2021年05月25日21:02:12 · chenshiwei-io/leetcode@e53134d · GitHub
[go: up one dir, main page]
Skip to content

Commit e53134d

Browse files
author
陈世伟
committed
feat: 回溯 2021年05月25日21:02:12
1 parent 571483f commit e53134d

File tree

13 files changed

+449
-2
lines changed
Expand file tree

13 files changed

+449
-2
lines changed

‎leetcode/1047.删除字符串中的所有相邻重复项[stack]/remove_duplicates.go renamed to ‎leetcode/1047.删除字符串中的所有相邻重复项/remove_duplicates.go

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,17 @@
1-
package _047_删除字符串中的所有相邻重复项_stack_
1+
package _047_删除字符串中的所有相邻重复项
2+
3+
import "fmt"
24

35
func removeDuplicates(S string) string {
46
var stack []byte
57
for i := 0; i < len(S); i++ {
68
if len(stack) > 0 && stack[len(stack)-1] == S[i] {
9+
fmt.Println(stack[len(stack)-1], S[i], string(stack[:len(stack)-1]))
710
stack = stack[:len(stack)-1]
811
continue
912
}
1013
stack = append(stack, S[i])
1114
}
15+
fmt.Println(string(stack))
1216
return string(stack)
1317
}

‎leetcode/1047.删除字符串中的所有相邻重复项[stack]/remove_duplicates_test.go renamed to ‎leetcode/1047.删除字符串中的所有相邻重复项/remove_duplicates_test.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
package _047_删除字符串中的所有相邻重复项_stack_
1+
package _047_删除字符串中的所有相邻重复项
22

33
import "testing"
44

‎leetcode/17.电话号码的字母组合/letterCombinations.go

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package _7_电话号码的字母组合
2+
3+
var letterMap = []string{
4+
"", // 0
5+
"", // 1
6+
"abc", // 2
7+
"def", // 3
8+
"ghi", // 4
9+
"jkl", // 5
10+
"mno", // 6
11+
"pqrs", // 7
12+
"tuv", // 8
13+
"wxyz", // 9
14+
}
15+
16+
func letterCombinations(digits string) []string {
17+
var (
18+
paths []string
19+
path []byte
20+
fn func(digits string, startIdx int)
21+
)
22+
if len(digits) == 0 {
23+
return nil
24+
}
25+
26+
fn = func(digits string, startIdx int) {
27+
if len(path) == len(digits) {
28+
tmp := make([]byte, len(digits), len(digits))
29+
copy(tmp, path)
30+
paths = append(paths, string(tmp))
31+
return
32+
}
33+
34+
world := letterMap[digits[startIdx]-'0']
35+
// for 横向遍历
36+
for _, v := range world {
37+
path = append(path, byte(v))
38+
// 递归纵向遍历
39+
fn(digits, startIdx+1)
40+
// 回溯不断调整结果集
41+
path = path[:len(path)-1]
42+
}
43+
44+
}
45+
46+
fn(digits, 0)
47+
48+
return paths
49+
}

‎leetcode/17.电话号码的字母组合/letterCombinations_test.go

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package _7_电话号码的字母组合
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_letterCombinations(t *testing.T) {
9+
type args struct {
10+
digits string
11+
}
12+
tests := []struct {
13+
name string
14+
args args
15+
want []string
16+
}{
17+
{name: `输入：digits = "23"
18+
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]`, args: args{digits: "23"}, want: []string{
19+
"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf",
20+
}},
21+
}
22+
for _, tt := range tests {
23+
t.Run(tt.name, func(t *testing.T) {
24+
if got := letterCombinations(tt.args.digits); !reflect.DeepEqual(got, tt.want) {
25+
t.Errorf("letterCombinations() = %v, want %v", got, tt.want)
26+
}
27+
})
28+
}
29+
}

‎leetcode/216.组合总和III/combinationSum3.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package _16_组合总和III
2+
3+
func combinationSum3(k int, n int) [][]int {
4+
5+
var (
6+
fn func(k, n, startIdx int)
7+
paths [][]int
8+
path []int
9+
// 计算sum
10+
sum int
11+
)
12+
fn = func(k, n, startIdx int) {
13+
if len(path) == k { // 符合3个数
14+
if sum == n { // 判断总和
15+
tmp := make([]int, len(path), cap(path))
16+
copy(tmp, path)
17+
paths = append(paths, tmp)
18+
}
19+
return
20+
}
21+
for i := startIdx; i <= 9-(k-len(path))+1; i++ {
22+
path = append(path, i)
23+
sum += i
24+
fn(k, n, i+1)
25+
path = path[:len(path)-1]
26+
sum -= i
27+
}
28+
}
29+
30+
fn(k, n, 1)
31+
32+
return paths
33+
}

‎leetcode/216.组合总和III/combinationSum3_test.go

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package _16_组合总和III
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_combinationSum3(t *testing.T) {
9+
type args struct {
10+
k int
11+
n int
12+
}
13+
tests := []struct {
14+
name string
15+
args args
16+
want [][]int
17+
}{
18+
{name: `输入: k = 3, n = 7 输出: [[1,2,4]]`, args: args{
19+
k: 3,
20+
n: 7,
21+
}, want: [][]int{{1, 2, 4}}},
22+
}
23+
for _, tt := range tests {
24+
t.Run(tt.name, func(t *testing.T) {
25+
if got := combinationSum3(tt.args.k, tt.args.n); !reflect.DeepEqual(got, tt.want) {
26+
t.Errorf("combinationSum3() = %v, want %v", got, tt.want)
27+
}
28+
})
29+
}
30+
}

‎leetcode/39.组合总和/combinationSum.go

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package _9_组合总和
2+
3+
func combinationSum(candidates []int, target int) [][]int {
4+
var (
5+
paths [][]int
6+
path []int
7+
sum int
8+
fn func(candidates []int, target int, startIdx int)
9+
)
10+
11+
fn = func(candidates []int, target int, startIdx int) {
12+
if sum > target {
13+
return
14+
}
15+
16+
if sum == target {
17+
tmp := make([]int, len(path))
18+
copy(tmp, path)
19+
paths = append(paths, tmp)
20+
return
21+
}
22+
23+
for i := startIdx; i < len(candidates); i++ {
24+
path = append(path, candidates[i])
25+
sum += candidates[i]
26+
fn(candidates, target, i)
27+
path = path[:len(path)-1]
28+
sum -= candidates[i]
29+
}
30+
}
31+
32+
fn(candidates, target, 0)
33+
34+
return paths
35+
}

‎leetcode/39.组合总和/combinationSum_test.go

Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package _9_组合总和
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_combinationSum(t *testing.T) {
9+
type args struct {
10+
candidates []int
11+
target int
12+
}
13+
tests := []struct {
14+
name string
15+
args args
16+
want [][]int
17+
}{
18+
{name: `输入：candidates = [2,3,6,7], target = 7,
19+
所求解集为：
20+
[
21+
[7],
22+
[2,2,3]
23+
]`, args: args{
24+
candidates: []int{2, 3, 6, 7},
25+
target: 7,
26+
}, want: [][]int{
27+
{2, 2, 3},
28+
{7},
29+
}},
30+
}
31+
for _, tt := range tests {
32+
t.Run(tt.name, func(t *testing.T) {
33+
if got := combinationSum(tt.args.candidates, tt.args.target); !reflect.DeepEqual(got, tt.want) {
34+
t.Errorf("combinationSum() = %v, want %v", got, tt.want)
35+
}
36+
})
37+
}
38+
}

‎leetcode/450.删除二叉搜索树中的节点/deleteNode.go

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,59 @@
1+
package _50_删除二叉搜索树中的节点
2+
3+
/**
4+
* Definition for a binary tree node.
5+
* type TreeNode struct {
6+
* Val int
7+
* Left *TreeNode
8+
* Right *TreeNode
9+
* }
10+
*/
11+
type TreeNode struct {
12+
Val int
13+
Left *TreeNode
14+
Right *TreeNode
15+
}
16+
17+
func deleteNode(root *TreeNode, key int) *TreeNode {
18+
if root == nil {
19+
return root
20+
}
21+
if root.Val < key {
22+
root.Right = deleteNode(root.Right, key)
23+
} else if root.Val > key {
24+
root.Left = deleteNode(root.Left, key)
25+
} else if root.Val == key {
26+
// 要删除的节点等于叶子节点
27+
if root.Left == nil {
28+
return root.Right
29+
} else if root.Right == nil {
30+
return root.Left
31+
} else {
32+
node := root.Right
33+
for node.Left != nil {
34+
node = node.Left
35+
}
36+
37+
node.Left = root.Left
38+
return root.Right
39+
}
40+
41+
}
42+
43+
return root
44+
}
45+
46+
func successor(node *TreeNode) int {
47+
node = node.Right
48+
for node.Left != nil {
49+
node = node.Left
50+
}
51+
return node.Val
52+
}
53+
func predecessor(node *TreeNode) int {
54+
node = node.Left
55+
for node.Right != nil {
56+
node = node.Right
57+
}
58+
return node.Val
59+
}

‎leetcode/701.二叉搜索树中的插入操作/insertIntoBST.go

Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
1+
package _01_二叉搜索树中的插入操作
2+
3+
/**
4+
* Definition for a binary tree node.
5+
* type TreeNode struct {
6+
* Val int
7+
* Left *TreeNode
8+
* Right *TreeNode
9+
* }
10+
*/
11+
type TreeNode struct {
12+
Val int
13+
Left *TreeNode
14+
Right *TreeNode
15+
}
16+
17+
func insertIntoBST(root *TreeNode, val int) *TreeNode {
18+
var (
19+
fn func(node *TreeNode) *TreeNode
20+
)
21+
22+
fn = func(node *TreeNode) *TreeNode {
23+
if node == nil {
24+
node = &TreeNode{
25+
Val: val,
26+
Left: nil,
27+
Right: nil,
28+
}
29+
return node
30+
}
31+
32+
if node.Val > val {
33+
node.Left = fn(node.Left)
34+
} else {
35+
node.Right = fn(node.Right)
36+
}
37+
38+
return node
39+
}
40+
41+
root = fn(root)
42+
43+
return root
44+
45+
}

0 commit comments

Comments
 (0)
0