55. Jump Game
Văn bản bài toán được dịch từ tiếng Nga theo ngôn ngữ giao diện. Mã không thay đổi.
Вам дан mảng целых чисел nums. Изначально вы находитесь на первом индексе mảngа, и каждый element mảngа представляет вашу максимальную длину прыжка в этой позиции.
return true, если вы можете достичь последнего индекса, или false в противном случае.
Ví dụ
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# lời giải
đã khớp/gốcpublic 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++ lời giải
bản nháp tự động, xem lại trước khi gửi#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 lời giải
đã khớp/gốcenum 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 lời giải
đã khớp/gốclet 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 lời giải
đã khớp/gốcclass 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 lời giải
đã khớp/gốctype 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️⃣
Модификация Thuật toánа обратного трассирования:
Измените Thuật toán обратного трассирования таким образом, чтобы на рекурсивном шаге сначала проверялось, известен ли индекс (GOOD/BAD).
Если индекс известен, тогда returnsся True/False.
3️⃣
Выполнение и сохранение результатов:
Если индекс не известен, выполняйте шаги обратного трассирования, как ранее.
После определения значения текущего индекса, сохраните его в таблице памяти.
😎
Vacancies for this task
việc làm đang hoạt động with overlapping task tags are đã hiển thị.
Chưa có việc làm đang hoạt động.