Skip to content

Instantly share code, notes, and snippets.

@jianminchen
Created June 23, 2017 19:06
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save jianminchen/a63bd91d4fecbd69bffb197cb52cf166 to your computer and use it in GitHub Desktop.
Save jianminchen/a63bd91d4fecbd69bffb197cb52cf166 to your computer and use it in GitHub Desktop.
Leetcode 45 - Jump game II - greedy algorithm
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace JumpGameII
{
class JumpGameII
{
static void Main(string[] args)
{
RunTestcase();
}
public static void RunTestcase()
{
var testcase = new int[] { 2, 3, 1, 1, 4 };
var numberSteps = Jump_backwardGreedy(testcase);
}
/// <summary>
/// June 23, 2017
/// Code review please!
///
/// Start from last index. For each step, find the smallest index
/// it can jump from and then update the last index until last index reaches zero.
/// The greedy algorithm works, how come? Figure out
/// Backward algorithm
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public static int Jump_backwardGreedy(int[] nums)
{
int lastIndex = nums.Length - 1;
int step = 0;
int smallestIndex;
while (lastIndex != 0)
{
// find smallest index to reach
for (smallestIndex = 0; smallestIndex < lastIndex; smallestIndex++)
{
var current = nums[smallestIndex];
if (smallestIndex + current >= lastIndex)
{
break;
}
}
if (smallestIndex == lastIndex)
{
return -1;
}
lastIndex = smallestIndex;
step++;
}
return step;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment