arrays - 当所有跳跃的长度相同并且某些位置无法降落时，我可以通过一个范围移动的最小跳跃是多少？

Question

通过 CodeFights 工作。这是第 5 级的问题 4 https://codefights.com/arcade/intro/level-5/XC9Q2DhRRKQrfLhb5 :

You are given an array of integers representing coordinates of obstacles situated on a straight line.

Assume that you are jumping from the point with coordinate 0 to the right. You are allowed only to make jumps of the same length represented by some integer.

Find the minimal length of the jump enough to avoid all the obstacles.

Example

For inputArray = [5, 3, 6, 7, 9], the output should be avoidObstacles(inputArray) = 4.

Check out the image below for better understanding:

Input/Output

[time limit] 4000ms (rb) [input] array.integer inputArray

Non-empty array of positive integers.

Constraints: 2 ≤ inputArray.length ≤ 10, 1 ≤ inputArray[i] ≤ 40.

[output] integer

The desired length.

实现这一目标的自然方法似乎是步骤。这是我的代码:

def avoidObstacles(arr)
  jumps = (arr.min..arr.max+1).to_a - arr
  full_map = (0..arr.max+1)
  jumps.each do |j|
    return j if (full_map.step(j).to_a & arr).empty?
  end
end

更清晰的写法:

def avoidObstacles(arr)
  jumps = (arr.min..arr.max+1).reject{|n| arr.include?(n)}
  full_map = (0..arr.max+1)
  jumps.each do |j|
    return j if full_map.step(j).none?{|n|arr.include?(n)}
  end
end

我通过了网站上给出的所有可见测试:

Input: inputArray: [5, 3, 6, 7, 9] Expected Output: 4

Input: inputArray: [2, 3] Expected Output: 4

Input: inputArray: [1, 4, 10, 6, 2] Expected Output: 7

但我在一项隐藏测试中被绊倒了。我从另一个用户那里借用了一个解决方案，它适用于所有情况:

def avoidObstacles a
    obs = a.each_with_object(Hash.new(false)){|v, h| h[v]=true}
    m = a.max
    (1..m+1).each do |j|
        return j if (0...m/j+1).all?{ |i| obs[i*j] == false }
    end
    m
end

我不太确定这个借来的解决方案在哪里成功而我的失败了。

提前感谢您的帮助。我对编码还很陌生，感谢您抽出时间。

Answer 1

avoidObstacles [3,5,7] #=> 4

但它应该是2。你要

def avoid_obstacles(arr)
  return nil if arr.empty? or arr.max == 1
  jumps = (2..arr.max+1).to_a - arr
  full_map = (0..arr.max+1)
  jumps.each do |j|
    return j if (full_map.step(j).to_a & arr).empty?
  end
end

avoid_obstacles [3,5,7]
  #=> 2

我更改了方法的名称，因为 Ruby 惯例是使用 snake-case用于方法和变量的名称。

其他人的解决方案有效，因为它从 j = 1 开始搜索。 (它可以从 j=2 开始，因为 j = 1 总是会失败。