สมมติว่าเรามีอาร์เรย์ของจำนวนเต็มที่เรียกว่า arr เราอยู่ที่ดัชนี 0 ในขั้นตอนเดียว เราสามารถข้ามจากดัชนี i ไปยัง i + x โดยที่:i + x
ดังนั้นหากอินพุตเป็นแบบนั้น
จากนั้นผลลัพธ์จะเป็น 3 เราต้องกระโดดสามครั้งจากดัชนี 0 เป็น 4 เป็น 3 เป็น 9
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งแผนที่ m
-
n :=ขนาดของ arr
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
ใส่ i ต่อท้าย m[arr[i]]
-
-
ใส่ i ต่อท้าย m[arr[i]]
-
ใส่ 0 เข้าไป
-
กำหนดหนึ่งคิว q
-
สำหรับการเริ่มต้น lvl :=0 เมื่อไม่มี q ว่าง ให้อัปเดต (เพิ่ม lvl ขึ้น 1), do−
-
sz :=ขนาดของ q
-
ในขณะที่ sz ไม่ใช่ศูนย์ ให้ลด sz ในการวนซ้ำแต่ละครั้ง 1 ทำ −
-
curr :=องค์ประกอบแรกของ q
-
ลบองค์ประกอบออกจาก q
-
ถ้า curr เหมือนกับ n - 1 แล้ว
-
กลับเลเวล
-
-
ผม :=สกุลเงิน
-
ถ้า i - 1>=0 และไม่ใช่ i - 1 อยู่ในการเยี่ยมชมแล้ว −
-
ใส่ i - 1 ลงใน q
-
ใส่ i - 1 เข้าไป
-
-
ถ้า i + 1
-
แทรก i + 1 ลงใน q
-
แทรก i + 1 ลงในการเยี่ยมชม
-
-
สำหรับการเริ่มต้น j :=0 เมื่อ j
-
ถ้า (m[arr[curr], j]) ไม่ได้เข้าเยี่ยม −
-
แทรก m[arr[curr], j] ลงใน q
-
แทรก m[arr[curr], j] เข้าไป
-
-
-
ถ้า arr[curr] ไม่อยู่ใน m แล้ว −
-
ลบ arr[curr] จาก m
-
-
-
-
กลับ -1
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int minJumps(vector<int>& arr) {
map<int, vector<int> > m;
int n = arr.size();
for (int i = 0; i < n; i++) {
m[arr[i]].push_back(i);
}
set<int> visited;
visited.insert(0);
queue<int> q;
q.push(0);
for (int lvl = 0; !q.empty(); lvl++) {
int sz = q.size();
while (sz--) {
int curr = q.front();
q.pop();
if (curr == n - 1)
return lvl;
int i = curr;
if (i - 1 >= 0 && !visited.count(i - 1)) {
q.push(i - 1);
visited.insert(i - 1);
}
if (i + 1 < n && !visited.count(i + 1)) {
q.push(i + 1);
visited.insert(i + 1);
}
for (int j = 0; j < m[arr[curr]].size(); j++) {
if (!visited.count(m[arr[curr]][j])) {
q.push(m[arr[curr]][j]);
visited.insert(m[arr[curr]][j]);
}
}
if (m.count(arr[curr])) {
m.erase(arr[curr]);
}
}
}
return -1;
}
};
main(){
Solution ob;
vector<int> v = {20,-5,-5,25,20,5,5,5,1,25};
cout << (ob.minJumps(v));
} อินพุต
{20,-5,-5,25,20,5,5,5,1,25} ผลลัพธ์
3
