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

Commitdef75b2

Browse files
committed
add new files
1 parent981b85e commitdef75b2

5 files changed

+200
-0
lines changed

‎234. Palindrome Linked List.go

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package main
2+
3+
typeListNodestruct {
4+
Valint
5+
Next*ListNode
6+
}
7+
8+
/**
9+
把链表的前半部分反转，如果整个链表是回文的话，反转之后应该是
10+
1->2->1->2这样的形式
11+
然后依次比较对应位置上的值是否相等
12+
*/
13+
funcisPalindrome(head*ListNode)bool {
14+
ifhead==nil||head.Next==nil {
15+
returntrue
16+
}
17+
fast,slow,tmp:=head,head,head
18+
varlListNode
19+
forfast!=nil&&fast.Next!=nil {
20+
//快指针每次前进两步
21+
fast=fast.Next.Next
22+
//慢指针负责反转前半部分链表
23+
tmp=slow.Next
24+
slow.Next=l.Next
25+
l.Next=slow
26+
slow=tmp
27+
}
28+
iffast!=nil {
29+
slow=slow.Next
30+
}
31+
tmp=l.Next
32+
//比较对应位置上的节点值是否相等
33+
forslow!=nil&&tmp!=nil&&slow.Val==tmp.Val {
34+
slow,tmp=slow.Next,tmp.Next
35+
}
36+
returnslow==nil
37+
}
Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package main
2+
3+
typeNumMatrixstruct {
4+
s [][]int
5+
}
6+
7+
/**
8+
trick是行的方向上，保存累加值
9+
这样计算sum的时候，只有用一次减法就搞定了
10+
*/
11+
12+
funcConstructor(matrix [][]int)NumMatrix {
13+
m:=len(matrix)
14+
ifm==0 {
15+
s:=make([][]int,0)
16+
returnNumMatrix{
17+
s:s,
18+
}
19+
}
20+
n:=len(matrix[0])
21+
fori:=0;i<m;i++ {
22+
forj:=1;j<n;j++ {
23+
matrix[i][j]+=matrix[i][j-1]
24+
}
25+
}
26+
returnNumMatrix{
27+
s:matrix,
28+
}
29+
}
30+
31+
func (this*NumMatrix)SumRegion(row1int,col1int,row2int,col2int)int {
32+
ifrow2>=len(this.s)||col2>=len(this.s[0]) {
33+
return0
34+
}
35+
ret:=0
36+
ifcol1==0 {
37+
fori:=row1;i<=row2;i++ {
38+
ret+= this.s[i][col2]
39+
}
40+
}else {
41+
fori:=row1;i<=row2;i++ {
42+
ret+= this.s[i][col2]-this[i][col1-1]
43+
}
44+
}
45+
returnret
46+
}

‎310. Minimum Height Trees.go

Lines changed: 63 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,63 @@
1+
package main
2+
3+
/**
4+
从叶子节点开始不停的向中间收缩。
5+
首先遍历所有的节点，保存对应的入度关系（由于没有方向，所以需要保存两个方向的关系）
6+
然后找到所有的叶子节点（入度等于1的节点）
7+
然后先将叶子节点入队列
8+
剪掉这些叶子节点的后续节点，同时将其中入度为1的节点入队列
9+
当叶子节点少于三个的时候,就是最后的结果
10+
11+
*/
12+
funcfindMinHeightTrees(nint,edges [][]int) []int {
13+
ifn==1 {
14+
return []int{0}
15+
}
16+
17+
m:=make(map[int][]int)
18+
//建立对应关系
19+
for_,v:=rangeedges {
20+
if_,ok:=m[v[0]];ok {
21+
m[v[0]]=append(m[v[0]],v[1])
22+
}else {
23+
m[v[0]]= []int{v[1]}
24+
}
25+
if_,ok:=m[v[1]];ok {
26+
m[v[1]]=append(m[v[1]],v[0])
27+
}else {
28+
m[v[1]]= []int{v[0]}
29+
}
30+
}
31+
leaves:= []int{}
32+
//找到所有的叶子节点
33+
fork,v:=rangem {
34+
iflen(v)==1 {
35+
leaves=append(leaves,k)
36+
}
37+
}
38+
forn>2 {
39+
n-=len(leaves)
40+
one:= []int{}
41+
for_,v:=rangeleaves {
42+
next:=m[v]
43+
for_,val:=rangenext {
44+
m[v]=del(m[v],val)
45+
m[val]=del(m[val],v)
46+
iflen(m[val])==1 {
47+
one=append(one,val)
48+
}
49+
}
50+
}
51+
leaves=one
52+
}
53+
returnleaves
54+
}
55+
56+
funcdel(s []int,vint) []int {
57+
forkey,val:=ranges {
58+
ifval==v {
59+
s=append(s[:key],s[key+1:]...)
60+
}
61+
}
62+
returns
63+
}

‎328. Odd Even Linked List.go

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
package main
2+
3+
typeListNodestruct {
4+
Valint
5+
Next*ListNode
6+
}
7+
8+
funcoddEvenList(head*ListNode)*ListNode {
9+
ifhead==nil {
10+
returnnil
11+
}
12+
odd,even:=head,head.Next
13+
evenHead:=even
14+
foreven!=nil&&even.Next!=nil {
15+
odd.Next=even.Next
16+
odd=odd.Next
17+
even.Next=odd.Next
18+
even=even.Next
19+
}
20+
odd.Next=evenHead
21+
returnhead
22+
}
Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package main
2+
3+
import"math"
4+
5+
funcincreasingTriplet(nums []int)bool {
6+
returnhelper(nums,3)
7+
}
8+
9+
funchelper(nums []int,kint)bool {
10+
iflen(nums)<k {
11+
returnfalse
12+
}
13+
dp:=make([]int,k+1)
14+
dp[0]=math.MinInt32
15+
dp[1]=nums[0]
16+
maxLen:=1
17+
fori:=1;i<len(nums);i++ {
18+
forj:=maxLen;j>=0;j-- {
19+
ifnums[i]>dp[j] {
20+
ifj==maxLen {
21+
maxLen++
22+
ifmaxLen==k {
23+
returntrue
24+
}
25+
}
26+
dp[j+1]=nums[i]
27+
break
28+
}
29+
}
30+
}
31+
returnfalse
32+
}

0 commit comments

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