1345. Jump Game IV
Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.
Дан tableau целых чисел arr, изначально вы находитесь на первом индексе tableauа.
За один шаг вы можете прыгнуть с индекса i на индекс:
- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.
Вернуть минимальное количество шагов, чтобы достичь последнего индекса tableauа.
Обратите внимание, что нельзя прыгать за пределы tableauа в любой момент времени.
Exemple:
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# solution
correspondant/originalpublic 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++ solution
brouillon automatique, à relire avant soumission#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 solution
correspondant/originalclass 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 solution
correspondant/originalclass 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 solution
correspondant/originalclass 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 solution
correspondant/originalpackage 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
Построить graphe, где ключи - значения из tableauа, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.
Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.
Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.
😎
Vacancies for this task
offres actives with overlapping task tags are affichés.
Il n'y a pas encore d'offres actives.