用Python查找在恰好k跳内到达最后一个岛屿所需的跳跃最大长度的最小值

假设我们有一个数字数组A，在A中，第i个数字表示岛屿所在的位置，并且给定另一个整数k（1 ≤ k < N）。现在，一个人站在第0个岛屿上，必须通过恰好k跳，从一个岛屿跳到另一个岛屿来到达最后一个岛屿，我们必须找到这个人在他/她的旅程中所做的跳跃最大长度的最小值。我们必须记住，所有岛屿的位置都是按升序给出的。

因此，如果输入类似于A = [7, 20, 41, 48]，k = 2，则输出将为28，因为有两种方法可以到达最后一个岛屿：从7到20到48，这里任何两个连续岛屿之间的最大距离是48和20之间，即28。以及从7到41到48，这里任何两个连续岛屿之间的最大距离是41和7之间，即34。所以，28和34的最小值是28。

为了解决这个问题，我们将遵循以下步骤：

  • 定义一个函数isPossible()。它将接收arr、dist、k作为参数。

  • n := arr的大小

  • req := 0

  • current := 0

  • previous := 0

  • 对于范围从0到n的i，执行以下操作：

    • 当current不等于n且(arr[current] - arr[previous]) <= dist时，执行以下操作：

      • current := current + 1

    • req := req + 1

    • 如果current等于n，则：

      • 退出循环

    • previous := current - 1

  • 如果current不等于n，则：

    • 返回False

  • 如果req <= k，则：

    • 返回True

  • 返回False

  • 从主方法中，执行以下操作：

  • n := arr的大小

  • left := 0

  • right := arr的最后一个元素

  • ans := 0

  • 当left <= right时，执行以下操作：

    • mid := (left + right) / 2;

    • 如果isPossible(arr, mid, k)不为零，则：

      • ans := mid

      • right := mid - 1

    • 否则：

      • left := mid + 1

  • 返回ans

示例

让我们看看以下实现以更好地理解：

def isPossible(arr,dist, k) :
   n = len(arr)
   req = 0
   current = 0
   previous = 0
   for i in range(0, n):
      while (current != n and (arr[current] - arr[previous]) <= dist):
         current += 1
      req += 1
      if (current == n):
         break
      previous = current - 1
   if (current != n):
      return False
   if (req <= k):
      return True
   return False
def minimum_distance(arr, k):
   n = len(arr)
   left = 0
   right = arr[-1]
   ans = 0
   while (left <= right):
      mid = (left + right) // 2;
      if (isPossible(arr, mid, k)):
         ans = mid
         right = mid - 1
      else:
         left = mid + 1
   return ans
arr = [7, 20, 41, 48]
k = 2
print(minimum_distance(arr, k))

输入

[7, 20, 41, 48] , 2

输出

28

更新于: 2020年8月20日

145 次查看

开启你的职业生涯

通过完成课程获得认证

立即开始
广告