加速解决算法

Question

正在研究以下算法：

Given an array of non-negative integers, you are initially positioned at the first index of the array.

Each element in the array represents your maximum jump length at that position.

Determine if you are able to reach the last index.

For example:

A = [2,3,1,1,4], return true.

A = [3,2,1,0,4], return false.

以下是我的解决方案。它会尝试每一个可能的步骤，然后相应地记忆。因此，如果第一个元素是三，则代码执行三步、两步和一步，并从那里启动三个独立的函数。然后我用哈希记忆。我的问题是代码工作得很好，但是对于非常大的输入它会超时。记忆有帮助，但只有一点点。我是在正确记忆还是在回溯错误的方法？

def can_jump(nums)
    @memo = {}
    avail?(nums, 0)
end

def avail?(nums, index)
    return true if nums.nil? || nums.empty? || nums.length == 1 || index >= nums.length - 1
    current = nums[index]
    true_count = 0
    until current == 0  #try every jump from the val to 1
        @memo[index + current] ||= avail?(nums, index + current)
        true_count +=1 if @memo[index + current] == true
        current -= 1
    end

    true_count > 0

end

Answer 1

您的代码是 O(n^2)，但您可以在 O(n) 时间和 O(1) space 内生成结果。这个想法是通过数组向后工作，保持到目前为止找到的最小索引，您可以从该索引到达索引 n-1。

像这样：

def can_jump(nums)
    min_index = nums.length - 1
    for i in (nums.length - 2).downto(0)
        if nums[i] + i >= min_index
            min_index = i
        end
    end
    min_index == 0
end

print can_jump([2, 3, 1, 1, 4]), "\n"
print can_jump([3, 2, 1, 0, 4]), "\n"

Answer 2

这是一个 () 算法：

初始化为0。
对于中的每个数字：
1. 如果大于，则和后面的数都达不到，所以
  - return 假.
2. 如果+大于，设置为+。
如果大于或等于中的最后一个索引
- return 真.
- 否则return false.

这是一个 Ruby 实现：

def can_jump(nums)
  max_reach = 0
  nums.each_with_index do |num, idx|
    return false if idx > max_reach
    max_reach = [idx+num, max_reach].max
  end
  max_reach >= nums.size - 1
end

p can_jump([2,3,1,1,4]) # => true
p can_jump([3,2,1,0,4]) # => false

在 repl.it 上查看：https://repl.it/FvlV/1

加速解决算法

Speeding up solution to algorithm

ruby

algorithm

memoization

time-complexity