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

Commit45b43c8

Browse files
committed
add new files
1 parent658824b commit45b43c8

10 files changed

+289
-7
lines changed

‎121. Best Time to Buy and Sell Stock.go

Lines changed: 17 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -3,11 +3,23 @@ package main
33
import"math"
44

55
funcmaxProfit(prices []int)int {
6-
max_profit:=0
7-
min_price:=math.MaxInt64
6+
maxProfit:=0
7+
minPrice:=math.MaxInt64
88
for_,v:=rangeprices {
9-
min_price=int(math.Min(float64(min_price),float64(v)))
10-
max_profit=int(math.Max(float64(max_profit),float64(v-min_price)))
9+
minPrice=mymin(minPrice,v)
10+
maxProfit=mymax(maxProfit,v-minPrice)
1111
}
12-
returnmax_profit
12+
returnmaxProfit
13+
}
14+
funcmymin(x,yint)int {
15+
ifx>y {
16+
returny
17+
}
18+
returnx
19+
}
20+
funcmymax(x,yint)int {
21+
ifx>y {
22+
returnx
23+
}
24+
returny
1325
}

‎124. Binary Tree Maximum Path Sum.go

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package main
2+
3+
import"math"
4+
5+
typeTreeNodestruct {
6+
Valint
7+
Left*TreeNode
8+
Right*TreeNode
9+
}
10+
11+
varansint
12+
13+
funcmaxPathSum(root*TreeNode)int {
14+
ans=math.MinInt32
15+
ifroot==nil {
16+
return0
17+
}
18+
ifroot.Left==nil&&root.Right==nil {
19+
returnroot.Val
20+
}
21+
maxPath(root)
22+
returnans
23+
}
24+
funcmymax(x,yint)int {
25+
ifx>y {
26+
returnx
27+
}
28+
returny
29+
}
30+
31+
funcmaxPath(root*TreeNode)int {
32+
ifroot==nil {
33+
return0
34+
}
35+
l:=mymax(0,maxPath(root.Left))
36+
r:=mymax(0,maxPath(root.Right))
37+
sum:=l+r+root.Val
38+
ans=mymax(ans,sum)
39+
returnmymax(l,r)+root.Val
40+
41+
}

‎307. Range Sum Query - Mutable.go

Lines changed: 0 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,5 @@
11
package main
22

3-
import"github.com/olivere/elastic"
4-
53
typeNumArraystruct {
64
n []int
75
}
Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package main
2+
3+
import"math"
4+
5+
/**
6+
三种状态之间互相转移：持有，售出，休息
7+
售出的收益等于持有加上当天价格
8+
持有的收益等于max(前一天休息之后买入，前一天持有）
9+
休息的收益等于max(前一天休息，前一天售出)
10+
*/
11+
funcmaxProfit(prices []int)int {
12+
sold,rest,hold:=0,0,math.MinInt32
13+
for_,v:=rangeprices {
14+
pre_sold:=sold
15+
sold=hold+v
16+
hold=mymax(hold,rest-v)
17+
rest=mymax(rest,pre_sold)
18+
}
19+
returnmymax(rest,sold)
20+
}
21+
22+
funcmymax(x,yint)int {
23+
ifx>y {
24+
returnx
25+
}
26+
returny
27+
}

‎377. Combination Sum IV.go

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,14 @@
1+
package main
2+
3+
funccombinationSum4(nums []int,targetint)int {
4+
dp:=make([]int,len(nums)+1)
5+
dp[0]=1
6+
fori:=1;i<=target;i++ {
7+
for_,v:=rangenums {
8+
ifv<=i {
9+
dp[i]+=dp[i-v]
10+
}
11+
}
12+
}
13+
returndp[target]
14+
}

‎416. Partition Equal Subset Sum.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package main
2+
3+
/**
4+
dp[i]:是否可以得到和i
5+
dp[i+v]=true,如果dp[i]==true，如果可以得到i，那么加上v就得到了i+v，所以dp[i+v]=true
6+
dp[0] =true,得到和0是可以的
7+
*/
8+
funccanPartition(nums []int)bool {
9+
sum:=0
10+
for_,v:=rangenums {
11+
sum+=v
12+
}
13+
ifsum%2==1 {
14+
returnfalse
15+
}
16+
dp:=make([]bool,sum+1)
17+
fork:=rangedp {
18+
dp[k]=false
19+
}
20+
dp[0]=true
21+
for_,v:=rangenums {
22+
//注意，这里是倒着循环，避免被覆盖
23+
fori:=sum;i>=0;i-- {
24+
ifdp[i] {
25+
dp[i+v]=true
26+
}
27+
}
28+
ifdp[sum/2] {
29+
returntrue
30+
}
31+
}
32+
returnfalse
33+
}

