BFS: Jump Game IV

Using pair to record the index and depth

`const int N = 5e4 + 10;int f[N];class Solution {public:    int minJumps(vector<int>& arr) {        memset(f, 0, sizeof(f));        const int n = arr.size();        if (n == 1) return 0;        unordered_map<int, vector<int>> m;        for (int i = 0; i < n; ++i) {            //if (i >= 1 && i < n -1 && arr[i-1] == arr[i] && arr[i] == arr[i+1]) continue;            m[arr[i]].push_back(i);        }        deque<pair<int, int>> dq;        dq.emplace_back(n-1, 0);        int ret = 0;        while (true) {            auto [k, depth] = dq.front();dq.pop_front();            if (k == 0) {                return depth;            }            for (auto &x: m[arr[k]]) {                if (x != k && !f[x]) {                    f[x] = 1;                    if (x == 0) return depth + 1;                    dq.emplace_back(x, depth + 1);                }            }            for (auto di : {-1, 1}) {                if (k + di < n && k + di >= 0 && !f[k + di]) {                    f[k + di] = 1;                    if (k + di == 0) return depth + 1;                    dq.emplace_back( k + di, depth + 1);                }            }        }        return ret;            }};`

A better way

`const int N = 5e4 + 10;bool f[N];class Solution {public:    int minJumps(vector<int>& arr) {        memset(f, 0, sizeof(f));        const int n = arr.size();        if (n==1) return 0;        unordered_map<int, vector<int>> m;        for (int i = 0; i < n; ++i) {            if (i >= 1 && i < n -1 && arr[i-1] == arr[i] && arr[i] == arr[i+1]) continue;            m[arr[i]].push_back(i);        }        deque<int> dq;        dq.emplace_back(n-1);        int ret = 0;        int depth = 1;        f[n-1] = true;        while (true) {            int sz = dq.size();            for (int i = 0; i < sz; ++i) {                int k = dq.front(); dq.pop_front();                if (k == 0) return depth;                for (auto &x: m[arr[k]]) {                    if (x != k &&  !f[x]) {                        f[x] = true;                        if (x == 0) return depth;                        dq.push_back(x);                    }                }                for (auto di : {-1, 1}) {                    if (k + di < n && k + di >= 0 && !f[k + di]) {                         f[k + di] = true;                        if (k + di == 0) return depth;                        dq.push_back(k + di);                    }                }             }            depth++;        }                return ret;      }};`

--

--

More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.