Блог

Я пытаюсь решить проблему, и мой код завершается с ошибкой в одном тестовом примере, где список имеет длину 25000. Есть ли какой-нибудь способ сделать это быстрее. Я пытался использовать functools.lru_cache , и я все еще не могу выполнить в течение времени, необходимого для завершения.

Это проблема с сайта

Учитывая массив неотрицательных целых чисел nums, вы изначально располагаетесь по первому индексу массива.

Каждый элемент в массиве представляет вашу максимальную длину перехода в этой позиции.

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

Это то, что я пробовал

 def can_jump(input_list):

    @lru_cache
    def helper(idx = 0):
        if idx == len(input_list) - 1:
            return True
        return any(helper(new_idx) for x in range(input_list[idx]) 
        if (new_idx := idx   x   1) < len(input_list)) # increasing order of jumps

    return helper()
 

Примеры работы с тестовыми примерами

 input_list = [2,3,1,1,4]
print(can_jump(input_list)) # True
input_list = [3,2,1,0,4]
print(can_jump(input_list)) # False
 

Я также попытался пойти в другом направлении,

 return any(helper(new_idx) for x in range(input_list[idx], 0, -1) 
if (new_idx := idx   x) < len(input_list)) # decreasing order of jumps
 

Но я все еще не могу заставить это работать достаточно быстро, чтобы очистить последний тестовый пример списка элементов 25000, что я здесь делаю не так?

Хорошо, я думаю, я понял. Можете ли вы попробовать это? Пожалуйста, обратите внимание, это взято прямо из: https://codereview.stackexchange.com/questions/223612/jump-game-leetcode

 def canjump(nums):
    maximum_reachable_index = 0

    for index, max_jump in enumerate(nums):
        if index > maximum_reachable_index:
            return False

        maximum_reachable_index = max(index   max_jump, maximum_reachable_index)

    return True