1345. Jump Game IV
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
Дан mảng целых чисел arr, изначально вы находитесь на первом индексе mảngа.
За один шаг вы можете прыгнуть с индекса i на индекс:
- i + 1, где: i + 1 < arr.length.
- i - 1, где: i - 1 >= 0.
- j, где: arr[i] == arr[j] и i != j.
Вернуть минимальное количество шагов, чтобы достичь последнего индекса mảngа.
Обратите внимание, что нельзя прыгать за пределы mảngа в любой момент времени.
Ví dụ:
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# lời giải
đã khớp/gốcpublic 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốcpackage 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
Построить đồ thị, где ключи - значения из mảngа, а значения - списки индексов этих значений. Начать с первого индекса, добавив его в очередь текущего слоя и инициализировать набор посещенных индексов.
Выполнять BFS: для каждого индекса текущего слоя проверять соседние индексы (i + 1, i - 1 и все j, где arr[i] == arr[j]), добавляя непосещенные индексы в очередь следующего слоя.
Повторять шаг 2, увеличивая счетчик шагов до достижения последнего индекса или пока не закончится очередь.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.
Chưa có việc làm đang hoạt động.