My C++ solution using queue


  • 0
    C
    struct nodes {
        int index;
        int range;
        int step;
        nodes(int a, int b, int c) {
            index = a;
            range = b;
            step = c;
        }
    };
    
    class Solution {
    public:
        int jump(vector<int>& nums) {
            int len = nums.size();
            if(len <= 1) return 0;
            
            nodes first(0, nums[0], 0);
            queue<nodes>que;
            que.push(first);
            
            while(!que.empty()) {
                nodes cur = que.front();
                que.pop();
                int nextIndex = 0, nextRange = 0, maxRange = 0;
                
                if(cur.index + cur.range >= len - 1) {
                    return ++cur.step;
                }
                
                for(int i = 1;i <= cur.range;i ++) {
                    if(maxRange < cur.index + i + nums[cur.index + i]) {
                        maxRange = cur.index + i + nums[cur.index + i];
                        nextIndex = cur.index + i;
                        nextRange = nums[cur.index + i];
                    }
                }
                
                nodes next(nextIndex, nextRange, cur.step + 1);
                que.push(next);
            }
            
            return 1;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.