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

Commita4afee5

Browse files
committed
add new files
1 parent1015a0c commita4afee5

6 files changed

+202
-2
lines changed

‎160. Intersection of Two Linked Lists.go

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -20,11 +20,11 @@ func getIntersectionNode(headA, headB *ListNode) *ListNode {
2020
a,b=headA,headB
2121
forla<lb {
2222
b=b.Next
23-
b--
23+
lb--
2424
}
2525
forlb<la {
2626
a=a.Next
27-
a--
27+
la--
2828
}
2929
fora!=b {
3030
a=a.Next

‎200. Number of Islands.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+
dfs深度优先搜索
5+
*/
6+
funcnumIslands(grid [][]byte)int {
7+
iflen(grid)==0 {
8+
return0
9+
}
10+
ret:=0
11+
fori:=0;i<len(grid);i++ {
12+
forj:=0;j<len(grid[0]);j++ {
13+
ifgrid[i][j]=='1' {
14+
helper(grid,i,j)
15+
ret++
16+
}
17+
}
18+
}
19+
returnret
20+
}
21+
22+
funchelper(grid [][]byte,i,jint) {
23+
ifi<0||j<0||i>=len(grid)||j>=len(grid[0]) {
24+
return
25+
}
26+
ifgrid[i][j]=='1' {
27+
grid[i][j]='0'
28+
helper(grid,i-1,j)
29+
helper(grid,i,j-1)
30+
helper(grid,i+1,j)
31+
helper(grid,i,j+1)
32+
}
33+
}

‎202. Happy Number.go

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
package main
2+
3+
funcisHappy(nint)bool {
4+
returnisOne(n)
5+
}
6+
funcgetSum(nint)int {
7+
ifn/10==0 {
8+
returnn*n
9+
}
10+
return (n%10)*(n%10)+getSum(n/10)
11+
}
12+
funcisOne(nint)bool {
13+
a:=getSum(n)
14+
ifa==1 {
15+
returntrue
16+
}elseifa==4 {
17+
returnfalse
18+
}else {
19+
returnisOne(a)
20+
}
21+
}

‎207. Course Schedule.go

Lines changed: 50 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,50 @@
1+
package main
2+
3+
/**
4+
DAG，顾名思义，如果一个有向图中从任意点出发都不能回到该点的话，这张图就是一个有向无环图
5+
判断一个有向图是否有环，有两个算法：
6+
7+
拓扑排序
8+
即找出该图的一个线性序列，使得需要事先完成的事件总排在之后才能完成的事件之前。如果能找到这样一个线性序列，则该图是一个有向无环图
9+
DFS
10+
遍历图中的所有点，从i点出发开始DFS，如果在DFS的不断深入过程中又回到了该点，则说明图中存在回路。
11+
*/
12+
13+
funccanFinish(numCoursesint,prerequisites [][]int)bool {
14+
m:=make(map[int][]int)
15+
res:=make([]int,numCourses)
16+
for_,p:=rangeprerequisites {
17+
v,ok:=m[p[0]]
18+
if!ok {
19+
m[p[0]]= []int{p[1]}
20+
}else {
21+
m[p[0]]=append(v,p[1])
22+
}
23+
}
24+
fori:=0;i<numCourses;i++ {
25+
ifhelper(i,res,m)==false {
26+
returnfalse
27+
}
28+
}
29+
returntrue
30+
}
31+
funchelper(idxint,res []int,mmap[int][]int)bool {
32+
ifres[idx]==1 {
33+
returntrue
34+
}
35+
ifres[idx]==2 {
36+
returnfalse
37+
}
38+
v,ok:=m[idx]
39+
if!ok {
40+
returntrue
41+
}
42+
res[idx]=2
43+
fori:=0;i<len(v);i++ {
44+
ifhelper(v[i],res,m)==false {
45+
returnfalse
46+
}
47+
}
48+
res[idx]=1
49+
returntrue
50+
}

‎210. Course Schedule II.go

Lines changed: 53 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
package main
2+
3+
/**
4+
5+
设置一个队列
6+
第一步现将所有入度为0的节点保存在队列中
7+
然后，出队列，并将该节点的后续节点的入度减一
8+
如果后续节点的入度变成0，入队列
9+
最后将结果逆序
10+
*/
11+
funcfindOrder(numCoursesint,prerequisites [][]int) []int {
12+
ifnumCourses==0 {
13+
return []int{}
14+
}
15+
m:=make([][]int,numCourses)
16+
in:=make([]int,numCourses)
17+
q:= []int{}
18+
order:= []int{}
19+
for_,p:=rangeprerequisites {
20+
m[p[0]]=append(m[p[0]],p[1])//记录所有的对应关系
21+
in[p[1]]++//记录入度
22+
}
23+
//把所有入度为0的节点，入队列
24+
fori:=0;i<numCourses;i++ {
25+
ifin[i]==0 {
26+
q=append(q,i)
27+
}
28+
}
29+
//循环处理，一边出队列，一边入队列
30+
forlen(q)!=0 {
31+
cur:=q[0]
32+
q=q[1:]//出队列
33+
order=append(order,cur)
34+
//处理该节点的后续节点
35+
fori:=0;i<len(m[cur]);i++ {
36+
dep:=m[cur][i]
37+
in[dep]--//后续节点-1
38+
ifin[dep]==0 {
39+
//如果入度变成了0，入队列
40+
q=append(q,dep)
41+
}
42+
}
43+
}
44+
//如果还有节点没有处理，则不能完成课程
45+
iflen(order)!=numCourses {
46+
return []int{}
47+
}
48+
//逆序
49+
fori,j:=0,len(order)-1;i<j;i,j=i+1,j-1 {
50+
order[i],order[j]=order[j],order[i]
51+
}
52+
returnorder
53+
}

‎213. House Robber II.go

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package main
2+
3+
/**
4+
分成两种情况考虑:
5+
打劫第一个house
6+
不打劫第一个house
7+
8+
如果打劫第一个house，就不能打劫最后一个house
9+
否则就可以打劫最后一个
10+
最后取这两种情况的最大值
11+
*/
12+
funcrob(nums []int)int {
13+
l:=len(nums)
14+
ifl==0 {
15+
return0
16+
}
17+
ifl==1 {
18+
returnnums[0]
19+
}
20+
//dp1表示从第一个house开始
21+
//dp2表示从第二个house开始
22+
dp1,dp2:=make([]int,l),make([]int,l)
23+
dp1[0]=nums[0]
24+
dp1[1]=max(dp1[0],nums[1])
25+
dp2[0]=0
26+
dp2[1]=max(dp2[0],nums[1])
27+
fori:=2;i<l;i++ {
28+
ifi<l-1 {
29+
dp1[i]=max(dp1[i-1],dp1[i-2]+nums[i])
30+
}else {//最后一个house
31+
dp1[i]=dp1[i-1]//不能抢
32+
}
33+
dp2[i]=max(dp2[i-1],dp2[i-2]+nums[i])
34+
}
35+
returnmax(dp1[l-1],dp2[l-1])
36+
}
37+
38+
funcmax(x,yint)int {
39+
ifx>y {
40+
returnx
41+
}
42+
returny
43+
}

0 commit comments

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