|
| 1 | +/** |
| 2 | + * GREEDY approach of solving Jump Game. |
| 3 | + * |
| 4 | + *@param {number[]} numbers - array of possible jump length. |
| 5 | + */ |
| 6 | +exportdefaultfunctiongrdJumpGame(numbers){ |
| 7 | +// The "good" cell is a cell from which we may jump to the last cell of the numbers array. |
| 8 | + |
| 9 | +// The last cell in numbers array is for sure the "good" one since it is our goal to reach. |
| 10 | +letleftGoodPosition=numbers.length-1; |
| 11 | + |
| 12 | +// Go through all numbers from right to left. |
| 13 | +for(letnumberIndex=numbers.length-2;numberIndex>=0;numberIndex-=1){ |
| 14 | +// If we can reach the "good" cell from the current one then for sure the current |
| 15 | +// one is also "good". Since after all we'll be able to reach the end of the array |
| 16 | +// from it. |
| 17 | +constmaxCurrentJumpLength=numberIndex+numbers[numberIndex]; |
| 18 | +if(maxCurrentJumpLength>=leftGoodPosition){ |
| 19 | +leftGoodPosition=numberIndex; |
| 20 | +} |
| 21 | +} |
| 22 | + |
| 23 | +// If the most left "good" position is the zero's one then we may say that it IS |
| 24 | +// possible jump to the end of the array from the first cell; |
| 25 | +returnleftGoodPosition===0; |
| 26 | +} |