55. Jump Game

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

El texto de la tarea se traduce del ruso para el idioma seleccionado. El código no cambia.

LeetCode Static

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

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

Ejemplo

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# solución

coincidente/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++ solución

borrador automático, revisar antes de enviar

#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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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 solución

coincidente/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️⃣

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

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

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

3️⃣

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

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

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

😎

Vacantes para esta tarea

Se muestran vacantes activas con etiquetas coincidentes.

Todas las vacantes

Todavía no hay vacantes activas.