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

Commit658824b

Browse files
committed
add new files
1 parent4b74f07 commit658824b

7 files changed

+246
-0
lines changed

‎198. House Robber.go‎

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package main
2+
3+
/*
4+
dp解法：
5+
状态方程：
6+
dp[i] = max(dp[i-2]+nums[i],dp[i-1])
7+
*/
8+
9+
funcrob(nums []int)int {
10+
iflen(nums)==0 {
11+
return0
12+
}
13+
iflen(nums)==1 {
14+
returnnums[0]
15+
}
16+
dp:=make([]int,len(nums))
17+
dp[0]=nums[0]
18+
dp[1]=mymax(nums[0],nums[1])
19+
fori:=2;i<len(nums);i++ {
20+
dp[i]=mymax(dp[i-2]+nums[i],dp[i-1])
21+
}
22+
returndp[len(nums)-1]
23+
}
24+
25+
funcmymax(x,yint)int {
26+
ifx>y {
27+
returnx
28+
}
29+
returny
30+
}

‎321. Create Maximum Number.go‎

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
package main
2+
3+
import (
4+
"strconv"
5+
"strings"
6+
)
7+
8+
funcmaxNumber(nums1 []int,nums2 []int,kint) []int {
9+
ans:= []int{}
10+
iflen(nums1)==0&&len(nums2)==0 {
11+
returnans
12+
}
13+
iflen(nums1)==0 {
14+
returnnums2[:k]
15+
}
16+
iflen(nums2)==0 {
17+
returnnums1[:k]
18+
}
19+
fori:=0;i<k;i++ {
20+
ifi>len(nums1)||k-i>len(nums2) {
21+
continue
22+
}
23+
m:=mergeArray(maxArray(nums1,i),maxArray(nums2,k-i))
24+
ifarrayToStr(ans)<arrayToStr(m) {
25+
ans=m
26+
}
27+
}
28+
returnans
29+
}
30+
31+
//数组转换成字符串，用于比较大小
32+
funcarrayToStr(nums []int)string {
33+
ret:=""
34+
str:= []string{}
35+
iflen(nums)==0 {
36+
returnret
37+
}
38+
for_,v:=rangenums {
39+
str=append(str,strconv.Itoa(v))
40+
}
41+
returnstrings.Join(str,"")
42+
}
43+
44+
//合并两个数组，不改变顺序的情况下，获得一个最大的数组
45+
funcmergeArray(nums1,nums2 []int) []int {
46+
iflen(nums1)==0 {
47+
returnnums2
48+
}
49+
iflen(nums2)==0 {
50+
returnnums1
51+
}
52+
ans:= []int{}
53+
i,j:=0,0
54+
fori<len(nums1)&&j<len(nums2) {
55+
ifbigArray(nums1[i:],nums2[j:]) {
56+
ans=append(ans,nums1[i])
57+
i++
58+
}else {
59+
ans=append(ans,nums2[j])
60+
j++
61+
}
62+
}
63+
ifi<len(nums1) {
64+
ans=append(ans,nums1[i:]...)
65+
}
66+
ifj<len(nums2) {
67+
ans=append(ans,nums2[j:]...)
68+
}
69+
returnans
70+
}
71+
72+
//取数组中前k个最大的值
73+
funcmaxArray(nums []int,kint) []int {
74+
ans:= []int{}
75+
ifk==0 {
76+
returnans
77+
}
78+
l:=len(nums)
79+
toPop:=0
80+
ifl<=k {
81+
returnnums
82+
}else {
83+
toPop=l-k
84+
}
85+
86+
for_,v:=rangenums {
87+
forlen(ans)>0&&v>ans[len(ans)-1]&&toPop>0 {
88+
ans=ans[:len(ans)-1]
89+
toPop--
90+
}
91+
ans=append(ans,v)
92+
}
93+
returnans[:k]
94+
}
95+
96+
//比较两个数组的大小，如果前一个大于后一个，返回true
97+
98+
funcbigArray(nums1,nums2 []int)bool {
99+
l1,l2:=len(nums1),len(nums2)
100+
l:=0
101+
ifl1>l2 {
102+
l=l2
103+
}else {
104+
l=l1
105+
}
106+
fori:=0;i<l;i++ {
107+
ifnums1[i]==nums2[i] {
108+
continue
109+
}
110+
ifnums1[i]>nums2[i] {
111+
returntrue
112+
}else {
113+
returnfalse
114+
}
115+
}
116+
ifl1>l2 {
117+
returntrue
118+
}
119+
returnfalse
120+
}

