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

Commitf2e7d10

Browse files
committed
add new files
1 parent5d34e78 commitf2e7d10

11 files changed

+323
-1
lines changed

‎110. Balanced Binary Tree.go

Lines changed: 7 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -24,5 +24,11 @@ func getHeight(root *TreeNode) int {
2424
return0
2525
}
2626

27-
returnint(math.Max(float64(getHeight(root.Left)),float64(getHeight(root.Right)))+1)
27+
returnmymax(getHeight(root.Left),getHeight(root.Right))+1
28+
}
29+
funcmymax(x,yint)int {
30+
ifx>y {
31+
returnx
32+
}
33+
returny
2834
}
Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package main
2+
3+
/**
4+
用map保存元素出现次数
5+
如果比当前元素大1的元素也出现，则比较和的最大值
6+
*/
7+
8+
funcfindLHS(nums []int)int {
9+
10+
ret:=0
11+
iflen(nums)==0 {
12+
returnret
13+
}
14+
m:=make(map[int]int)
15+
for_,v:=rangenums {
16+
if_,ok:=m[v];ok {
17+
m[v]++
18+
}else {
19+
m[v]=1
20+
}
21+
}
22+
fork,v:=rangem {
23+
ifval,ok:=m[k+1];ok {
24+
ifv+val>ret {
25+
ret=v+val
26+
}
27+
}
28+
}
29+
returnret
30+
}

‎654. Maximum Binary Tree.go

Lines changed: 39 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,39 @@
1+
package main
2+
3+
typeTreeNodestruct {
4+
Valint
5+
Left*TreeNode
6+
Right*TreeNode
7+
}
8+
9+
/**
10+
递归
11+
先找到最大的，作为root
12+
然后左边的作为Left，右边的作为Right
13+
14+
*/
15+
16+
funcconstructMaximumBinaryTree(nums []int)*TreeNode {
17+
returnhelper(nums,0,len(nums))
18+
}
19+
20+
funchelper(nums []int,l,rint)*TreeNode {
21+
ifl==r {
22+
returnnil
23+
}
24+
maxi:=max(nums,l,r)
25+
root:=&TreeNode{Val:nums[maxi]}
26+
root.Left=helper(nums,l,maxi)
27+
root.Right=helper(nums,maxi+1,r)
28+
returnroot
29+
}
30+
31+
funcmax(nums []int,l,rint)int {
32+
ret:=l
33+
fori:=l;i<r;i++ {
34+
ifnums[ret]<nums[i] {
35+
ret=i
36+
}
37+
}
38+
returnret
39+
}

‎655. Print Binary Tree.go

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package main
2+
3+
import (
4+
"strconv"
5+
)
6+
7+
typeTreeNodestruct {
8+
Valint
9+
Left*TreeNode
10+
Right*TreeNode
11+
}
12+
13+
/**
14+
先得到树的最大高度h
15+
打印的宽度等于2的h次方-1
16+
*/
17+
18+
varret [][]string
19+
20+
funcprintTree(root*TreeNode) [][]string {
21+
ifroot==nil {
22+
returnnil
23+
}
24+
h:=getHeight(root)
25+
w:=pow(2,h)-1
26+
ret=make([][]string,h)
27+
fork:=rangeret {
28+
s:=make([]string,w)
29+
forkey:=ranges {
30+
s[key]=""
31+
}
32+
ret[k]=s
33+
}
34+
helper(root,0,0,w)
35+
returnret
36+
}
37+
funchelper(root*TreeNode,level,l,rint) {
38+
ifroot!=nil {
39+
mid:=l+ (r-l)/2
40+
ret[level][mid]=strconv.Itoa(root.Val)
41+
helper(root.Left,level+1,l,mid-1)
42+
helper(root.Right,level+1,mid+1,r)
43+
}
44+
}
45+
46+
funcgetHeight(root*TreeNode)int {
47+
ifroot==nil {
48+
return0
49+
}
50+
l:=getHeight(root.Left)
51+
r:=getHeight(root.Right)
52+
ifl>r {
53+
returnl+1
54+
}
55+
returnr+1
56+
}
57+
funcpow(x,yint)int {
58+
ret:=x
59+
fori:=1;i<y;i++ {
60+
ret*=x
61+
}
62+
returnret
63+
}

‎657. Robot Return to Origin.go

Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package main
2+
3+
/**
4+
分别记录上下左右的数量，
5+
如果上和下相等，并且左和右相等，则返回true
6+
*/
7+
funcjudgeCircle(movesstring)bool {
8+
mm:= []byte(moves)
9+
iflen(moves)==0 {
10+
returntrue
11+
}
12+
su,sd,sl,sr:=0,0,0,0
13+
for_,v:=rangemm {
14+
ifv=='U' {
15+
su++
16+
}
17+
ifv=='D' {
18+
sd++
19+
}
20+
ifv=='L' {
21+
sl++
22+
}
23+
ifv=='R' {
24+
sr++
25+
}
26+
}
27+
returnsu==sd&&sl==sr
28+
}

‎665. Non-decreasing Array.go

