Codility NailingPlanks - 在钉子计数上使用二进制搜索而不是木板

Question

我已经通读了这个问题的答案 - 。这不是重复的，因为我正在尝试使用不同的方法解决这个问题 - 而不是运行在给定钉子可以覆盖的木板上进行二进制搜索，我试图运行计算覆盖所有木板所需的钉子总数。

这是我的代码：

def solution(A, B, C):
    min_nails = 1
    max_nails = len(C)
    valid = []
    while (min_nails <= max_nails):
        mid_nails = (min_nails + max_nails) // 2
        if (is_valid_nails_amount(mid_nails,A,B,C)):
            max_nails = mid_nails - 1
            valid.append(mid_nails)
        else: 
            min_nails = mid_nails + 1
    return -1 if len(valid) == 0 else min(valid)

def is_valid_nails_amount(nails,A,B,C): 
    candidates=C[0:nails]
    min_cover = min(candidates)
    max_cover = max(candidates)
    isValid = True
    for (a,b) in zip(A,B): 
        if not(min_cover in range(a, b + 1) or max_cover in range(a, b + 1) or a in range(min_cover, max_cover + 1) or b in range(min_cover, max_cover + 1)): 
            isValid = False
            break 
    return isValid

算法首先检查 C:

中的前 len(C) + 1 / 2 个钉子

首先计算出这个范围内钉子能覆盖的最小值和最大值(min_cover和max_cover)。
接下来，它遍历A和B，检查每块木板是否可以被(min_cover, max_cover)范围内的任何钉子钉上。
如果结果是False，我们将min_nails更新为mid_nails + 1并重复。如果结果是 True，我们将钉子的数量存储在 valid 数组中，并尝试通过设置 max_nails = mid_nails - 1

此方法获得 100% 的正确性，但在性能测试中失败，因为它产生了不正确的结果 - 对于每个性能测试，最小钉数 obtained 远低于预期结果。我怀疑错误会在这一行：if not(min_cover in range(a, b + 1) or max_cover in range(a, b + 1) or a in range(min_cover, max_cover + 1) or b in range(min_cover, max_cover + 1))

但我不知道它是什么。

Answer 1

您的 if 条件的问题可以通过此示例输入看出：

A = [1,3,5]
B = [2,4,6]
C = [1,5,3]
print(solution(A, B, C))

这将打印 2，但预期输出为 3，因为需要所有三个钉子。

然而，你的代码将有 is_valid_nails_amount(2, A, B, C) return True，尽管第二块木板没有被那两个钉子钉住。

问题是这两种情况都不能保证钉子能打到木板上(a, b):

a in range(min_cover, max_cover + 1)
b in range(min_cover, max_cover + 1)

您的算法确实需要检查 min/max 范围内是否有可用于击中木板的钉子。

Codility NailingPlanks - 在钉子计数上使用二进制搜索而不是木板

Codility NailingPlanks - Using Binary Search on Nail Count Instead of Planks

python

algorithm

binary-search