1345. Jump Game IV
Il testo del problema è tradotto dal russo per la lingua selezionata. Il codice resta invariato.
Дан array целых чисел arr, изначально вы находитесь на первом индексе arrayа.
За один шаг вы можете прыгнуть с индекса i на индекс:
- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.
Вернуть минимальное количество шагов, чтобы достичь последнего индекса arrayа.
Обратите внимание, что нельзя прыгать за пределы arrayа в любой момент времени.
Esempio:
Input: arr = [100,-23,-23,404,100,23,23,23,3,404]
Output: 3
Explanation: You need three jumps from index 0 --> 4 --> 3 --> 9. Note that index 9 is the last index of the array.
C# soluzione
abbinato/originalepublic class Solution {
public int MinJumps(int[] arr) {
int n = arr.Length;
if (n <= 1) {
return 0;
}
var graph = new Dictionary<int, List<int>>();
for (int i = 0; i < n; i++) {
if (!graph.ContainsKey(arr[i])) {
graph[arr[i]] = new List<int>();
}
graph[arr[i]].Add(i);
}
var curs = new List<int> { 0 };
var visited = new HashSet<int> { 0 };
int step = 0;
while (curs.Count > 0) {
var nex = new List<int>();
foreach (var node in curs) {
if (node == n - 1) {
return step;
}
foreach (var child in graph[arr[node]]) {
if (!visited.Contains(child)) {
visited.Add(child);
nex.Add(child);
}
}
graph[arr[node]].Clear();
if (node + 1 < n && !visited.Contains(node + 1)) {
visited.Add(node + 1);
nex.Add(node + 1);
}
if (node - 1 >= 0 && !visited.Contains(node - 1)) {
visited.Add(node - 1);
nex.Add(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
}C++ soluzione
bozza automatica, rivedere prima dell'invio#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 int MinJumps(vector<int>& arr) {
int n = arr.size();
if (n <= 1) {
return 0;
}
var graph = new unordered_map<int, List<int>>();
for (int i = 0; i < n; i++) {
if (!graph.count(arr[i])) {
graph[arr[i]] = new List<int>();
}
graph[arr[i]].push_back(i);
}
var curs = new List<int> { 0 };
var visited = new HashSet<int> { 0 };
int step = 0;
while (curs.size() > 0) {
var nex = new List<int>();
foreach (var node in curs) {
if (node == n - 1) {
return step;
}
foreach (var child in graph[arr[node]]) {
if (!visited.Contains(child)) {
visited.push_back(child);
nex.push_back(child);
}
}
graph[arr[node]].Clear();
if (node + 1 < n && !visited.Contains(node + 1)) {
visited.push_back(node + 1);
nex.push_back(node + 1);
}
if (node - 1 >= 0 && !visited.Contains(node - 1)) {
visited.push_back(node - 1);
nex.push_back(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
}Java soluzione
abbinato/originaleclass Solution {
public int minJumps(int[] arr) {
int n = arr.length;
if (n <= 1) {
return 0;
}
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n; i++) {
graph.computeIfAbsent(arr[i], v -> new LinkedList<>()).add(i);
}
List<Integer> curs = new LinkedList<>();
curs.add(0);
Set<Integer> visited = new HashSet<>();
int step = 0;
while (!curs.isEmpty()) {
List<Integer> nex = new LinkedList<>();
for (int node : curs) {
if (node == n - 1) {
return step;
}
for (int child : graph.get(arr[node])) {
if (!visited.contains(child)) {
visited.add(child);
nex.add(child);
}
}
graph.get(arr[node]).clear();
if (node + 1 < n && !visited.contains(node + 1)) {
visited.add(node + 1);
nex.add(node + 1);
}
if (node - 1 >= 0 && !visited.contains(node - 1)) {
visited.add(node - 1);
nex.add(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
}JavaScript soluzione
abbinato/originaleclass Solution {
minJumps(arr) {
const n = arr.length;
if (n <= 1) return 0;
const graph = new Map();
for (let i = 0; i < n; i++) {
if (!graph.has(arr[i])) {
graph.set(arr[i], []);
}
graph.get(arr[i]).push(i);
}
let curs = [0];
const visited = new Set();
visited.add(0);
let step = 0;
while (curs.length > 0) {
const nex = [];
for (const node of curs) {
if (node === n - 1) return step;
for (const child of graph.get(arr[node])) {
if (!visited.has(child)) {
visited.add(child);
nex.push(child);
}
}
graph.get(arr[node]).length = 0;
if (node + 1 < n && !visited.has(node + 1)) {
visited.add(node + 1);
nex.push(node + 1);
}
if (node - 1 >= 0 && !visited.has(node - 1)) {
visited.add(node - 1);
nex.push(node - 1);
}
}
curs = nex;
step++;
}
return -1;
}
}Python soluzione
abbinato/originaleclass Solution:
def minJumps(self, arr):
n = len(arr)
if n <= 1:
return 0
graph = {}
for i in range(n):
if arr[i] not in graph:
graph[arr[i]] = []
graph[arr[i]].append(i)
curs = [0]
visited = {0}
step = 0
while curs:
nex = []
for node in curs:
if node == n - 1:
return step
for child in graph[arr[node]]:
if child not in visited:
visited.add(child)
nex.append(child)
graph[arr[node]] = []
if node + 1 < n and node + 1 not in visited:
visited.add(node + 1)
nex.append(node + 1)
if node - 1 >= 0 and node - 1 not in visited:
visited.add(node - 1)
nex.append(node - 1)
curs = nex
step += 1
return -1Go soluzione
abbinato/originalepackage main
import "container/list"
func minJumps(arr []int) int {
n := len(arr)
if n <= 1 {
return 0
}
graph := make(map[int][]int)
for i := 0; i < n; i++ {
graph[arr[i]] = append(graph[arr[i]], i)
}
curs := list.New()
curs.PushBack(0)
visited := make(map[int]bool)
visited[0] = true
step := 0
for curs.Len() > 0 {
nex := list.New()
for e := curs.Front(); e != nil; e = e.Next() {
node := e.Value.(int)
if node == n-1 {
return step
}
for _, child := range graph[arr[node]] {
if !visited[child] {
visited[child] = true
nex.PushBack(child)
}
}
graph[arr[node]] = nil
if node+1 < n && !visited[node+1] {
visited[node+1] = true
nex.PushBack(node+1)
}
if node-1 >= 0 && !visited[node-1] {
visited[node-1] = true
nex.PushBack(node-1)
}
}
curs = nex
step++
}
return -1
}Algorithm
Построить grafo, где ключи - значения из arrayа, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.
Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.
Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.
😎
Vacancies for this task
offerte attive with overlapping task tags are mostrati.
Non ci sono ancora offerte attive.