Created
June 23, 2017 19:06
-
-
Save jianminchen/a63bd91d4fecbd69bffb197cb52cf166 to your computer and use it in GitHub Desktop.
Leetcode 45 - Jump game II - greedy algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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