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

Commitc135e4c

Browse files
authored
Sri Hari: Batch-3/Neetcode-150/Added Golang, Kotlin (neetcode-gh#3724)
* Added Golang, Kotlin* Added Golang, Kotlin* Added Golang, Kotlin* Added Golang, Kotlin* Added Golang, Kotlin
1 parent1dd97f0 commitc135e4c

18 files changed

+4999
-10
lines changed

‎articles/cheapest-flight-path.md

Lines changed: 202 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -25,7 +25,7 @@ class Solution:
2525
dist[nei][nextStops+1]= nextCst
2626
heapq.heappush(minHeap, (nextCst, nei, nextStops))
2727

28-
return-1
28+
return-1
2929
```
3030

3131
```java
@@ -46,7 +46,7 @@ public class Solution {
4646
Comparator.comparingInt(a-> a[0])
4747
);
4848
minHeap.offer(newint[]{0, src,-1});
49-
49+
5050
while (!minHeap.isEmpty()) {
5151
int[] top= minHeap.poll();
5252
int cst= top[0], node= top[1], stops= top[2];
@@ -186,6 +186,78 @@ public class Solution {
186186
}
187187
```
188188

189+
```go
190+
funcfindCheapestPrice(nint,flights [][]int,srcint,dstint,kint)int {
191+
INF:=1000000000
192+
adj:=make([][]struct{ to, costint }, n)
193+
dist:=make([][]int, n)
194+
fori:=range dist {
195+
dist[i] =make([]int, k+5)
196+
forj:=range dist[i] {
197+
dist[i][j] = INF
198+
}
199+
}
200+
for_,flight:=range flights {
201+
from,to,cost:= flight[0], flight[1], flight[2]
202+
adj[from] =append(adj[from],struct{ to, costint }{to, cost})
203+
}
204+
dist[src][0] =0
205+
minHeap:= priorityqueue.NewWith(func(a, binterface{})int {
206+
return utils.IntComparator(a.([3]int)[0], b.([3]int)[0])
207+
})
208+
minHeap.Enqueue([3]int{0, src, -1})
209+
for !minHeap.Empty() {
210+
value,_:= minHeap.Dequeue()
211+
cst,node,stops:= value.([3]int)[0], value.([3]int)[1], value.([3]int)[2]
212+
if node == dst {
213+
return cst
214+
}
215+
if stops == k || dist[node][stops+1] < cst {
216+
continue
217+
}
218+
for_,nei:=range adj[node] {
219+
nextCst:= cst + nei.cost
220+
nextStops:= stops +1
221+
if dist[nei.to][nextStops+1] > nextCst {
222+
dist[nei.to][nextStops+1] = nextCst
223+
minHeap.Enqueue([3]int{nextCst, nei.to, nextStops})
224+
}
225+
}
226+
}
227+
return -1
228+
}
229+
```
230+
231+
```kotlin
232+
classSolution {
233+
funfindCheapestPrice(n:Int,flights:Array<IntArray>,src:Int,dst:Int,k:Int):Int {
234+
valINF=1_000_000_000
235+
val adj=Array(n) { mutableListOf<Pair<Int,Int>>() }
236+
val dist=Array(n) {IntArray(k+5) {INF } }
237+
for (flightin flights) {
238+
adj[flight[0]].add(Pair(flight[1], flight[2]))
239+
}
240+
dist[src][0]=0
241+
val minHeap=PriorityQueue(compareBy<Triple<Int,Int,Int>> { it.first })
242+
minHeap.add(Triple(0, src,-1))
243+
while (minHeap.isNotEmpty()) {
244+
val (cst, node, stops)= minHeap.poll()
245+
if (node== dst)return cst
246+
if (stops== k|| dist[node][stops+1]< cst)continue
247+
for ((nei, w)in adj[node]) {
248+
val nextCst= cst+ w
249+
val nextStops= stops+1
250+
if (dist[nei][nextStops+1]> nextCst) {
251+
dist[nei][nextStops+1]= nextCst
252+
minHeap.add(Triple(nextCst, nei, nextStops))
253+
}
254+
}
255+
}
256+
return-1
257+
}
258+
}
259+
```
260+
189261
::tabs-end
190262

191263
###Time & Space Complexity
@@ -346,6 +418,59 @@ public class Solution {
346418
}
347419
```
348420

421+
```go
422+
funcfindCheapestPrice(nint,flights [][]int,srcint,dstint,kint)int {
423+
prices:=make([]int, n)
424+
fori:=range prices {
425+
prices[i] = math.MaxInt32
426+
}
427+
prices[src] =0
428+
429+
fori:=0; i <= k; i++ {
430+
tmpPrices:=make([]int, n)
431+
copy(tmpPrices, prices)
432+
433+
for_,flight:=range flights {
434+
s,d,p:= flight[0], flight[1], flight[2]
435+
if prices[s] == math.MaxInt32 {
436+
continue
437+
}
438+
if prices[s] + p < tmpPrices[d] {
439+
tmpPrices[d] = prices[s] + p
440+
}
441+
}
442+
prices = tmpPrices
443+
}
444+
445+
if prices[dst] == math.MaxInt32 {
446+
return -1
447+
}
448+
return prices[dst]
449+
}
450+
```
451+
452+
```kotlin
453+
classSolution {
454+
funfindCheapestPrice(n:Int,flights:Array<IntArray>,src:Int,dst:Int,k:Int):Int {
455+
val prices=IntArray(n) {Int.MAX_VALUE }
456+
prices[src]=0
457+
458+
repeat(k+1) {
459+
val tmpPrices= prices.copyOf()
460+
for ((s, d, p)in flights) {
461+
if (prices[s]==Int.MAX_VALUE)continue
462+
if (prices[s]+ p< tmpPrices[d]) {
463+
tmpPrices[d]= prices[s]+ p
464+
}
465+
}
466+
tmpPrices.copyInto(prices)
467+
}
468+
469+
returnif (prices[dst]==Int.MAX_VALUE)-1else prices[dst]
470+
}
471+
}
472+
```
473+
349474
::tabs-end
350475

351476
###Time & Space Complexity
@@ -527,6 +652,81 @@ public class Solution {
527652
}
528653
```
529654

655+
```go
656+
funcfindCheapestPrice(nint,flights [][]int,srcint,dstint,kint)int {
657+
prices:=make([]int, n)
658+
fori:=range prices {
659+
prices[i] = math.MaxInt32
660+
}
661+
prices[src] =0
662+
663+
adj:=make([][][2]int, n)
664+
for_,flight:=range flights {
665+
from,to,cost:= flight[0], flight[1], flight[2]
666+
adj[from] =append(adj[from], [2]int{to, cost})
667+
}
668+
669+
q:= [][3]int{{0, src,0}}
670+
671+
forlen(q) >0 {
672+
curr:= q[0]
673+
q = q[1:]
674+
cst,node,stops:= curr[0], curr[1], curr[2]
675+
676+
if stops > k {
677+
continue
678+
}
679+
680+
for_,neighbor:=range adj[node] {
681+
nei,w:= neighbor[0], neighbor[1]
682+
nextCost:= cst + w
683+
if nextCost < prices[nei] {
684+
prices[nei] = nextCost
685+
q =append(q, [3]int{nextCost, nei, stops +1})
686+
}
687+
}
688+
}
689+
690+
if prices[dst] == math.MaxInt32 {
691+
return -1
692+
}
693+
return prices[dst]
694+
}
695+
```
696+
697+
```kotlin
698+
classSolution {
699+
funfindCheapestPrice(n:Int,flights:Array<IntArray>,src:Int,dst:Int,k:Int):Int {
700+
val prices=IntArray(n) {Int.MAX_VALUE }
701+
prices[src]=0
702+
703+
val adj=Array(n) { mutableListOf<Pair<Int,Int>>() }
704+
for (flightin flights) {
705+
val (from, to, cost)= flight
706+
adj[from].add(Pair(to, cost))
707+
}
708+
709+
val q:Queue<Triple<Int,Int,Int>>=LinkedList()
710+
q.offer(Triple(0, src,0))
711+
712+
while (q.isNotEmpty()) {
713+
val (cst, node, stops)= q.poll()
714+
if (stops> k)continue
715+
716+
for ((nei, w)in adj[node]) {
717+
val nextCost= cst+ w
718+
if (nextCost< prices[nei]) {
719+
prices[nei]= nextCost
720+
q.offer(Triple(nextCost, nei, stops+1))
721+
}
722+
}
723+
}
724+
725+
returnif (prices[dst]==Int.MAX_VALUE)-1else prices[dst]
726+
}
727+
}
728+
```
729+
530730
::tabs-end
531731

532732
###Time & Space Complexity

0 commit comments

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