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

Commit44e7863

Browse files
authored
Sri Hari: Batch-3/Neetcode-150/Added Golang, Kotlin (neetcode-gh#3728)
* Added Golang, Kotlin* Added Golang, Kotlin* Added Golang, Kotlin* Added Golang, Kotlin* Added Golang, Kotlin* Added Golang, Kotlin* Added Golang, Kotlin
1 parent7e0c9a7 commit44e7863

File tree

35 files changed

+7614
-20
lines changed

35 files changed

+7614
-20
lines changed

‎articles/burst-balloons.md

Lines changed: 176 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -138,12 +138,63 @@ public class Solution {
138138
}
139139
```
140140

141+
```go
142+
funcmaxCoins(nums []int)int {
143+
nums =append([]int{1}, nums...)
144+
nums =append(nums,1)
145+
146+
vardfsfunc(nums []int)int
147+
dfs =func(nums []int)int {
148+
iflen(nums) ==2 {
149+
return0
150+
}
151+
152+
maxCoins:=0
153+
fori:=1; i <len(nums)-1; i++ {
154+
coins:= nums[i-1] * nums[i] * nums[i+1]
155+
coins +=dfs(append(append([]int{}, nums[:i]...), nums[i+1:]...))
156+
if coins > maxCoins {
157+
maxCoins = coins
158+
}
159+
}
160+
return maxCoins
161+
}
162+
163+
returndfs(nums)
164+
}
165+
```
166+
167+
```kotlin
168+
classSolution {
169+
funmaxCoins(nums:IntArray):Int {
170+
val newNums= intArrayOf(1)+ nums+ intArrayOf(1)
171+
172+
fundfs(nums:IntArray):Int {
173+
if (nums.size==2) {
174+
return0
175+
}
176+
177+
var maxCoins=0
178+
for (iin1 until nums.size-1) {
179+
val coins= nums[i-1]* nums[i]* nums[i+1]
180+
val nextCoins= dfs(nums.take(i).toIntArray()+
181+
nums.drop(i+1).toIntArray())
182+
maxCoins= maxOf(maxCoins, coins+ nextCoins)
183+
}
184+
return maxCoins
185+
}
186+
187+
return dfs(newNums)
188+
}
189+
}
190+
```
191+
141192
::tabs-end
142193

143194
###Time & Space Complexity
144195

145-
- Time complexity: $O(n*2^n)$
146-
- Space complexity: $O(n*2^n)$
196+
* Time complexity: $O(n*2^n)$
197+
* Space complexity: $O(n*2^n)$
147198

148199
---
149200

@@ -314,12 +365,77 @@ public class Solution {
314365
}
315366
```
316367

368+
```go
369+
funcmaxCoins(nums []int)int {
370+
nums =append([]int{1}, nums...)
371+
nums =append(nums,1)
372+
n:=len(nums)
373+
374+
dp:=make([][]int, n)
375+
fori:=0; i < n; i++ {
376+
dp[i] =make([]int, n)
377+
}
378+
379+
vardfsfunc(l, rint)int
380+
dfs =func(l, rint)int {
381+
if l > r {
382+
return0
383+
}
384+
if dp[l][r] >0 {
385+
return dp[l][r]
386+
}
387+
388+
dp[l][r] =0
389+
fori:= l; i <= r; i++ {
390+
coins:= nums[l-1] * nums[i] * nums[r+1]
391+
coins +=dfs(l, i-1) +dfs(i+1, r)
392+
dp[l][r] =max(dp[l][r], coins)
393+
}
394+
return dp[l][r]
395+
}
396+
397+
returndfs(1,len(nums)-2)
398+
}
399+
400+
funcmax(a,bint)int {
401+
if a > b {
402+
return a
403+
}
404+
return b
405+
}
406+
```
407+
408+
```kotlin
409+
classSolution {
410+
funmaxCoins(nums:IntArray):Int {
411+
val newNums= intArrayOf(1)+ nums+ intArrayOf(1)
412+
val n= newNums.size
413+
val dp=Array(n) {IntArray(n) }
414+
415+
fundfs(l:Int,r:Int):Int {
416+
if (l> r)return0
417+
if (dp[l][r]>0)return dp[l][r]
418+
419+
dp[l][r]=0
420+
for (iin l..r) {
421+
val coins= newNums[l-1]* newNums[i]* newNums[r+1]
422+
val totalCoins= coins+ dfs(l, i-1)+ dfs(i+1, r)
423+
dp[l][r]= maxOf(dp[l][r], totalCoins)
424+
}
425+
return dp[l][r]
426+
}
427+
428+
return dfs(1, newNums.size-2)
429+
}
430+
}
431+
```
432+
317433
::tabs-end
318434

319435
###Time & Space Complexity
320436

321-
- Time complexity: $O(n^3)$
322-
- Space complexity: $O(n^2)$
437+
* Time complexity: $O(n ^3)$
438+
* Space complexity: $O(n ^2)$
323439

324440
---
325441

@@ -451,10 +567,63 @@ public class Solution {
451567
}
452568
```
453569

570+
```go
571+
funcmaxCoins(nums []int)int {
572+
n:=len(nums)
573+
newNums:=append([]int{1}, nums...)
574+
newNums =append(newNums,1)
575+
576+
dp:=make([][]int, n+2)
577+
fori:=range dp {
578+
dp[i] =make([]int, n+2)
579+
}
580+
581+
forl:= n; l >=1; l-- {
582+
forr:= l; r <= n; r++ {
583+
fori:= l; i <= r; i++ {
584+
coins:= newNums[l-1] * newNums[i] * newNums[r+1]
585+
coins += dp[l][i-1] + dp[i+1][r]
586+
dp[l][r] =max(dp[l][r], coins)
587+
}
588+
}
589+
}
590+
591+
return dp[1][n]
592+
}
593+
594+
funcmax(a,bint)int {
595+
if a > b {
596+
return a
597+
}
598+
return b
599+
}
600+
```
601+
602+
```kotlin
603+
classSolution {
604+
funmaxCoins(nums:IntArray):Int {
605+
val n= nums.size
606+
val newNums= intArrayOf(1)+ nums+ intArrayOf(1)
607+
608+
val dp=Array(n+2) {IntArray(n+2) }
609+
610+
for (lin n downTo1) {
611+
for (rin l..n) {
612+
for (iin l..r) {
613+
val coins= newNums[l-1]* newNums[i]* newNums[r+1]
614+
dp[l][r]= maxOf(dp[l][r], coins+ dp[l][i-1]+ dp[i+1][r])
615+
}
616+
}
617+
}
618+
619+
return dp[1][n]
620+
}
621+
}
622+
```
623+
454624
::tabs-end
455625

456626
###Time & Space Complexity
457627

458-
- Time complexity: $O(n^3)$
459-
- Space complexity: $O(n^2)$
460-
628+
* Time complexity: $O(n^3)$
629+
* Space complexity: $O(n^2)$

0 commit comments

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