55. Jump Game

LeetCode medium original: C# #array #csharp #dynamic-programming #leetcode #math #medium #recursion

Le texte du problème est traduit du russe pour la langue sélectionnée. Le code reste inchangé.

LeetCode Static

Вам дан tableau целых чисел nums. Изначально вы находитесь на первом индексе tableauа, и каждый element tableauа представляет вашу максимальную длину прыжка в этой позиции.

return true, если вы можете достичь последнего индекса, или false в противном случае.

Exemple

Input: nums = [2,3,1,1,4]

Output: true

Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

C# solution

correspondant/original

public enum Index { GOOD, BAD, UNKNOWN }
public class Solution {
    Index[] memo;
    public bool CanJumpFromPosition(int position, int[] nums) {
        if (memo[position] != Index.UNKNOWN) {
            return memo[position] == Index.GOOD ? true : false;
        }
        int furthestJump = Math.Min(position + nums[position], nums.Length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump;
             nextPosition++) {
            if (CanJumpFromPosition(nextPosition, nums)) {
                memo[position] = Index.GOOD;
                return true;
            }
        }
        memo[position] = Index.BAD;
        return false;
    }
    public bool CanJump(int[] nums) {
        memo = new Index[nums.Length];
        for (int i = 0; i < memo.Length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.Length - 1] = Index.GOOD;
        return CanJumpFromPosition(0, nums);
    }
}

C++ solution

brouillon automatique, à relire avant soumission

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public enum Index { GOOD, BAD, UNKNOWN }
class Solution {
public:
    Index[] memo;
    public bool CanJumpFromPosition(int position, vector<int>& nums) {
        if (memo[position] != Index.UNKNOWN) {
            return memo[position] == Index.GOOD ? true : false;
        }
        int furthestJump = min(position + nums[position], nums.size() - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump;
             nextPosition++) {
            if (CanJumpFromPosition(nextPosition, nums)) {
                memo[position] = Index.GOOD;
                return true;
            }
        }
        memo[position] = Index.BAD;
        return false;
    }
    public bool CanJump(vector<int>& nums) {
        memo = new Index[nums.size()];
        for (int i = 0; i < memo.size(); i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.size() - 1] = Index.GOOD;
        return CanJumpFromPosition(0, nums);
    }
}

Java solution

correspondant/original

enum Index {
    GOOD,
    BAD,
    UNKNOWN,
}

public class Solution {
    Index[] memo;

    public boolean canJumpFromPosition(int position, int[] nums) {
        if (memo[position] != Index.UNKNOWN) {
            return memo[position] == Index.GOOD;
        }

        int furthestJump = Math.min(position + nums[position], nums.length - 1);
        for (int nextPosition = position + 1; nextPosition <= furthestJump; nextPosition++) {
            if (canJumpFromPosition(nextPosition, nums)) {
                memo[position] = Index.GOOD;
                return true;
            }
        }

        memo[position] = Index.BAD;
        return false;
    }

    public boolean canJump(int[] nums) {
        memo = new Index[nums.length];
        for (int i = 0; i < memo.length; i++) {
            memo[i] = Index.UNKNOWN;
        }
        memo[memo.length - 1] = Index.GOOD;
        return canJumpFromPosition(0, nums);
    }
}

JavaScript solution

correspondant/original

let memo;
const canJumpFromPosition = (position, nums) => {
    if (memo[position] != "UNKNOWN") {
        return memo[position] == "GOOD";
    }
    let furthestJump = Math.min(position + nums[position], nums.length - 1);
    for (
        let nextPosition = position + 1;
        nextPosition <= furthestJump;
        nextPosition++
    ) {
        if (canJumpFromPosition(nextPosition, nums)) {
            memo[position] = "GOOD";
            return true;
        }
    }
    memo[position] = "BAD";
    return false;
};
var canJump = function (nums) {
    memo = new Array(nums.length).fill("UNKNOWN");
    memo[memo.length - 1] = "GOOD";
    return canJumpFromPosition(0, nums);
};

Python solution

correspondant/original

class Solution:
    def __init__(self):
        self.memo = []
        self.nums = []

    def canJumpFromPosition(self, position):
        if self.memo[position] != -1:
            return self.memo[position] == 1
        furthestJump = min(position + self.nums[position], len(self.nums) - 1)
        for nextPosition in range(position + 1, furthestJump + 1):
            if self.canJumpFromPosition(nextPosition):
                self.memo[position] = 1
                return True
        self.memo[position] = 0
        return False

    def canJump(self, nums):
        self.nums = nums
        self.memo = [-1] * len(nums)
        self.memo[-1] = 1
        return self.canJumpFromPosition(0)

Go solution

correspondant/original

type Index int

const (
    GOOD    Index = 1
    BAD     Index = 2
    UNKNOWN Index = 0
)

var memo []Index

func canJumpFromPosition(position int, nums []int) bool {
    if memo[position] != UNKNOWN {
        return memo[position] == GOOD
    }
    furthestJump := position + nums[position]
    if furthestJump > len(nums)-1 {
        furthestJump = len(nums) - 1
    }
    for nextPosition := position + 1; nextPosition <= furthestJump; nextPosition++ {
        if canJumpFromPosition(nextPosition, nums) {
            memo[position] = GOOD
            return true
        }
    }
    memo[position] = BAD
    return false
}

func canJump(nums []int) bool {
    memo = make([]Index, len(nums))
    for i := range memo {
        memo[i] = UNKNOWN
    }
    memo[len(nums)-1] = GOOD
    return canJumpFromPosition(0, nums)
}

Algorithm

1️⃣

Инициализация таблицы памяти:

Изначально все elementы таблицы памяти имеют статус UNKNOWN, за исключением последнего, который является (тривиально) GOOD (может достичь сам себя).

2️⃣

Модификация Algorithmeа обратного трассирования:

Измените Algorithme обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).

Если индекс известен, тогда returnsся True/False.

3️⃣

Выполнение и сохранение результатов:

Если индекс не известен, выполняйте шаги обратного трассирования, как ранее.

После определения значения текущего индекса, сохраните его в таблице памяти.

😎

Vacancies for this task

offres actives with overlapping task tags are affichés.

Toutes les offres

Il n'y a pas encore d'offres actives.