algorithm - 错误的动态规划算法

Question

从 Code Review 转来。如果这个问题也不适合 SO，请告诉我。我会删除它。

我正在研究算法难题:https://www.hackerrank.com/challenges/hackerland-radio-transmitters/forum

它不能通过所有的测试用例。一些测试用例具有如此大的数组，以至于很难调试。我这边的简单案例似乎都可以正常工作。任何人都可以研究这个并分享这个算法有什么问题吗？基本上它只是循环遍历数组并找到每个最远的覆盖站(作为 origin)。类似计数器的变量 result 记录来源(广播电台)。

def solution(k, arr, origin=0):
    arr = sorted(list(set(arr)))
    result = 1
    cur = 0
    origin = 0

    for i in range(1, len(arr)):
        if arr[i] - arr[origin] <= k:
            pass
        else:
            origin = i - 1
            j = 1
            while origin + j < len(arr):
                if arr[origin + j] - arr[origin] <= k:
                    pass
                else:
                    origin = origin + j
                    i = origin + j + 1
                    result += 1
                    continue
                j += 1
    return result

Answer 1

您的大部分代码都是正确的。唯一的问题是使用 For range 外循环并在内循环中继续。

• For range 循环不会在运行时改变 i 值(它更像是一个 ForEach 循环)。
• continue 不会终止内部循环 - 您可能需要使用 break。

下面的代码通过了所有的测试用例

def solution(k, arr, origin=0):
    arr = sorted(list(set(arr)))
    print arr
    result = 1 
    cur = 0
    origin = 0
    i = 0 

    while (i < len(arr)):
        if arr[i] - arr[origin] <= k:
        i = i + 1
            pass
        else:
            origin = i - 1
            j = 1
            while origin + j < len(arr):
                if arr[origin + j] - arr[origin] <= k:
                    pass
                else:
                    # Start for next station position from this point
                    i = origin + j
                    origin = i
                    # need another radio station
                    result += 1
                    break
                j += 1
    return result

希望对您有所帮助!