online advertising

Thursday, July 9, 2015

LeetCode OJ - Jump Game

Problem:

Please find the problem here.

Solution:

It feels like a reachability problem, but it is one that comes with a special structure so that we can do it in linear time.

The code for this one really simple, so the code should explain it. .

If we can reach a certain position, then we can reach any position before it. So we define the horizon as the maximally reachable index. If we figure we can go further, then update the horizon, if the horizon is the end of the array (sometimes even further than it), then we can stop the algorithm and report true.

If we cannot reach, then just return false.

Code:

#include "stdafx.h"

// https://leetcode.com/problems/jump-game/

#include "LEET_JUMP_GAME.h"
#include <map>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

namespace _LEET_JUMP_GAME
{
    class Solution {
    public:
        bool canJump(vector<int>& nums)
        {
            unsigned int horizon = 0;
            for (unsigned int i = 0; i <= horizon; i++)
            {
                if (horizon >= nums.size() - 1)
                {
                    return true;
                }
                horizon = max(i + nums[i], horizon);
            }

            return false;
        }
    };
}

using namespace _LEET_JUMP_GAME;

int LEET_JUMP_GAME()
{
    Solution solution;
    int case1Array[] = { 2, 3, 1, 1, 4 };
    int case2Array[] = { 3, 2, 1, 0, 4 };
    vector<int> case1 = vector<int>(case1Array, case1Array + 5);
    vector<int> case2 = vector<int>(case2Array, case2Array + 5);
    cout << solution.canJump(case1) << endl;
    cout << solution.canJump(case2) << endl;
    return 0;
}

No comments :

Post a Comment