656. Coin Path
Вам дан целочисленный массив монет (1-индексированный) длины n и целое число maxJump. Вы можете перейти на любой индекс i массива coins, если coins[i] != -1 и вы должны заплатить coins[i] при посещении индекса i. Кроме того, если вы в данный момент находитесь на индексе i, вы можете перейти только на любой индекс i + k, где i + k <= n и k - значение в диапазоне [1, maxJump]. Изначально вы находитесь на индексе 1 (coins[1] не -1). Вы хотите найти путь, который достигнет индекса n с минимальной стоимостью. Верните целочисленный массив индексов, которые вы посетите в таком порядке, чтобы достичь индекса n с минимальной стоимостью. Если существует несколько путей с одинаковой стоимостью, верните лексикографически наименьший такой путь. Если невозможно достичь индекса n, возвращается пустой массив. Путь p1 = [Pa1, Pa2, ..., Pax] длины x лексикографически меньше, чем p2 = [Pb1, Pb2, ..., Pbx] длины y, если и только если при первом j, где Paj и Pbj отличаются, Paj < Pbj; если такого j нет, то x < y.
Пример:
Input: coins = [1,2,4,-1,2], maxJump = 2
Output: [1,3,5]
C# решение
сопоставлено/оригиналusing System;
using System.Collections.Generic;
public class Solution {
public List<int> MinCostPath(int[] coins, int maxJump) {
int n = coins.Length;
if (coins[0] == -1) return new List<int>();
int[] dp = new int[n];
Array.Fill(dp, int.MaxValue);
dp[0] = coins[0];
List<int>[] path = new List<int>[n];
for (int i = 0; i < n; i++) path[i] = new List<int>();
path[0].Add(1);
PriorityQueue<(int cost, int index), int> heap = new PriorityQueue<(int, int), int>();
heap.Enqueue((coins[0], 0), coins[0]);
while (heap.Count > 0) {
var (currentCost, i) = heap.Dequeue();
if (currentCost > dp[i]) continue;
for (int k = 1; k <= maxJump; k++) {
if (i + k < n && coins[i + k] != -1) {
int newCost = currentCost + coins[i + k];
if (newCost < dp[i + k] || (newCost == dp[i + k] && ComparePaths(path[i], path[i + k], i + k + 1))) {
dp[i + k] = newCost;
path[i + k] = new List<int>(path[i]);
path[i + k].Add(i + k + 1);
heap.Enqueue((newCost, i + k), newCost);
}
}
}
}
return dp[n - 1] == int.MaxValue ? new List<int>() : path[n - 1];
}
private bool ComparePaths(List<int> path1, List<int> path2, int newIndex) {
List<int> newPath1 = new List<int>(path1);
newPath1.Add(newIndex);
return string.Join(",", newPath1).CompareTo(string.Join(",", path2)) < 0;
}
public static void Main(string[] args) {
Solution solution = new Solution();
int[] coins = { 0, 2, 4, -1, 2, 5 };
int maxJump = 2;
var result = solution.MinCostPath(coins, maxJump);
}
}C++ решение
auto-draft, проверить перед отправкой#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public List<int> MinCostPath(vector<int>& coins, int maxJump) {
int n = coins.size();
if (coins[0] == -1) return new List<int>();
vector<int>& dp = new int[n];
Array.Fill(dp, int.MaxValue);
dp[0] = coins[0];
List<int>[] path = new List<int>[n];
for (int i = 0; i < n; i++) path[i] = new List<int>();
path[0].push_back(1);
PriorityQueue<(int cost, int index), int> heap = new PriorityQueue<(int, int), int>();
heap.Enqueue((coins[0], 0), coins[0]);
while (heap.size() > 0) {
var (currentCost, i) = heap.Dequeue();
if (currentCost > dp[i]) continue;
for (int k = 1; k <= maxJump; k++) {
if (i + k < n && coins[i + k] != -1) {
int newCost = currentCost + coins[i + k];
if (newCost < dp[i + k] || (newCost == dp[i + k] && ComparePaths(path[i], path[i + k], i + k + 1))) {
dp[i + k] = newCost;
path[i + k] = new List<int>(path[i]);
path[i + k].push_back(i + k + 1);
heap.Enqueue((newCost, i + k), newCost);
}
}
}
}
return dp[n - 1] == int.MaxValue ? new List<int>() : path[n - 1];
}
private bool ComparePaths(List<int> path1, List<int> path2, int newIndex) {
List<int> newPath1 = new List<int>(path1);
newPath1.push_back(newIndex);
return string.Join(",", newPath1).CompareTo(string.Join(",", path2)) < 0;
}
public static void Main(vector<string> args) {
Solution solution = new Solution();
vector<int>& coins = { 0, 2, 4, -1, 2, 5 };
int maxJump = 2;
var result = solution.MinCostPath(coins, maxJump);
}
}Java решение
сопоставлено/оригиналimport java.util.*;
class Solution {
public List<Integer> minCostPath(int[] coins, int maxJump) {
int n = coins.length;
if (coins[0] == -1) return new ArrayList<>();
int[] dp = new int[n];
Arrays.fill(dp, Integer.MAX_VALUE);
dp[0] = coins[0];
List<Integer>[] path = new List[n];
for (int i = 0; i < n; i++) path[i] = new ArrayList<>();
path[0].add(1);
PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
heap.offer(new int[] { coins[0], 0 });
while (!heap.isEmpty()) {
int[] current = heap.poll();
int current_cost = current[0], i = current[1];
if (current_cost > dp[i]) continue;
for (int k = 1; k <= maxJump; k++) {
if (i + k < n && coins[i + k] != -1) {
int new_cost = current_cost + coins[i + k];
if (new_cost < dp[i + k] || (new_cost == dp[i + k] && comparePaths(path[i], path[i + k], i + k + 1))) {
dp[i + k] = new_cost;
path[i + k] = new ArrayList<>(path[i]);
path[i + k].add(i + k + 1);
heap.offer(new int[] { new_cost, i + k });
}
}
}
}
return dp[n - 1] == Integer.MAX_VALUE ? new ArrayList<>() : path[n - 1];
}
private boolean comparePaths(List<Integer> path1, List<Integer> path2, int newIndex) {
List<Integer> newPath1 = new ArrayList<>(path1);
newPath1.add(newIndex);
return newPath1.toString().compareTo(path2.toString()) < 0;
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] coins = {0, 2, 4, -1, 2, 5};
int maxJump = 2;
}JavaScript решение
сопоставлено/оригиналvar minCostPath = function(coins, maxJump) {
const n = coins.length;
if (coins[0] === -1) return [];
const dp = new Array(n).fill(Infinity);
dp[0] = coins[0];
const path = Array.from({ length: n }, () => []);
path[0] = [1];
const heap = [[coins[0], 0]];
while (heap.length) {
heap.sort((a, b) => a[0] - b[0]);
const [current_cost, i] = heap.shift();
if (current_cost > dp[i]) continue;
for (let k = 1; k <= maxJump; k++) {
if (i + k < n && coins[i + k] !== -1) {
const new_cost = current_cost + coins[i + k];
if (new_cost < dp[i + k] || (new_cost === dp[i + k] && path[i].concat(i + k + 1) < path[i + k])) {
dp[i + k] = new_cost;
path[i + k] = path[i].concat(i + k + 1);
heap.push([new_cost, i + k]);
}
}
}
}
return dp[n - 1] === Infinity ? [] : path[n - 1];
};Python решение
сопоставлено/оригиналimport heapq
def minCostPath(coins, maxJump):
n = len(coins)
if coins[0] == -1:
return []
dp = [float('inf')] * n
dp[0] = coins[0]
path = [[] for _ in range(n)]
path[0] = [1]
heap = [(coins[0], 0)] # (cost, index)
while heap:
current_cost, i = heapq.heappop(heap)
if current_cost > dp[i]:
continue
for k in range(1, maxJump + 1):
if i + k < n and coins[i + k] != -1:
new_cost = current_cost + coins[i + k]
if new_cost < dp[i + k] or (new_cost == dp[i + k] and path[i] + [i + k + 1] < path[i + k]):
dp[i + k] = new_cost
path[i + k] = path[i] + [i + k + 1]
heapq.heappush(heap, (new_cost, i + k))
return path[-1] if dp[-1] != float('inf') else []Go решение
сопоставлено/оригиналpackage main
import (
"container/heap"
"fmt"
"math"
"sort"
)
type Item struct {
cost, index int
}
type PriorityQueue []*Item
func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool {
return pq[i].cost < pq[j].cost
}
func (pq PriorityQueue) Swap(i, j int) {
pq[i], pq[j] = pq[j], pq[i]
}
func (pq *PriorityQueue) Push(x interface{}) {
*pq = append(*pq, x.(*Item))
}
func (pq *PriorityQueue) Pop() interface{} {
old := *pq
n := len(old)
item := old[n-1]
*pq = old[0 : n-1]
return item
}
func minCostPath(coins []int, maxJump int) []int {
n := len(coins)
if coins[0] == -1 {
return []int{}
}
dp := make([]int, n)
for i := range dp {
dp[i] = math.MaxInt32
}
dp[0] = coins[0]
path := make([][]int, n)
for i := range path {
path[i] = []int{}
}
path[0] = []int{1}
pq := &PriorityQueue{&Item{cost: coins[0], index: 0}}
heap.Init(pq)
for pq.Len() > 0 {
current := heap.Pop(pq).(*Item)
currentCost, i := current.cost, current.index
if currentCost > dp[i] {
continue
}
for k := 1; k <= maxJump; k++ {
if i+k < n && coins[i+k] != -1 {
newCost := currentCost + coins[i+k]
newPath := append([]int{}, path[i]...)
newPath = append(newPath, i+k+1)
if newCost < dp[i+k] || (newCost == dp[i+k] && lexicographicalLess(newPath, path[i+k])) {
dp[i+k] = newCost
path[i+k] = newPath
heap.Push(pq, &Item{cost: newCost, index: i+k})
}
}
}
}
if dp[n-1] == math.MaxInt32 {
return []int{}
}
return path[n-1]
}
func lexicographicalLess(a, b []int) bool {
for i := range a {
if i >= len(b) {
return false
}
if a[i] != b[i] {
return a[i] < b[i]
}
}
return len(a) < len(b)
}Algorithm
Используйте динамическое программирование для нахождения минимальной стоимости до каждого индекса, начиная с первого.
Храните путь до каждого индекса для отслеживания наименьшего лексикографического пути.
Используя полученную информацию, восстановите путь с минимальной стоимостью до последнего индекса.
😎
Вакансии для этой задачи
Показаны активные вакансии с пересечением по тегам задачи.
Активных вакансий пока нет.