Commitfc48eb1

authored

Create 1553-minimum-number-of-days-to-eat-n-oranges.kt

1 parent2f5ad9c commitfc48eb1Copy full SHA for fc48eb1

File tree

+72

-0

lines changed

+72

-0

lines changed

Lines changed: 72 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,72 @@`
	`1`	`+// dfs`
	`2`	`+classSolution {`
	`3`	`+funminDays(n:Int):Int {`
	`4`	`+val dp=HashMap<Int,Int>().apply {`
	`5`	`+this[0]=0`
	`6`	`+this[1]=1`
	`7`	`+ }`
	`8`	`+`
	`9`	`+fundfs(n:Int):Int {`
	`10`	`+if (nin dp)return dp[n]!!`
	`11`	`+`
	`12`	`+val divByTwo=1+ (n%2)+ dfs(n/2)`
	`13`	`+val divByThree=1+ (n%3)+ dfs(n/3)`
	`14`	`+`
	`15`	`+ dp[n]= minOf(`
	`16`	`+ divByTwo,`
	`17`	`+ divByThree`
	`18`	`+ )`
	`19`	`+`
	`20`	`+return dp[n]!!`
	`21`	`+ }`
	`22`	`+`
	`23`	`+return dfs(n)`
	`24`	`+ }`
	`25`	`+}`
	`26`	`+`
	`27`	`+// Bonus: same as above but with more compact code`
	`28`	`+classSolution {`
	`29`	`+funminDays(n:Int):Int {`
	`30`	`+val dp=HashMap<Int,Int>()`
	`31`	`+`
	`32`	`+fundfs(n:Int):Int {`
	`33`	`+if (n<=1)return n`
	`34`	`+`
	`35`	`+if (n!in dp) {`
	`36`	`+ dp[n]= minOf(`
	`37`	`+1+ (n%2)+ dfs(n/2),`
	`38`	`+1+ (n%3)+ dfs(n/3)`
	`39`	`+ )`
	`40`	`+ }`
	`41`	`+`
	`42`	`+return dp[n]!!`
	`43`	`+ }`
	`44`	`+`
	`45`	`+return dfs(n)`
	`46`	`+ }`
	`47`	`+}`
	`48`	`+`
	`49`	`+// bfs`
	`50`	`+classSolution {`
	`51`	`+funminDays(n:Int):Int {`
	`52`	`+val q=LinkedList<Int>().apply { add(n) }`
	`53`	`+val visited=HashSet<Int>()`
	`54`	`+var days=1`
	`55`	`+`
	`56`	`+while (q.isNotEmpty()) {`
	`57`	`+ repeat (q.size) {`
	`58`	`+val n= q.removeFirst()`
	`59`	`+if (n==1\|\| n==0)return days`
	`60`	`+if (n!in visited) {`
	`61`	`+ visited.add(n)`
	`62`	`+ q.addLast(n-1)`
	`63`	`+if (n%2==0) q.addLast(n/2)`
	`64`	`+if (n%3==0) q.addLast(n/3)`
	`65`	`+ }`
	`66`	`+ }`
	`67`	`+ days++`
	`68`	`+ }`
	`69`	`+`
	`70`	`+return days`
	`71`	`+ }`
	`72`	`+}`

Comments

(0)