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

Commitfa147a0

Browse files
committed
add new files
1 parent45b43c8 commitfa147a0

6 files changed

+176
-0
lines changed

‎115. Distinct Subsequences.go

Lines changed: 31 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,31 @@
1+
package main
2+
3+
/**
4+
dp
5+
dp[i][j]表示构成i长度的t，用到j长度的s，结果等于种类
6+
转移方程：
7+
如果t[i]==s[j],dp[i][j]=dp[i-1][j-1]+dp[i][j-1]
8+
否则：dp[i][j]=dp[i][j-1]
9+
初始值：
10+
dp[0][*]=1表示构成0长度的t，有一种方法
11+
*/
12+
funcnumDistinct(sstring,tstring)int {
13+
ls,lt:=len(s),len(t)
14+
dp:=make([][]int,lt+1)
15+
fork:=rangedp {
16+
dp[k]=make([]int,ls+1)
17+
}
18+
fork:=rangedp[0] {
19+
dp[0][k]=1
20+
}
21+
fori:=1;i<=lt;i++ {
22+
forj:=1;j<=ls;j++ {
23+
ift[i-1]==s[j-1] {
24+
dp[i][j]=dp[i][j-1]+dp[i-1][j-1]
25+
}else {
26+
dp[i][j]=dp[i][j-1]
27+
}
28+
}
29+
}
30+
returndp[lt][ls]
31+
}

‎416. Partition Equal Subset Sum.go

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

33
/**
4+
dp
45
dp[i]:是否可以得到和i
56
dp[i+v]=true,如果dp[i]==true，如果可以得到i，那么加上v就得到了i+v，所以dp[i+v]=true
67
dp[0] =true,得到和0是可以的
8+
循环处理获得dp，期间要判断是否已经得到了结果
79
*/
810
funccanPartition(nums []int)bool {
911
sum:=0
Lines changed: 44 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
package main
2+
3+
/**
4+
dp:方程表示从i到j的长度中，回文子串的长度
5+
Base case:
6+
a ->dp[i][i]=1
7+
8+
case 1:s[i]==s[j]
9+
a*****a ->dp[i][j]=dp[i+1][j-1]+2
10+
11+
case 2:s[i]!=s[j]
12+
ab****b dp[i][j]=dp[i+1][i]
13+
a****ab dp[i][j]=dp[i][j-1]
14+
15+
*/
16+
funclongestPalindromeSubseq(sstring)int {
17+
n:=len(s)
18+
dp:=make([][]int,n)
19+
fork:=rangedp {
20+
dp[k]=make([]int,n)
21+
}
22+
forl:=1;l<=n;l++ {
23+
fori:=0;i<=n-l;i++ {
24+
j:=i+l-1
25+
ifi==j {
26+
dp[i][j]=1
27+
continue
28+
}
29+
ifs[i]==s[j] {
30+
dp[i][j]=dp[i+1][j-1]+2
31+
}else {
32+
dp[i][j]=mymax(dp[i+1][j],dp[i][j-1])
33+
}
34+
}
35+
}
36+
returndp[0][n-1]
37+
}
38+
39+
funcmymax(x,yint)int {
40+
ifx>y {
41+
returnx
42+
}
43+
returny
44+
}

‎560. Subarray Sum Equals K.go

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,40 @@
1+
package main
2+
3+
/**
4+
O(n^2)
5+
*/
6+
funcsubarraySum(nums []int,kint)int {
7+
l:=len(nums)
8+
sums:=make([]int,l+1)
9+
fori:=1;i<=l;i++ {
10+
sums[i]=sums[i-1]+nums[i-1]
11+
}
12+
ans:=0
13+
fori:=0;i<l;i++ {
14+
forj:=i;i<l;j++ {
15+
if (sums[j+1]-sums[i])==k {
16+
ans++
17+
}
18+
}
19+
}
20+
returnans
21+
}
22+
23+
/**
24+
prefix sum
25+
O(n)
26+
*/
27+
funcsubarraySum1(nums []int,kint)int {
28+
iflen(nums)==0 {
29+
return0
30+
}
31+
m:=make(map[int]int)
32+
m[0]=1
33+
ans,sum:=0,0
34+
for_,num:=rangenums {
35+
sum+=num
36+
ans+=m[sum-k]
37+
m[sum]++
38+
}
39+
returnans
40+
}

‎78. Subsets.go

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
package main
2+
3+
/**
4+
combination:
5+
dfs方法，注意中间结果一定要copy到新的变量中，不然会得到空值
6+
*/
7+
varans [][]int
8+
9+
funcsubsets(nums []int) [][]int {
10+
ans= [][]int{}
11+
cur:= []int{}
12+
fori:=0;i<=len(nums);i++ {
13+
dfs(nums,i,0,cur)
14+
}
15+
returnans
16+
}
17+
funcdfs(nums []int,n,sint,cur []int) {
18+
iflen(cur)==n {
19+
tmp:=make([]int,n)
20+
copy(tmp,cur)
21+
ans=append(ans,tmp)
22+
return
23+
}
24+
fori:=s;i<len(nums);i++ {
25+
cur=append(cur,nums[i])
26+
dfs(nums,n,i+1,cur)
27+
cur=cur[:len(cur)-1]
28+
}
29+
}

‎823. Binary Trees With Factors.go

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
package main
2+
3+
import"sort"
4+
5+
/**
6+
dp
7+
从最小的数开始
8+
dp[c] = sum{dp[a]*dp[b]};c=a*b;a,b,c in A
9+
ans = sum(dp[c])
10+
*/
11+
funcnumFactoredBinaryTrees(A []int)int {
12+
mod:=1000000007
13+
sort.Ints(A)
14+
dp:=make(map[int]int)
15+
fori:=0;i<len(A);i++ {
16+
dp[A[i]]=1
17+
forj:=0;j<i;j++ {
18+
ifA[i]%A[j]==0 {
19+
if_,ok:=dp[A[i]/A[j]];ok {
20+
dp[A[i]]+= (dp[A[j]]*dp[A[i]/A[j]])%mod
21+
}
22+
}
23+
}
24+
}
25+
ans:=0
26+
for_,v:=rangedp {
27+
ans+=v
28+
}
29+
returnans%mod
30+
}

0 commit comments

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