Commita293e17

committed

add new files

1 parentad9fb1e commita293e17Copy full SHA for a293e17

File tree

+156

-0

lines changed

+156

-0

lines changed

Lines changed: 40 additions & 0 deletions

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,33 @@`
	`1`	`+package main`
	`2`	`+`
	`3`	`+/**`
	`4`	`+DP`
	`5`	`+dp[i][j]表示原数组中从i到j的这么多数中，按照游戏规则，某个玩家所能获得的最大分数。`
	`6`	`+假设这个分数此时属于palyer1，那么dp[i+1][j]或者dp[i][j-1]表示player2玩家所能获得的最大分数。因为对于player1来讲，他第一次选择要么是第i个数，要么是第j个数，所以对于player2来讲，就分两种情况取最大。`
	`7`	`+另外我们设从i到j的所有数的和是sum[i,j]，则可以得到递推公式：（动态规划最明显的标识）`
	`8`	`+dp[i][j]=max(sum[i+1][j]-dp[i+1][j]+nums[i], sum[i][j-1]-dp[i][j-1]+nums[j]) 。`
	`9`	`+化简一下：`
	`10`	`+dp[i][j]=max(sum[i][j]-dp[i+1][j], sum[i][j]-dp[i][j-1]) 。`
	`11`	`+*/`
	`12`	`+funcPredictTheWinner(nums []int)bool {`
	`13`	`+l:=len(nums)`
	`14`	`+dp:=make([][]int,l+1)`
	`15`	`+fork:=rangedp {`
	`16`	`+dp[k]=make([]int,l)`
	`17`	`+}`
	`18`	`+fori:=l;i>=0;i-- {`
	`19`	`+forj:=i+1;j<l;j++ {`
	`20`	`+a:=nums[i]-dp[i+1][j]`
	`21`	`+b:=nums[j]-dp[i][j-1]`
	`22`	`+dp[i][j]=max(a,b)`
	`23`	`+}`
	`24`	`+}`
	`25`	`+returndp[0][l-1]>=0`
	`26`	`+}`
	`27`	`+`
	`28`	`+funcmax(x,yint)int {`
	`29`	`+ifx>y {`
	`30`	`+returnx`
	`31`	`+}`
	`32`	`+returny`
	`33`	`+}`

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,26 @@`
	`1`	`+package main`
	`2`	`+`
	`3`	`+import"math"`
	`4`	`+`
	`5`	`+funcconstructRectangle(areaint) []int {`
	`6`	`+i:=int(math.Sqrt(float64(area)))`
	`7`	`+forarea%i!=0 {`
	`8`	`+i--`
	`9`	`+}`
	`10`	`+ret:=make([]int,2)`
	`11`	`+ret[0]=max(i,area/i)`
	`12`	`+ret[1]=min(i,area/i)`
	`13`	`+returnret`
	`14`	`+}`
	`15`	`+funcmax(x,yint)int {`
	`16`	`+ifx>y {`
	`17`	`+returnx`
	`18`	`+}`
	`19`	`+returny`
	`20`	`+}`
	`21`	`+funcmin(x,yint)int {`
	`22`	`+ifx>y {`
	`23`	`+returny`
	`24`	`+}`
	`25`	`+returnx`
	`26`	`+}`

Lines changed: 17 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,17 @@`
	`1`	`+package main`
	`2`	`+`
	`3`	`+/**`
	`4`	`+DP`
	`5`	`+*/`
	`6`	`+funcchange(amountint,coins []int)int {`
	`7`	`+dp:=make([]int,amount+1)`
	`8`	`+dp[0]=1`
	`9`	`+forj:=0;j<len(coins);j++ {`
	`10`	`+fori:=1;i<=amount;i++ {`
	`11`	`+ifi-coins[j]>=0 {`
	`12`	`+dp[i]+=dp[i-coins[j]]`
	`13`	`+}`
	`14`	`+}`
	`15`	`+}`
	`16`	`+returndp[amount]`
	`17`	`+}`

Lines changed: 40 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,40 @@`
	`1`	`+package main`
	`2`	`+`
	`3`	`+//TODO TLE`
	`4`	`+funcfindLUSlength(strs []string)int {`
	`5`	`+res,n:=-1,len(strs)`
	`6`	`+fori:=0;i<n;i++ {`
	`7`	`+iflen(strs[i])<res {`
	`8`	`+continue`
	`9`	`+}`
	`10`	`+j:=-1`
	`11`	`+forj<n {`
	`12`	`+j++`
	`13`	`+ifi!=j&&isSub(strs[i],strs[j]) {`
	`14`	`+break`
	`15`	`+}`
	`16`	`+}`
	`17`	`+ifj==n {`
	`18`	`+res=max(res,len(strs[i]))`
	`19`	`+}`
	`20`	`+}`
	`21`	`+returnres`
	`22`	`+}`
	`23`	`+`
	`24`	`+funcmax(x,yint)int {`
	`25`	`+ifx>y {`
	`26`	`+returnx`
	`27`	`+}`
	`28`	`+returny`
	`29`	`+}`
	`30`	`+`
	`31`	`+funcisSub(a,bstring)bool {`
	`32`	`+i,j:=0,0`
	`33`	`+fori<len(a)&&j<len(b) {`
	`34`	`+ifa[i]==b[j] {`
	`35`	`+i++`
	`36`	`+j++`
	`37`	`+}`
	`38`	`+}`
	`39`	`+returni==len(a)`
	`40`	`+}`

Comments

(0)