leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

1345.cpp (1263B)

0 class Solution { 1 public: 2 int minJumps(vector<int> &arr) { 3 if (arr.size() < 2) return 0; 4 if (arr.front() == arr.back()) return 1; 5 6 unordered_map<int, vector<int>> um; 7 unordered_set<int> visited; 8 int n = arr.size(); 9 10 for (int i = 0; i < n; i++) 11 um[arr[i]].push_back(i); 12 13 queue<int> q; 14 q.push(0); 15 visited.insert(0); 16 for (int lvl = 0; !q.empty(); lvl++) { 17 for (int k = q.size(); k > 0; k--) { 18 int crnt = q.front(); 19 q.pop(); 20 21 if (crnt == n - 1) return lvl; 22 23 if (crnt + 1 < n && !visited.count(crnt + 1)) { 24 visited.insert(crnt + 1); 25 q.push(crnt + 1); 26 } 27 28 if (crnt - 1 >= 0 && !visited.count(crnt - 1)) { 29 visited.insert(crnt - 1); 30 q.push(crnt - 1); 31 } 32 33 for (int index : um[arr[crnt]]) { 34 if (!visited.count(index)) { 35 visited.insert(index); 36 q.push(index); 37 } 38 } 39 40 um[arr[crnt]].clear(); 41 } 42 } 43 return -1; 44 } 45 };