Lines changed: 25 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,25 @@
1+
package main
2+
3+
/**
4+
对于给定的数组 a1,a2,a3,a4,a5,…
5+
假设a4 < a3. 为了实现数组的单调非减，我们必须改变a4和a3其中的一个值，与此同时，为了后续计算的需要，我们应当尽可能使a4相对较小。此时，究竟是改变a3,还是a4取决于a2值的大小。我们假设a4 < a3， 那么a3 >= a2。 因此，如果a4 < a2, 那么我们将改变a4, 最好的选择就是令 a4 = a3; 否则的话，我们令a3 = a4， 但是这种情况我们并不需要考虑
6+
*/
7+
funccheckPossibility(nums []int)bool {
8+
iflen(nums)<=1 {
9+
returntrue
10+
}
11+
found:=false
12+
fori:=1;i<len(nums);i++ {
13+
ifnums[i]<nums[i-1] {
14+
iffound {
15+
returnfalse
16+
}else {
17+
ifi-2>=0&&nums[i]<nums[i-2] {
18+
nums[i]=nums[i-1]
19+
}
20+
found=true
21+
}
22+
}
23+
}
24+
returntrue
25+
}

‎669. Trim a Binary Search 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+
functrimBST(root*TreeNode,Lint,Rint)*TreeNode {
10+
11+
ifroot==nil {
12+
returnroot
13+
}
14+
ifroot.Val>R {
15+
returntrimBST(root.Left,L,R)
16+
}
17+
ifroot.Val<L {
18+
returntrimBST(root.Right,L,R)
19+
}
20+
root.Left=trimBST(root.Left,L,R)
21+
root.Right=trimBST(root.Right,L,R)
22+
returnroot
23+
}

‎680. Valid Palindrome II.go

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package main
2+
3+
/**
4+
greedy算法
5+
从两边向中间搜索，如果对应位置不相等
6+
则去掉左边的或者去掉右边的元素之后，剩余部分应该为回文
7+
*/
8+
funcvalidPalindrome(sstring)bool {
9+
str:= []byte(s)
10+
l:=len(s)
11+
fori:=0;i<l/2;i++ {
12+
ifstr[i]!=str[l-i-1] {
13+
j:=l-i-1
14+
returnisPalindrome(str,i+1,j)||isPalindrome(str,i,j-1)
15+
}
16+
}
17+
returntrue
18+
}
19+
funcisPalindrome(s []byte,l,rint)bool {
20+
fori:=l;i<=l+(r-l)/2;i++ {
21+
ifs[i]!=s[r-i+l] {
22+
returnfalse
23+
}
24+
}
25+
returntrue
26+
}

‎697. Degree of an Array.go

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
package main
2+
3+
/**
4+
先用一个map保存每个元素出现的位置
5+
6+
*/
7+
funcfindShortestSubArray(nums []int)int {
8+
9+
m:=make(map[int][]int)
10+
fori:=0;i<len(nums);i++ {
11+
m[nums[i]]=append(m[nums[i]],i)
12+
}
13+
14+
degree,ret:=0,len(nums)
15+
for_,v:=rangem {
16+
ifdegree<len(v) {
17+
degree=len(v)
18+
ret=v[len(v)-1]-v[0]+1
19+
}elseifdegree==len(v) {
20+
ifret>v[len(v)-1]-v[0]+1 {
21+
ret=v[len(v)-1]-v[0]+1
22+
}
23+
}
24+
}
25+
returnret
26+
}
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package main
2+
3+
typeTreeNodestruct {
4+
Valint
5+
Left*TreeNode
6+
Right*TreeNode
7+
}
8+
9+
/**
10+
如果插入值大于根节点，插入右子树
11+
反之插入左子树
12+
*/
13+
14+
funcinsertIntoBST(root*TreeNode,valint)*TreeNode {
15+
16+
ifroot==nil {
17+
return&TreeNode{
18+
Val:val,
19+
}
20+
}
21+
ifval>root.Val {
22+
root.Right=insertIntoBST(root.Right,val)
23+
}else {
24+
root.Left=insertIntoBST(root.Left,val)
25+
}
26+
returnroot
27+
28+
}
Lines changed: 28 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,28 @@
1+
package main
2+
3+
/**
4+
DP算法
5+
6+
dp[i][j]表示A和B共同前缀的长度
7+
初始都是0
8+
转移方程：dp[i][j] = dp[i+1][j+1]+1
9+
*/
10+
funcfindLength(A []int,B []int)int {
11+
ans:=0
12+
la,lb:=len(A),len(B)
13+
dp:=make([][]int,la+1)
14+
fork:=rangedp {
15+
dp[k]=make([]int,lb+1)
16+
}
17+
fori:=la-1;i>=0;i-- {
18+
forj:=lb-1;j>=0;j-- {
19+
ifA[i]==B[j] {
20+
dp[i][j]=dp[i+1][j+1]+1
21+
ifans<dp[i][j] {
22+
ans=dp[i][j]
23+
}
24+
}
25+
}
26+
}
27+
returnans
28+
}

0 commit comments

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