10000 feat: 46、47 · chenshiwei-io/leetcode@32bb718 · GitHub
[go: up one dir, main page]
Skip to content

Commit 32bb718

Browse files
author
chen-shiwei
committed
feat: 46、47
1 parent 4a33ec9 commit 32bb718

File tree

6 files changed

+208
-0
lines changed

6 files changed

+208
-0
lines changed

‎leetcode/46.全排列/permute.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package _6_全排列
2+
3+
func permute(nums []int) [][]int {
4+
var (
5+
paths [][]int
6+
path []int
7+
used = make([]bool, len(nums))
8+
fn func(nums []int)
9+
)
10+
11+
fn = func(nums []int) {
12+
if len(path) == len(nums) {
13+
tmp := make([]int, len(nums))
14+
copy(tmp, path)
15+
paths = append(paths, tmp)
16+
return
17+
}
18+
19+
for i := 0; i < len(nums); i++ {
20+
if used[i] {
21+
continue
22+
}
23+
path = append(path, nums[i])
24+
used[i] = true
25+
fn(nums)
26+
used[i] = false
27+
path = path[:len(path)-1]
28+
}
29+
}
30+
fn(nums)
31+
32+
return paths
33+
}

‎leetcode/46.全排列/permute_test.go

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

‎leetcode/47.全排列II/permuteUnique.go

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package _7_全排列II
2+
3+
import "sort"
4+
5+
func permuteUnique(nums []int) [][]int {
6+
var (
7+
paths [][]int
8+
path []int
9+
used = make([]bool, len(nums))
10+
fn func(nums []int)
11+
)
< 57AE code>12+
13+
fn = func(nums []int) {
14+
if len(nums) == len(path) {
15+
tmp := make([]int, len(path))
16+
copy(tmp, path)
17+
paths = append(paths, tmp)
18+
return
19+
}
20+
21+
for i := 0; i < len(nums); i++ {
22+
// used[i-1] == true 同一树枝使用过
23+
// used[i-1] == false 同一树层使用过
24+
if i > 0 && nums[i] == nums[i-1] && !used[i-1] {
25+
continue
26+
}
27+
if !used[i] {
28+
continue
29+
}
30+
path = append(path, nums[i])
31+
used[i] = true
32+
fn(nums)
33+
used[i] = false
34+
path = path[:len(path)-1]
35+
}
36+
}
37+
sort.Ints(nums)
38+
fn(nums)
39+
return paths
40+
}

‎leetcode/47.全排列II/permuteUnique_test.go

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package _7_全排列II
2+
3+
import (
4+
"reflect"
5+
"testing"
6+
)
7+
8+
func Test_permuteUnique(t *testing.T) {
9+
type args struct {
10+
nums []int
11+
}
12+
tests := []struct {
13+
name string
14+
args args
15+
want [][]int
16+
}{
17+
{name: `输入：nums = [1,1,2]
18+
输出：
19+
[[1,1,2],
20+
[1,2,1],
21+
[2,1,1]]`, args: args{nums: []int{1, 1, 2}}, want: [][]int{
22+
{1, 1, 2},
23+
{1, 2, 1},
24+
{2, 1, 1},
25+
}},
26+
}
27+
for _, tt := range tests {
28+
t.Run(tt.name, func(t *testing.T) {
29+
if got := permuteUnique(tt.args.nums); !reflect.DeepEqual(got, tt.want) {
30+
t.Errorf("permuteUnique() = %v, want %v", got, tt.want)
31+
}
32+
})
33+
}
34+
}

‎leetcode/491.递增子序列/findSubsequences.go

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package _91_递增子序列
2+
3+
// 不能排序去重，用map 去重，
4+
func findSubsequences(nums []int) [][]int {
5+
var (
6+
paths [][]int
7+
path []int
8+
fn func(nums []int, startIdx int)
9+
)
10+
11+
fn = func(nums []int, startIdx int) {
12+
13+
if len(path) >= 2 {
14+
tmp := make([]int, len(path))
15+
copy(tmp, path)
16+
paths = append(paths, tmp)
17+
if startIdx >= len(nums) {
18+
return
19+
}
20+
}
21+
22+
var used = make(map[int]bool)
23+
for i := startIdx; i < len(nums); i++ {
24+
// 不能排序去重，用map 去重，
25+
if len(path) != 0 && path[len(path)-1] > nums[i] /*判断递增*/ || used[nums[i]] {
26+
continue
27+
}
28+
used[nums[i]] = true
29+
path = append(path, nums[i])
30+
fn(nums, i+1)
31+
used[i] = false
32+
path = path[:len(path)-1]
33+
}
34+
35+
}
36+
37+
fn(nums, 0)
38+
39+
return paths
40+
}

‎leetcode/491.递增子序列/findSubsequences_test.go

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

0 commit comments

Comments
 (0)
0