在 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
从 main 方法中,执行以下操作 −
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
相关文章
有用资源
python 参考教程 - 该教程包含有关 python 的更多信息:https://www.cainiaomax.com/python/