‎494. Target Sum.go

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package main
2+
3+
funcfindTargetSumWays(nums []int,Sint)int {
4+
S=myabs(S)
5+
sum:=0
6+
for_,v:=rangenums {
7+
sum+=v
8+
}
9+
ifsum<S|| (S+sum)%2!=0 {
10+
return0
11+
}
12+
target:= (S+sum)/2
13+
dp:=make([]int,target+1)
14+
dp[0]=1
15+
for_,num:=rangenums {
16+
fori:=target;i>=num;i-- {
17+
dp[i]+=dp[i-num]
18+
}
19+
}
20+
returndp[target]
21+
}
22+
funcmyabs(xint)int {
23+
ifx>=0 {
24+
returnx
25+
}
26+
return-x
27+
}

‎64. Minimum Path Sum.go

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package main
2+
3+
/**
4+
二维的dp
5+
*/
6+
funcminPathSum(grid [][]int)int {
7+
m:=len(grid)
8+
ifm==0 {
9+
return0
10+
}
11+
n:=len(grid[0])
12+
13+
fori:=0;i<m;i++ {
14+
forj:=0;j<n;j++ {
15+
ifi==0&&j==0 {
16+
continue
17+
}
18+
ifi==0 {
19+
grid[i][j]+=grid[i][j-1]
20+
}elseifj==0 {
21+
grid[i][j]+=grid[i-1][j]
22+
}else {
23+
grid[i][j]+=mymin(grid[i-1][j],grid[i][j-1])
24+
}
25+
}
26+
}
27+
returngrid[m-1][n-1]
28+
}
29+
30+
funcmymin(x,yint)int {
31+
ifx>y {
32+
returny
33+
}
34+
returnx
35+
}

‎687. Longest Univalue Path.go

Lines changed: 41 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,41 @@
1+
package main
2+
3+
import"log"
4+
5+
typeTreeNodestruct {
6+
Valint
7+
Left*TreeNode
8+
Right*TreeNode
9+
}
10+
11+
varansint
12+
13+
funclongestUnivaluePath(root*TreeNode)int {
14+
ans=0
15+
longestPath(root)
16+
returnans
17+
}
18+
19+
funclongestPath(root*TreeNode)int {
20+
ifroot==nil {
21+
return0
22+
}
23+
l:=longestPath(root.Left)
24+
r:=longestPath(root.Right)
25+
pl,pr:=0,0
26+
ifroot.Left!=nil&&root.Val==root.Left.Val {
27+
pl=l+1
28+
}
29+
ifroot.Right!=nil&&root.Val==root.Right.Val {
30+
pr=r+1
31+
}
32+
ans=mymax(ans,pl+pr)
33+
returnmymax(pl,pr)
34+
}
35+
36+
funcmymax(x,yint)int {
37+
ifx>y {
38+
returnx
39+
}
40+
returny
41+
}

‎956. Tallest Billboard.go

Lines changed: 54 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,54 @@
1+
package main
2+
3+
/**
4+
dp思路
5+
dp方程的键为两个柱子之间的高度差，值为当前高度差情况下，两个柱子的最小高度
6+
状态转移的时候有三种情况，其中后两种可以合并
7+
最后dp[0]保存的就是两个柱子高度差为0的时候，两个柱子的最小高度
8+
*/
9+
functallestBillboard(rods []int)int {
10+
sum:=0
11+
for_,v:=rangerods {
12+
sum+=v
13+
}
14+
dp:=make([]int,sum+1)
15+
fork,_:=rangedp {
16+
dp[k]=-1
17+
}
18+
dp[0]=0
19+
for_,v:=rangerods {
20+
cur:=make([]int,sum+1)
21+
copy(cur,dp)
22+
//for i := 0; i <= sum; i++ {
23+
ford,val:=rangecur {
24+
ifval!=-1 {
25+
ifd+v<=sum {
26+
dp[d+v]=mymax(dp[d+v],val)
27+
}
28+
dp[myabs(d-v)]=mymax(dp[myabs(d-v)],val+mymin(v,d))
29+
}
30+
}
31+
//fmt.Println(dp)
32+
}
33+
returndp[0]
34+
}
35+
funcmymin(x,yint)int {
36+
ifx>y {
37+
returny
38+
}
39+
returnx
40+
}
41+
42+
funcmyabs(xint)int {
43+
ifx>=0 {
44+
returnx
45+
}
46+
return-x
47+
}
48+
49+
funcmymax(x,yint)int {
50+
ifx>y {
51+
returnx
52+
}
53+
returny
54+
}

0 commit comments

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