‎746. Min Cost Climbing Stairs.go‎

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

3+
/**
4+
dp解法
5+
状态方程：dp[i] =min(dp[i-2]+cost[i-2],dp[i-1]+cost[i-1])
6+
*/
7+
38
funcminCostClimbingStairs(cost []int)int {
49
l:=len(cost)
510
t:=make([]int,l)
Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package main
2+
3+
/**
4+
dp解法
5+
状态方程：
6+
如果最后一位是0：
7+
dp[i][0] = dp[i-1][0]
8+
dp[i][1] = min(dp[i-1][0], dp[i-1][1]) + 1
9+
如果最后一位是1：
10+
dp[i][0] = dp[i-1][0] + 1
11+
dp[i][1] = min(dp[i-1][0], dp[i-1][1])
12+
13+
TODO 可以降维优化
14+
*/
15+
16+
funcminFlipsMonoIncr(Sstring)int {
17+
l:=len(S)
18+
dp:=make([][]int,l+1)
19+
//二维数组初始化方法
20+
fori:=0;i<l+1;i++ {
21+
dp[i]=make([]int,2)
22+
}
23+
fori:=1;i<=l;i++ {
24+
ifS[i-1]=='0' {
25+
dp[i][0]=dp[i-1][0]
26+
dp[i][1]=mymin(dp[i-1][0],dp[i-1][1])+1
27+
}else {
28+
dp[i][0]=dp[i-1][0]+1
29+
dp[i][1]=mymin(dp[i-1][0],dp[i-1][1])
30+
}
31+
}
32+
returnmymin(dp[l][0],dp[l][1])
33+
}
34+
funcmymin(x,yint)int {
35+
ifx>y {
36+
returny
37+
}
38+
returnx
39+
}
Lines changed: 18 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,18 @@
1+
package main
2+
3+
funcrepeatedNTimes(A []int)int {
4+
l:=len(A)/2
5+
m:=make(map[int]int)
6+
for_,v:=rangeA {
7+
ifnum,ok:=m[v];ok {
8+
ifnum+1==l {
9+
returnv
10+
}else {
11+
m[v]++
12+
}
13+
}else {
14+
m[v]=1
15+
}
16+
}
17+
return0
18+
}

‎965. Univalued Binary Tree.go‎

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
package main
2+
3+
typeTreeNodestruct {
4+
Valint
5+
Left*TreeNode
6+
Right*TreeNode
7+
}
8+
9+
/**
10+
递归判断
11+
*/
12+
funcisUnivalTree(root*TreeNode)bool {
13+
ifroot==nil {
14+
returntrue
15+
}
16+
ifroot.Left!=nil&&root.Val!=root.Left.Val {
17+
returnfalse
18+
}
19+
ifroot.Right!=nil&&root.Val!=root.Right.Val {
20+
returnfalse
21+
}
22+
returnisUnivalTree(root.Left)&&isUnivalTree(root.Right)
23+
}

‎977. Squares of a Sorted Array.go‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
package main
2+
3+
import"sort"
4+
5+
funcsortedSquares(A []int) []int {
6+
fork,v:=rangeA {
7+
A[k]=v*v
8+
}
9+
sort.Ints(A)
10+
returnA
11+
}

0 commit comments

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