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

Commitf0fb8d1

Browse files
committed
add new files
1 parent9bef0a0 commitf0fb8d1

6 files changed

+214
-0
lines changed

‎337. House Robber III.go

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
package main
2+
3+
typeTreeNodestruct {
4+
Valint
5+
Left*TreeNode
6+
Right*TreeNode
7+
}
8+
9+
/**
10+
递归
11+
分两种情况，如果包括root，那么接下来就是root.left.left，root.left.right
12+
如果不包括root，接下来就是root.left,root.right
13+
取两种情况的最大值
14+
*/
15+
funcrob(root*TreeNode)int {
16+
ifroot==nil {
17+
return0
18+
}
19+
val:=0
20+
ifroot.Left!=nil {
21+
val+=rob(root.Left.Left)+rob(root.Left.Right)
22+
}
23+
ifroot.Right!=nil {
24+
val+=rob(root.Right.Right)+rob(root.Right.Left)
25+
}
26+
returnmax(val+root.Val,rob(root.Left)+rob(root.Right))
27+
}
28+
funcmax(x,yint)int {
29+
ifx>y {
30+
returnx
31+
}
32+
returny
33+
}

‎343. Integer Break.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+
dp算法：
5+
令dp[n]为n对应的最大积。
6+
那么递推方程就是：dp[n]=max(i*dp[n-i],i*(n-i))(其中i从1到n-1)。
7+
边界:dp[2]=1;
8+
*/
9+
funcintegerBreak(nint)int {
10+
dp:=make([]int,n+1)
11+
dp[1]=1
12+
dp[2]=1
13+
fori:=3;i<=n;i++ {
14+
dp[i]=-1
15+
forj:=1;j<i;j++ {
16+
dp[i]=max(dp[i-j]*j,max(dp[i],j*(i-j)))
17+
}
18+
}
19+
returndp[n]
20+
}
21+
22+
funcmax(x,yint)int {
23+
ifx>y {
24+
returnx
25+
}
26+
returny
27+
}
Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
package main
2+
3+
/**
4+
二分查找
5+
*/
6+
funckthSmallest(matrix [][]int,kint)int {
7+
iflen(matrix)==0 {
8+
return0
9+
}
10+
m:=len(matrix)
11+
low,high:=matrix[0][0],matrix[m-1][m-1]
12+
forlow<high {
13+
mid:= (low+high)/2
14+
cc:=helper(matrix,mid)
15+
ifcc<k {
16+
low=mid+1
17+
}else {
18+
high=mid
19+
}
20+
}
21+
returnlow
22+
}
23+
funchelper(matrix [][]int,targetint)int {
24+
c:=0
25+
i,j:=len(matrix)-1,0
26+
fori>=0&&j<=len(matrix)-1 {
27+
ifmatrix[i][j]<=target {
28+
j++
29+
c+=i+1
30+
}else {
31+
i--
32+
}
33+
}
34+
returnc
35+
}

‎412. Fizz Buzz.go

Lines changed: 19 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,19 @@
1+
package main
2+
3+
import"strconv"
4+
5+
funcfizzBuzz(nint) []string {
6+
ret:= []string{}
7+
fori:=1;i<=n;i++ {
8+
ifi%3==0&&i%5==0 {
9+
ret=append(ret,"FizzBuzz")
10+
}elseifi%3==0 {
11+
ret=append(ret,"Fizz")
12+
}elseifi%5==0 {
13+
ret=append(ret,"Buzz")
14+
}else {
15+
ret=append(ret,strconv.Itoa(i))
16+
}
17+
}
18+
returnret
19+
}
Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
package main
2+
3+
/**
4+
定义start和end两个标记，中间的内容即是窗口，计算窗口内所有字母出现的次数，因为全是大写字母，所以可以用一个26位的数组来记录窗口内每个字母出现的次数。
5+
找到窗口内出现最多的次数，加上允许替换的字母数k，看是否超过窗口宽度，如果超过了，说明窗口还可以更长， 也就是说窗口内重复的字母的长度可以更长，就将end右移一位，形成新的窗口，然后继续重复上面的步骤。如果没超过，说明能构成的最长的重复字母长度已经到顶了，这时应该将start右移一位，来寻找新的可能的更长重复字母长度。
6+
每次计算重复字母长度时，当出现更长的可能时，都更新最终的结果。
7+
*/
8+
9+
funccharacterReplacement(sstring,kint)int {
10+
iflen(s)==0 {
11+
return0
12+
}
13+
str:= []byte(s)
14+
start,end:=0,0
15+
ret:=0
16+
c:=make([]int,26)
17+
c[str[0]-'A']++
18+
forlen(str)>end {
19+
maxc:=0
20+
fori:=0;i<26;i++ {
21+
ifc[i]>maxc {
22+
maxc=c[i]
23+
}
24+
}
25+
ifmaxc+k>end-start {
26+
end++
27+
ifend<len(str) {
28+
c[str[end]-'A']++
29+
}
30+
}else {
31+
c[str[start]-'A']--
32+
start++
33+
}
34+
ifmaxc+k>ret {
35+
ifmaxc+k<=len(str) {
36+
ret=maxc+k
37+
}else {
38+
ret=len(str)
39+
}
40+
}
41+
}
42+
returnret
43+
}

‎435. Non-overlapping Intervals.go

Lines changed: 57 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,57 @@
1+
package main
2+
3+
import"sort"
4+
5+
/**
6+
将区间排序，因为我要们除掉的区间尽可能小，所以我尽量保存小区间，去除大区间，所以我们以右区间排序，从小到大，并且右区间相等时，按左区间从小到大排序，然后我们就维护左区间边界，当左区间边界小于下一个的区间的右边界的时候，就将左区间边界扩张为一个区间的左边界，当左区间边界大于下一个的区间的右边界的时候，我们要比较左区间边界与下一个区间的左边界大小，取最小的，这样我们可以容纳更多的区间而不重叠。
7+
*/
8+
9+
typeIntervalstruct {
10+
Startint
11+
Endint
12+
}
13+
14+
typeinSlice []Interval
15+
16+
funcnewInSlice(a []Interval)inSlice {
17+
b:=inSlice{}
18+
for_,v:=rangea {
19+
b=append(b,v)
20+
}
21+
returnb
22+
}
23+
24+
func (thisinSlice)Len()int {
25+
returnlen(this)
26+
}
27+
func (thisinSlice)Less(i,jint)bool {
28+
ifthis[i].Start==this[j].Start {
29+
returnthis[i].End<this[j].End
30+
}else {
31+
returnthis[i].Start<this[j].Start
32+
}
33+
}
34+
func (thisinSlice)Swap(i,jint) {
35+
this[i],this[j]=this[j],this[i]
36+
}
37+
38+
funceraseOverlapIntervals(intervals []Interval)int {
39+
iflen(intervals)<2 {
40+
return0
41+
}
42+
in:=newInSlice(intervals)
43+
sort.Sort(in)
44+
left:=in[0].End
45+
cnt:=1
46+
fori:=1;i<len(in);i++ {
47+
ifleft<=in[i].Start {
48+
cnt++
49+
left=in[i].End
50+
}else {
51+
ifleft>in[i].End {
52+
left=in[i].End
53+
}
54+
}
55+
}
56+
returnlen(in)-cnt
57+
}

0 commit comments

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