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

Commit3cad8d8

Browse files
committed
add new files
1 parent6cf16d4 commit3cad8d8

6 files changed

+220
-1
lines changed

‎104. Maximum Depth of Binary Tree.go

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,5 +14,11 @@ func maxDepth(root *TreeNode) int {
1414
}
1515
l:=maxDepth(root.Left)
1616
r:=maxDepth(root.Right)
17-
returnint(math.Max(float64(l),float64(r)))+1
17+
returnmax(l,r)+1
18+
}
19+
funcmax(x,yint)int {
20+
ifx>y {
21+
returnx
22+
}
23+
returny
1824
}
Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package main
2+
3+
typeTreeNodestruct {
4+
Valint
5+
Left*TreeNode
6+
Right*TreeNode
7+
}
8+
9+
/**
10+
根据中序和后续遍历结果，重建二叉树
11+
后续遍历的最后一个元素，是二叉树的root节点
12+
到中序数组中，root节点的位置，则左边用来递归创建左子树，右边用来递归创建右子树
13+
*/
14+
15+
typeIndexstruct {
16+
indexint
17+
}
18+
19+
funcbuildTree(inorder []int,postorder []int)*TreeNode {
20+
iflen(inorder)==0 {
21+
returnnil
22+
}
23+
//后续遍历的最后一个元素，是二叉树的root节点
24+
rootIndex:=&Index{len(postorder)-1}
25+
returnbuildTreeR(inorder,postorder,0,len(postorder)-1,rootIndex)
26+
}
27+
28+
funcbuildTreeR(inorder []int,postorder []int,startint,endint,rootIndex*Index)*TreeNode {
29+
ifstart>end {
30+
returnnil
31+
}
32+
33+
rootValue:=postorder[rootIndex.index]
34+
root:=&TreeNode{rootValue,nil,nil}
35+
rootIndex.index--
36+
37+
ifstart==end {
38+
returnroot
39+
}
40+
41+
//找到中序数组中，root节点的位置，则左边用来递归创建左子树，右边用来递归创建右子树
42+
index:=0
43+
fori:=start;i<=end;i++ {
44+
ifinorder[i]==rootValue {
45+
index=i
46+
break
47+
}
48+
}
49+
50+
root.Right=buildTreeR(inorder,postorder,index+1,end,rootIndex)
51+
root.Left=buildTreeR(inorder,postorder,start,index-1,rootIndex)
52+
53+
returnroot
54+
}

‎120. Triangle.go

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
package main
2+
3+
/**
4+
dp算法
5+
dp数组保存当前行获得的最小值
6+
从下往上转移
7+
初始化为最后一行的值
8+
*/
9+
10+
funcminimumTotal(triangle [][]int)int {
11+
l:=len(triangle)
12+
ifl==0 {
13+
return0
14+
}
15+
ifl==1 {
16+
returntriangle[0][0]
17+
}
18+
dp:=make([]int,l)
19+
//dp数组初始化成最后一行的值
20+
fori:=0;i<l;i++ {
21+
dp[i]=triangle[l-1][i]
22+
}
23+
fori:=l-2;i>=0;i-- {
24+
forj:=0;j<len(triangle[i]);j++ {
25+
dp[j]=min(dp[j],dp[j+1])+triangle[i][j]
26+
}
27+
}
28+
returndp[0]
29+
}
30+
funcmin(x,yint)int {
31+
ifx>y {
32+
returny
33+
}
34+
returnx
35+
36+
}

‎18. 4Sum.go

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
package main
2+
3+
import (
4+
"sort"
5+
)
6+
7+
/**
8+
四重循环加上剪枝AC
9+
三重循环加上左右指针居然MLE
10+
晕。。。
11+
*/
12+
funcfourSum(nums []int,targetint) [][]int {
13+
varret [][]int
14+
sort.Ints(nums)
15+
val:= [...]int{0,0,0}
16+
fori:=0;i<len(nums);i++ {
17+
ifi>0&&nums[i-1]==nums[i] {
18+
continue
19+
}
20+
forj:=i+1;j<len(nums);j++ {
21+
val[0]=nums[i]+nums[j]
22+
ifval[0]>target&&nums[j]>0 {//后面不可能有解
23+
break
24+
}
25+
ifj>i+1&&nums[j-1]==nums[j] {//相同元素
26+
continue
27+
}
28+
fork:=j+1;k<len(nums);k++ {
29+
val[1]=val[0]+nums[k]
30+
ifval[1]>target&&nums[k]>0 {
31+
break
32+
}
33+
ifk>j+1&&nums[k-1]==nums[k] {
34+
continue
35+
}
36+
form:=k+1;m<len(nums);m++ {
37+
val[2]=val[1]+nums[m]
38+
ifval[2]==target {
39+
tmp:= []int{nums[i],nums[j],nums[k],nums[m]}
40+
ret=append(ret,tmp)
41+
break
42+
}
43+
ifval[2]>target {
44+
break
45+
}
46+
}
47+
}
48+
}
49+
}
50+
returnret
51+
}

‎23. Merge k Sorted Lists.go

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package main
2+
3+
typeListNodestruct {
4+
Valint
5+
Next*ListNode
6+
}
7+
8+
/**
9+
分治的方法，不停的两两merge
10+
其中merge两个list的方法，就是#21
11+
*/
12+
13+
funcmergeKLists(lists []*ListNode)*ListNode {
14+
iflen(lists)==0 {
15+
returnnil
16+
}
17+
begin,end:=0,len(lists)-1
18+
forbegin<end {
19+
mid:= (begin+end-1)/2
20+
fori:=0;i<=mid;i++ {
21+
lists[i]=mergeTwoLists(lists[i],lists[end-i])
22+
}
23+
end= (begin+end)/2
24+
}
25+
returnlists[0]
26+
}
27+
28+
funcmergeTwoLists(l1*ListNode,l2*ListNode)*ListNode {
29+
ifl1==nil {
30+
returnl2
31+
}
32+
ifl2==nil {
33+
returnl1
34+
}
35+
ifl1.Val<l2.Val {
36+
l1.Next=mergeTwoLists(l1.Next,l2)
37+
returnl1
38+
}else {
39+
l2.Next=mergeTwoLists(l1,l2.Next)
40+
returnl2
41+
}
42+
43+
}

‎92. Reverse Linked List II.go

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package main
2+
3+
typeListNodestruct {
4+
Valint
5+
Next*ListNode
6+
}
7+
8+
funcreverseBetween(head*ListNode,mint,nint)*ListNode {
9+
shadowHead:=&ListNode{Next:head}//用于返回
10+
prevNode:=shadowHead
11+
//走到反转的起点位置
12+
fori:=1;i<m;i++ {
13+
prevNode=prevNode.Next
14+
head=head.Next
15+
}
16+
mNode:=head
17+
nNode:=head.Next
18+
//开始反转操作
19+
fori:=m;i<n;i++ {
20+
nextNNode:=nNode.Next
21+
nNode.Next=head
22+
head=nNode
23+
nNode=nextNNode
24+
}
25+
//把反转之后的list和原来的对接
26+
mNode.Next=nNode
27+
prevNode.Next=head
28+
returnshadowHead.Next
29+
}

0 commit comments

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