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

Commit782c3f4

Browse files
committed
add new files
1 parent455af2b commit782c3f4

14 files changed

+163
-6
lines changed

‎1. Two Sum.go

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

3+
/**
4+
用hash保存另一个数的值，遍历的同时判断是否存在
5+
*/
36
functwoSum(nums []int,targetint) []int {
47
m:=make(map[int]int)
58
fori:=0;i<len(nums);i++ {

‎14. Longest Common Prefix.go

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -8,6 +8,7 @@ func longestCommonPrefix(strs []string) string {
88
}
99
minLen:=math.MaxInt32
1010
minStr:=""
11+
//先找到最短的字符串
1112
for_,v:=rangestrs {
1213
l:=len(v)
1314
ifl<minLen {

‎15. 3Sum.go

Lines changed: 4 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3,14 +3,17 @@ package main
33
import"sort"
44

55
functhreeSum(nums []int) [][]int {
6+
//先排序
67
sort.Ints(nums)
8+
79
res:=make([][]int,0)
810
f:=func(nums []int,beginint,endint,targetint) {
9-
forbegin<end {
11+
forbegin<end {//从两端向中间遍历
1012
ifnums[begin]+nums[end]+target==0 {
1113
r:=make([]int,0)
1214
r=append(r,nums[begin],nums[end],target)
1315
res=append(res,r)
16+
//遇到相等的，就快进
1417
forbegin<end&&nums[begin]==nums[begin+1] {
1518
begin++
1619
}

‎17. Letter Combinations of a Phone Number.go

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

3+
/*
4+
回溯算法
5+
*/
36
funcletterCombinations(digitsstring) []string {
47
table:= []string{"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"}
58
ret:= []string{}

‎19. Remove Nth Node From End of List.go

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@ type ListNode struct {
66
}
77

88
/**
9-
* 快慢指针
9+
* 快慢指针,快指针先前进n步，然后两个指针一起前进，当快指针走到末尾的时候，慢指针所在的位置，就是目标位置
1010
*/
1111
funcremoveNthFromEnd(head*ListNode,nint)*ListNode {
1212
cur:=head

‎2. Add Two Numbers.go

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,13 +5,18 @@ type ListNode struct {
55
Next*ListNode
66
}
77

8+
/**
9+
注意的问题：
10+
1.进位
11+
2.两个list的长度不一定相等
12+
*/
813
funcaddTwoNumbers(l1*ListNode,l2*ListNode)*ListNode {
914
result:=&ListNode{0,nil}
1015
cursor:=result
1116
leftBit,rightBit,carryBit:=0,0,0
1217

1318
forl1!=nil||l2!=nil||carryBit>0 {
14-
ifl1!=nil {//考虑5+5的情况
19+
ifl1!=nil {
1520
leftBit=l1.Val
1621
l1=l1.Next
1722
}else {
@@ -24,7 +29,7 @@ func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
2429
}else {
2530
rightBit=0
2631
}
27-
32+
//考虑有进位的情况
2833
cursor.Val= (leftBit+rightBit+carryBit)%10
2934
carryBit= (leftBit+rightBit+carryBit)/10
3035

‎21. Merge Two Sorted Lists.go

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,10 @@ type ListNode struct {
55
Next*ListNode
66
}
77

8+
/**
9+
递归操作
10+
当某一个为空的时候，退出
11+
*/
812
funcmergeTwoLists(l1*ListNode,l2*ListNode)*ListNode {
913
ifl1==nil {
1014
returnl2

‎3. Longest Substring Without Repeating Characters.go

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

3+
/**
4+
滑动窗口，如果在hash表里找到了当前的字符，重新设置窗口的起点位置
5+
*/
36
funclengthOfLongestSubstring(sstring)int {
47
m:=make(map[rune]int)
58
start,max:=-1,0
69

710
fork,v:=ranges {
8-
iflast,ok:=m[v];ok&&last>start {
11+
iflast,ok:=m[v];ok&&last>start {//如果发现重复字符
912
start=last
1013
}
1114
m[v]=k
12-
ifk-start>max {
15+
ifk-start>max {//保存最大值
1316
max=k-start
1417
}
1518
}
Lines changed: 38 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,38 @@
1+
package main
2+
3+
typeTreeNodestruct {
4+
Valint
5+
Left*TreeNode
6+
Right*TreeNode
7+
}
8+
9+
/**
10+
用队列保存节点,一层一层的处理
11+
从队列里取出节点的同时，判断左右子树是否为空，不为空则入队列
12+
*/
13+
14+
funcaverageOfLevels1(root*TreeNode) []float64 {
15+
ret:= []float64{}
16+
ifroot==nil {
17+
returnret
18+
}
19+
cnt,sum:=0,0
20+
q:= []*TreeNode{root}
21+
forlen(q)>0 {
22+
cnt=len(q)
23+
sum=0
24+
fori:=0;i<cnt;i++ {
25+
tmp:=q[0]
26+
q=q[1:]
27+
iftmp.Left!=nil {
28+
q=append(q,tmp.Left)
29+
}
30+
iftmp.Right!=nil {
31+
q=append(q,tmp.Right)
32+
}
33+
sum+=tmp.Val
34+
}
35+
ret=append(ret,float64(sum)/float64(cnt))
36+
}
37+
returnret
38+
}

‎643. Maximum Average Subarray I.go

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package main
2+
3+
/**
4+
先计算前k个的sum，然后一直向右滑动，统计最大值
5+
*/
6+
funcfindMaxAverage(nums []int,kint)float64 {
7+
sum:=0
8+
fori:=0;i<k;i++ {
9+
sum+=nums[i]
10+
}
11+
m:=sum
12+
fori:=k;i<len(nums);i++ {
13+
sum=sum-nums[i-k]+nums[i]
14+
ifsum>m {
15+
m=sum
16+
}
17+
}
18+
returnfloat64(m)/float64(k)
19+
}

‎645. Set Mismatch.go

Lines changed: 46 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,46 @@
1+
package main
2+
3+
/**
4+
用hash表判断重复项
5+
用累加和减去不重复项之和，等于丢失的数字
6+
*/
7+
//TODO 速度待优化
8+
funcfindErrorNums(nums []int) []int {
9+
10+
m:=make(map[int]int)
11+
sum:=0
12+
ret:=make([]int,2)
13+
for_,v:=rangenums {
14+
if_,ok:=m[v];ok {
15+
ret[0]=v
16+
}else {
17+
m[v]=1
18+
sum+=v
19+
}
20+
}
21+
l:=len(nums)
22+
ret[1]=l*(1+l)/2-sum
23+
returnret
24+
}
25+
26+
/**
27+
用一个新数组保存出现的次数，然后找出出现两次的和出现0次的
28+
速度比上面快很多
29+
*/
30+
funcfindErrorNums1(nums []int) []int {
31+
l:=len(nums)
32+
m:=make([]int,l)
33+
ret:=make([]int,2)
34+
fori:=0;i<l;i++ {
35+
m[nums[i]-1]++
36+
}
37+
fork,v:=rangem {
38+
ifv==2 {
39+
ret[0]=k+1
40+
}
41+
ifv==0 {
42+
ret[1]=k+1
43+
}
44+
}
45+
returnret
46+
}

‎653. Two Sum IV - Input is a BST.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+
遍历树，用hash保存节点值，递归判断
5+
类似普通的2sum
6+
*/
7+
varmmap[int]bool
8+
9+
funchelper(root*TreeNode,kint)bool {
10+
ifroot==nil {
11+
returnfalse
12+
}
13+
if_,ok:=m[k-root.Val];ok {
14+
returntrue
15+
}
16+
m[root.Val]=true
17+
returnhelper(root.Left,k)||helper(root.Right,k)
18+
}
19+
funcfindTarget(root*TreeNode,kint)bool {
20+
m=make(map[int]bool)
21+
returnhelper(root,k)
22+
}
23+
24+
/**
25+
另外，也可以利用bst的性质，中序遍历成一个有序数组，然后再做2sum
26+
*/

‎7. Reverse Integer.go

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2,6 +2,10 @@ package main
22

33
import"math"
44

5+
/**
6+
循环取余数
7+
需要注意越界
8+
*/
59
funcreverse(xint)int {
610

711
res:=0

‎9. Palindrome Number.go

Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,11 +4,13 @@ func isPalindrome(x int) bool {
44
ifx<0 {
55
returnfalse
66
}
7+
//排除以0结尾的情况
78
ifx!=0&&x%10==0 {
89
returnfalse
910
}
1011
y:=0
1112
c:=x
13+
//把x反转，判断是否和原来的x相等
1214
forx!=0 {
1315
y=y*10+x%10
1416
x/=10

0 commit comments

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