1345. Jump Game IV
Task text is translated from Russian for the selected interface language. Code is left unchanged.
Дан array целых чисел arr, изначально вы находитесь на первом индексе arrayа.
За один шаг вы можете прыгнуть с индекса i на индекс:
- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.
Вернуть минимальное количество шагов, чтобы достичь последнего индекса arrayа.
Обратите внимание, что нельзя прыгать за пределы arrayа в любой момент времени.
Example:
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
matched/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
auto-draft, review before submit#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
matched/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
matched/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
matched/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
matched/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
Построить graph, где ключи - значения из arrayа, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.
Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.
Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.
😎
Vacancies for this task
Active vacancies with overlapping task tags are shown.
There are no active vacancies yet.