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

Commit8d6d0c4

Browse files
authored
Merge pull request6boris#85 from kylesliu/develop
update the 46 problem
2 parentsd78ae36 +f65687b commit8d6d0c4

File tree

3 files changed

+52
-15
lines changed

3 files changed

+52
-15
lines changed

‎src/0046.Permutations/README.md

Lines changed: 6 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -23,13 +23,16 @@ Output: "10101"
2323
**Tags:** Math, String
2424

2525
##题意
26-
>给你两个二进制串,求其和的二进制串。
26+
>给出一列互不相同的整数,返回其全排列
2727
2828
##题解
2929

3030
###思路1
31-
>按照小学算数那么来做,用`carry` 表示进位,从后往前算,依次往前,每算出一位就插入到最前面即可,直到把两个二进制串都遍历完即可。
32-
31+
>我们从前往后,一位一位枚举,每次选择一个没有被使用过的数。
32+
选好之后,将该数的状态改成“已被使用”,同时将该数记录在相应位置上,然后递归。
33+
递归返回时,不要忘记将该数的状态改成“未被使用”,并将该数从相应位置上删除。
34+
35+
时间复杂度分析:搜索树中最后一层共 n!n! 个节点,前面所有层加一块的节点数量相比于最后一层节点数是无穷小量,可以忽略。且最后一层节点记录方案的计算量是 O(n)O(n),所以总时间复杂度是 O(n×n!)O(n×n!)。
3336
```go
3437

3538
```

‎src/0046.Permutations/Solution.go

Lines changed: 30 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,33 @@
11
package Solution
22

3-
funcSolution(xbool)bool {
4-
returnx
3+
varans [][]int
4+
varvisit []bool
5+
6+
funcpermute(nums []int) [][]int {
7+
8+
ans= [][]int{}
9+
visit=make([]bool,len(nums))
10+
dfs(nums, []int{})
11+
returnans
12+
}
13+
14+
funcdfs(nums []int,curr []int) {
15+
iflen(curr)==len(nums) {
16+
temp:=make([]int,len(curr))
17+
copy(temp,curr)
18+
ans=append(ans,temp)
19+
return
20+
}
21+
22+
foridx,num:=rangenums {
23+
if!visit[idx] {
24+
curr=append(curr,num)
25+
visit[idx]=true
26+
27+
dfs(nums,curr)
28+
29+
visit[idx]=false
30+
curr=curr[:len(curr)-1]
31+
}
32+
}
533
}

‎src/0046.Permutations/Solution_test.go

Lines changed: 16 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -2,28 +2,34 @@ 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+
inputs[]int
14+
expect[][]int
1415
}{
15-
{"TestCacse 1",true,true},
16-
{"TestCacse 1",true,true},
17-
{"TestCacse 1",false,false},
16+
{"TestCase", []int{1,1,2}, [][]int{
17+
{1,1,2},
18+
{1,2,1},
19+
{1,1,2},
20+
{1,2,1},
21+
{2,1,1},
22+
{2,1,1},
23+
}},
1824
}
1925

2026
//开始测试
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) {
27+
fori,c:=rangecases {
28+
t.Run(c.name+" "+strconv.Itoa(i),func(t*testing.T) {
29+
got:=permute(c.inputs)
30+
if!reflect.DeepEqual(got,c.expect) {
2531
t.Fatalf("expected: %v, but got: %v, with inputs: %v",
26-
c.expect,ret,c.inputs)
32+
c.expect,got,c.inputs)
2733
}
2834
})
2935
}

0 commit comments

Comments
 (0)

[8]ページ先頭

©2009-2025 Movatter.jp