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

Commit8a6920f

Browse files
committed
add new files
1 parente198f8f commit8a6920f

8 files changed

+161
-2
lines changed

‎450. Delete Node in a BST.go

Lines changed: 34 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,34 @@
1+
package main
2+
3+
typeTreeNodestruct {
4+
Valint
5+
Left*TreeNode
6+
Right*TreeNode
7+
}
8+
9+
funcdeleteNode(root*TreeNode,keyint)*TreeNode {
10+
ifroot==nil {
11+
returnnil
12+
}
13+
ifkey<root.Val {//如果key小于root，从左子树删除
14+
root.Left=deleteNode(root.Left,key)
15+
}elseifkey>root.Val {//如果key大于root，从右子树删除
16+
root.Right=deleteNode(root.Right,key)
17+
}else {//删除root节点
18+
ifroot.Left==nil {
19+
returnroot.Right
20+
}
21+
ifroot.Right==nil {
22+
returnroot.Left
23+
}
24+
root.Val=findMin(root.Right)
25+
root.Right=deleteNode(root.Right,root.Val)
26+
}
27+
returnroot
28+
}
29+
funcfindMin(root*TreeNode)int {
30+
forroot.Left!=nil {
31+
root=root.Left
32+
}
33+
returnroot.Val
34+
}

‎459. Repeated Substring Pattern.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+
1. 用两个s 首尾相连得到一个新的字符串ss ;
6+
2. 去掉ss 的首尾两个字符；
7+
3. 如果在剩下来的字符串中能找到s 那么返回True，否则False
8+
if len(s) == 0 {
9+
return false
10+
}
11+
ss := (s + s)[1:(len(s)*2)-1]
12+
return strings.Contains(ss, s)
13+
这里用的解法：
14+
重复子串长度最长为len/2，直接每次选择一个可以被整除的较小的数，截取开头的那几个字符，然后重复到原长度验证就好。
15+
*/
16+
funcrepeatedSubstringPattern(sstring)bool {
17+
str:= []byte(s)
18+
iflen(str)<=1 {
19+
returnfalse
20+
}
21+
max:=len(str)/2
22+
fori:=1;i<=max;i++ {
23+
j:=i
24+
idx:=0
25+
iflen(str)%i>0 {
26+
continue
27+
}
28+
for ;j<len(str);j++ {
29+
ifstr[j]!=str[idx] {
30+
break
31+
}
32+
idx++
33+
ifidx>=i {
34+
idx=0
35+
}
36+
}
37+
38+
ifj==len(str) {
39+
returntrue
40+
}
41+
}
42+
returnfalse
43+
}

‎463. Island Perimeter.go

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

3+
/**
4+
思路就是每一个为1的点，看它的上下左右是否也为1，若为1则有一边重复，最后加的时候要减去重复的边。
5+
*/
6+
37
funcislandPerimeter(grid [][]int)int {
48
row:=len(grid)
59
col:=len(grid[0])

‎475. Heaters.go

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,10 @@ import (
55
"sort"
66
)
77

8+
/**
9+
用二分查找。对heaters进行sort，然后得到某个house的相对位置。再计算左右的距离。
10+
11+
*/
812
funcfindRadius(houses []int,heaters []int)int {
913
sort.Ints(heaters)
1014
ret:=-1

‎494. Target Sum.go

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

3+
/**
4+
假设原数组为S，目标值为target，那么原数组必然可以分成两个部分，一个部分里面的元素前面需要加-，即运算的时候应该是做减法，另一个部分里面的元素前面需要加+，即运算的时候应该是做加法；
5+
我们将做加法部分的数组记为P，做减法部分的数组记为N，举个例子，例如S = {1，2，3，4，5}，target = 3，那么有一种可以是1-2+3-4+5，即P = {1，3，5}，N = {2，4}；
6+
于是我们可以知道：target = sum(P) - sum(N)；
7+
那么sum(P) + sum(N) + sum(P) - sum(N) = sum(S) + target = 2sum(P)；
8+
那么sum(P) = [target + sum(S)] / 2；
9+
根据以上的推导，我们可以得到这样的结论：我们需要找到这样一个子序列P，使得子序列之和等于原序列之和与目标值的和的一半，我们需要找到这样子序列的数目。
10+
显而易见，如果原序列之和与目标值的和为奇数，肯定不存在这样的子序列，如果原序列之和小于目标值，也肯定不存在（因为这种情况下，即使我们填的都是+，让所有元素相加都小于目标值，肯定不存在满足条件的解决方案）。
11+
排除了以上的两种特殊情况之后，我们接下来研究的就是在原数组中找到之和符合条件的子序列个数，非常明显DP的方法。
12+
13+
*/
314
funcfindTargetSumWays(nums []int,Sint)int {
415
S=myabs(S)
516
sum:=0

‎500. Keyboard Row.go

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
package main
2+
3+
/**
4+
先把每一行用map保存，然后查找每个词
5+
*/
6+
funcfindWords(words []string) []string {
7+
str:= []string{"QWERTYUIOPqwertyuiop","ASDFGHJKLasdfghjkl","ZXCVBNMzxcvbnm"}
8+
dic:=make(map[byte]int)
9+
fori:=0;i<len(str);i++ {
10+
forj:=0;j<len(str[i]);j++ {
11+
dic[str[i][j]]=i
12+
}
13+
}
14+
ret:=make([]string,0,len(words))
15+
for_,word:=rangewords {
16+
flag:=true
17+
fori:=0;flag&&i<len(word)-1;i++ {
18+
ifdic[word[i]]!=dic[word[i+1]] {
19+
flag=false
20+
}
21+
}
22+
ifflag {
23+
ret=append(ret,word)
24+
}
25+
}
26+
returnret
27+
}
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+
递归把节点的数量保存在map中,同时记录最大的出现次数
11+
*/
12+
13+
varmodeint
14+
15+
funcfindMode(root*TreeNode) []int {
16+
mode=0
17+
dic:=make(map[int]int)
18+
ret:= []int{}
19+
helper(root,dic)
20+
fork,v:=rangedic {
21+
ifv==mode {
22+
ret=append(ret,k)
23+
}
24+
}
25+
returnret
26+
}
27+
28+
funchelper(root*TreeNode,dicmap[int]int) {
29+
ifroot==nil {
30+
return
31+
}
32+
dic[root.Val]++
33+
ifdic[root.Val]>mode {
34+
mode=dic[root.Val]
35+
}
36+
helper(root.Left,dic)
37+
helper(root.Right,dic)
38+
}

‎515. Find Largest Value in Each Tree Row.go

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

3-
import"fmt"
4-
53
typeTreeNodestruct {
64
Valint
75
Left*TreeNode

0 commit comments

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