diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/jump_game4.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/jump_game4.cpp')
-rw-r--r-- | other/jump_game4.cpp | 52 |
1 files changed, 52 insertions, 0 deletions
diff --git a/other/jump_game4.cpp b/other/jump_game4.cpp new file mode 100644 index 0000000..8496d94 --- /dev/null +++ b/other/jump_game4.cpp @@ -0,0 +1,52 @@ +// 1345. Jump Game IV +#include "leetcode.h" + +/* + * given array of integers 'arr', you are initially positioned at first index of + * array. in one step, you can jump from index 'i' to index 'j'. return minimum + * number of steps to reach lat index of array. notice, you cannot jump outside + * of array at any time. + */ + +class Solution { +public: + int minJumps(vector<int> &arr) { + int n = arr.size(), step = 0; + unordered_map<int, vector<int>> idx_val; + for (int i = 0; i < n; i++) + idx_val[arr[i]].push_back(i); + vector<bool> visited(n); + visited[0] = true; + queue<int> q; + q.push(0); + while (!q.empty()) { + for (int size = q.size(); size > 0; --size) { + int i = q.front(); + q.pop(); + if (i == n - 1) + return step; // end of arr + vector<int> next = idx_val[arr[i]]; + next.push_back(i - 1); + next.push_back(i + 1); + for (int j : next) { + if (j >= 0 && j < n && !visited[j]) { + visited[j] = true; + q.push(j); + } + } + next.clear(); + } + step++; + } + return 0; + } +}; + +int main() { + Solution obj; + vector<int> a1 = {100, -23, -23, 404, 100, 23, 23, 23, 3, 404}; + vector<int> a2 = {7}, a3 = {7, 6, 9, 6, 9, 6, 9, 7}; + cout << obj.minJumps(a1) << endl; // expect: 3 + cout << obj.minJumps(a2) << endl; // expect: 0 + cout << obj.minJumps(a3) << endl; // expect: 1 +} |