错误的动态规划算法

Question

从代码审查转移。如果这个问题也不适合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 范围外循环并在内循环中继续。

• 对于范围循环不会更改 i 值 @ 运行时(它更像是一个 ForEach 循环(。
• 继续不会终止内部循环 - 您可能希望使用 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

希望对您有所帮助！

Answer 2

您将第一个对象放在第一个索引上。最优解中的第一个对象也可以稍后放置。

solution(1,[1,2,3,4,5,6])打印 3，当它应该是 2 时(通过将两个对象放在 2 和 5 上(。你把第一个对象放在 1 上，然后是 3，然后是 5。理想情况下，它应该放在 2 上，然后放在 5 上。