用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 次檢視

開啟你的職業生涯

透過完成課程獲得認證

立即開始
廣告