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

Commitc7c6c12

Browse files
authored
Merge pull request6boris#216 from kylesliu/develop
add some tree solution
2 parents49f2bf0 +d6763a7 commitc7c6c12

File tree

76 files changed

+2271
-1913
lines changed

Some content is hidden

Large Commits have some content hidden by default. Use the searchbox below for content that may be hidden.

76 files changed

+2271
-1913
lines changed

‎lcof/of042/README.md‎

Lines changed: 0 additions & 32 deletions
This file was deleted.

‎lcof/of042/Solution.go‎

Lines changed: 45 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1,16 +1,57 @@
11
package Solution
22

3-
funcmaxSubArray(nums []int)int {
3+
// 动态规划1
4+
funcmaxSubArray_1(nums []int)int {
5+
iflen(nums)==1 {
6+
returnnums[0]
7+
}
8+
dp:=make([]int,len(nums))
9+
dp[0]=nums[0]
10+
ans:=dp[0]
11+
fori:=1;i<len(nums);i++ {
12+
dp[i]=max(dp[i-1]+nums[i],nums[i])
13+
ans=max(ans,dp[i])
14+
}
15+
returnans
16+
}
17+
18+
// 动态规划2
19+
funcmaxSubArray_2(nums []int)int {
420
ans:=nums[0]
521
fori:=1;i<len(nums);i++ {
6-
ifnums[i-1]>0 {
7-
nums[i]+=nums[i-1]
8-
}
22+
nums[i]=max(nums[i-1]+nums[i],nums[i])
923
ans=max(ans,nums[i])
1024
}
1125
returnans
1226
}
1327

28+
// 分治
29+
funcmaxSubArray_3(nums []int)int {
30+
returnget(nums,0,len(nums)-1).mSum
31+
}
32+
33+
funcpushUp(l,rStatus)Status {
34+
iSum:=l.iSum+r.iSum
35+
lSum:=max(l.lSum,l.iSum+r.lSum)
36+
rSum:=max(r.rSum,r.iSum+l.rSum)
37+
mSum:=max(max(l.mSum,r.mSum),l.rSum+r.lSum)
38+
returnStatus{lSum,rSum,mSum,iSum}
39+
}
40+
41+
funcget(nums []int,l,rint)Status {
42+
ifl==r {
43+
returnStatus{nums[l],nums[l],nums[l],nums[l]}
44+
}
45+
m:= (l+r)>>1
46+
lSub:=get(nums,l,m)
47+
rSub:=get(nums,m+1,r)
48+
returnpushUp(lSub,rSub)
49+
}
50+
51+
typeStatusstruct {
52+
lSum,rSum,mSum,iSumint
53+
}
54+
1455
funcmax(x,yint)int {
1556
ifx>y {
1657
returnx

‎lcof/of042/Solution_test.go‎

Lines changed: 15 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,10 @@
11
package Solution
22

33
import (
4+
"fmt"
45
"reflect"
56
"runtime"
7+
"strings"
68
"testing"
79

810
"github.com/stretchr/testify/assert"
@@ -12,10 +14,12 @@ import (
1214
typeSolutionFuncTypefunc([]int)int
1315

1416
varSolutionFuncList= []SolutionFuncType{
15-
maxSubArray,
17+
maxSubArray_1,
18+
maxSubArray_2,
19+
maxSubArray_3,
1620
}
1721

18-
//test info struct
22+
//Test info struct
1923
typeCasestruct {
2024
namestring
2125
inputs []int
@@ -24,24 +28,23 @@ type Case struct {
2428

2529
// test case
2630
varcases= []Case{
27-
{
28-
name:"TestCase 1",
29-
inputs: []int{-2,1,-3,4,-1,2,1,-5,4},
30-
expect:6,
31-
},
31+
{name:"TestCase 1",inputs: []int{1},expect:1},
32+
{name:"TestCase 2",inputs: []int{-2,1},expect:1},
33+
{name:"TestCase 3",inputs: []int{-2,-1},expect:-1},
34+
{name:"TestCase 4",inputs: []int{-2,1,-3,4,-1,2,1,-5,4},expect:6},
3235
}
3336

3437
// TestSolution Example for solution test cases
3538
funcTestSolution(t*testing.T) {
3639
ast:=assert.New(t)
3740

3841
for_,f:=rangeSolutionFuncList {
42+
funcName:=strings.Split(runtime.FuncForPC(reflect.ValueOf(f).Pointer()).Name(),".")[1]
3943
for_,c:=rangecases {
40-
t.Run(c.name,func(t*testing.T) {
41-
actual:=f(c.inputs)
42-
ast.Equal(c.expect,actual,
43-
"func: %v case: %v ",
44-
runtime.FuncForPC(reflect.ValueOf(f).Pointer()).Name(),c.name)
44+
t.Run(fmt.Sprintf("%s %s",funcName,c.name),func(t*testing.T) {
45+
got:=f(c.inputs)
46+
ast.Equal(c.expect,got,
47+
"func: %v case: %v ",funcName,c.name)
4548
})
4649
}
4750
}

‎lcof/of053-II/Solution.go‎

Lines changed: 49 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,49 @@
1+
package Solution
2+
3+
import (
4+
"sort"
5+
)
6+
7+
funcmissingNumber_1(nums []int)int {
8+
sort.Ints(nums)
9+
ifnums[0]!=0 {
10+
return0
11+
}elseifnums[len(nums)-1]!=len(nums) {
12+
returnlen(nums)
13+
}
14+
fori:=1;i<len(nums);i++ {
15+
ifi!=nums[i] {
16+
returni
17+
}
18+
}
19+
return0
20+
}
21+
22+
funcmissingNumber_2(nums []int)int {
23+
m:=make(map[int]int)
24+
for_,v:=rangenums {
25+
m[v]++
26+
}
27+
fori:=rangenums {
28+
if_,ok:=m[i+1];!ok {
29+
returni+1
30+
}
31+
}
32+
return0
33+
}
34+
35+
funcmissingNumber_3(nums []int)int {
36+
ans:=len(nums)
37+
fori,v:=rangenums {
38+
ans^=i^v
39+
}
40+
returnans
41+
}
42+
43+
funcmissingNumber_4(nums []int)int {
44+
sum:=len(nums)* (len(nums)+1)/2
45+
for_,v:=rangenums {
46+
sum-=v
47+
}
48+
returnsum
49+
}

‎lcof/of053-II/Solution_test.go‎

Lines changed: 55 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,55 @@
1+
package Solution
2+
3+
import (
4+
"fmt"
5+
"reflect"
6+
"runtime"
7+
"strings"
8+
"testing"
9+
10+
"github.com/stretchr/testify/assert"
11+
)
12+
13+
// Solution func Info
14+
typeSolutionFuncTypefunc([]int)int
15+
16+
varSolutionFuncList= []SolutionFuncType{
17+
missingNumber_1,
18+
missingNumber_2,
19+
missingNumber_3,
20+
missingNumber_4,
21+
}
22+
23+
// Test case info struct
24+
typeCasestruct {
25+
namestring
26+
input []int
27+
expectint
28+
}
29+
30+
// Test case
31+
varcases= []Case{
32+
{"TestCase 1", []int{3,0,1},2},
33+
{"TestCase 2", []int{9,6,4,2,3,5,7,0,1},8},
34+
{"TestCase 2", []int{0,1},2},
35+
}
36+
37+
// TestSolution Run test case for all solutions
38+
funcTestSolution(t*testing.T) {
39+
ast:=assert.New(t)
40+
41+
for_,f:=rangeSolutionFuncList {
42+
funcName:=strings.Split(runtime.FuncForPC(reflect.ValueOf(f).Pointer()).Name(),".")[1]
43+
for_,c:=rangecases {
44+
t.Run(fmt.Sprintf("%s %s",funcName,c.name),func(t*testing.T) {
45+
nums:=make([]int,0)
46+
for_,v:=rangec.input {
47+
nums=append(nums,v)
48+
}
49+
got:=f(nums)
50+
ast.Equal(c.expect,got,
51+
"func: %v case: %v ",funcName,c.name)
52+
})
53+
}
54+
}
55+
}

‎lcof/of054/README.md‎

Lines changed: 0 additions & 32 deletions
This file was deleted.

‎lcof/of054/Solution.go‎

Lines changed: 18 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -10,22 +10,24 @@ type TreeNode struct {
1010
Right*TreeNode
1111
}
1212

13-
funckthLargest(root*TreeNode,kint)int {
14-
varnums []int
15-
nums=dfs(&nums,root)
16-
returnnums[k-1]
17-
}
13+
funckthLargest_1(root*TreeNode,kint)int {
14+
ans:=-1
15+
vardfsfunc(node*TreeNode)
16+
dfs=func(node*TreeNode) {
17+
ifnode==nil {
18+
return
19+
}
20+
dfs(node.Right)
21+
ifk==0 {
22+
return
23+
}
24+
k--
25+
ifk==0 {
26+
ans=node.Val
27+
}
28+
dfs(node.Left)
1829

19-
// 逆中序遍历（右中左 -- 递减序列）
20-
funcdfs(nums*[]int,r*TreeNode) []int {
21-
ifr.Right!=nil {
22-
dfs(nums,r.Right)
23-
}
24-
ifr!=nil {
25-
*nums=append(*nums,r.Val)
26-
}
27-
ifr.Left!=nil {
28-
dfs(nums,r.Left)
2930
}
30-
return*nums
31+
dfs(root)
32+
returnans
3133
}

‎lcof/of054/Solution_test.go‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,7 +12,7 @@ import (
1212
typeSolutionFuncTypefunc(*TreeNode,int)int
1313

1414
varSolutionFuncList= []SolutionFuncType{
15-
kthLargest,
15+
kthLargest_1,
1616
}
1717

1818
//test info struct

‎leetcode/1-100/0094.Binary-Tree-Inorder-Traversal/Solution.go‎

Lines changed: 13 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -6,27 +6,28 @@ type TreeNode struct {
66
Right*TreeNode
77
}
88

9-
funcinorderTraversal(root*TreeNode) []int {
9+
funcinorderTraversal_1(root*TreeNode) []int {
1010
ans:=make([]int,0)
1111
ifroot!=nil {
12-
ans=append(ans,inorderTraversal(root.Left)...)
12+
ans=append(ans,inorderTraversal_1(root.Left)...)
1313
ans=append(ans,root.Val)
14-
ans=append(ans,inorderTraversal(root.Right)...)
14+
ans=append(ans,inorderTraversal_1(root.Right)...)
1515
}
1616
returnans
1717
}
1818

1919
funcinorderTraversal_2(root*TreeNode) []int {
20-
ans,stack:=make([]int,0), []*TreeNode{}
21-
forroot!=nil||len(stack)>0 {
22-
forroot!=nil {
23-
stack=append(stack,root)
24-
root=root.Left
20+
ans,stk:=make([]int,0), []*TreeNode{}
21+
node:=root
22+
fornode!=nil||len(stk)>0 {
23+
fornode!=nil {
24+
stk=append(stk,node)
25+
node=node.Left
2526
}
26-
root=stack[len(stack)-1]
27-
stack=stack[:len(stack)-1]
28-
ans=append(ans,root.Val)
29-
root=root.Right
27+
node=stk[len(stk)-1]
28+
stk=stk[:len(stk)-1]
29+
ans=append(ans,node.Val)
30+
node=node.Right
3031
}
3132
returnans
3233
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp