查找下一个有效 Table

Question

我们得到了一个距离列表，比如距离 = [2, 4, 1]。 tables 的数量是距离的长度 + 1，因此在我们的示例中我们将有 4 tables。对于每个 table 我们需要找到下一个有效的 table 以便 table j 和 i 之间的距离大于或等于 6 英尺。如果不存在这样的 table，则将 j 的下一个有效 table 设置为 0。此外，单个 table 的宽度为 1 英尺。所以在我们的例子中我们有：

t1 -- t2 ---- t3 - t4
where a single dash represents 1ft.

Next valid table for t1 is 0
Next valid table for t2 is 0 
Next valid table for t3 is t1 because they share a distance of 7ft between them
Next valid table for t4 is t2 because they share a distance of 6ft between them

如何计算出每个 table 的下一个有效 table？我注意到第一个 table 是特殊的，因为它之前没有其他 table 所以它的下一个有效 table 将自动设置为 0。我还发现有子问题需要被解决（所以我想我可以用自下而上的动态编程方式来做）。下一个 table 的解决方案将取决于其前一个 table 的解决方案。这是我想出的一些逻辑：

if distance between table i and i-1 is >= 6:
    next valid table for i is i-1
elif table i-1 has a next valid, table i's next valid will be table (i-1) next valid + 1
else:
     # Stuck here on how to find the next valid table

我觉得我在正确的轨道上获得了这个 O(n)，但我需要一点额外的帮助。

Answer 1

列出 table 个位置并维护指向正确 table 的指针，这是下一个 i.

的答案

  2   4   1
0   3   8   10
t1  t2  t3  t4

t1 0  ptr 0
t2 0  ptr 0
t3 t1 ptr t1
t4 t2 ptr t2

左指针最多增加O(n)次，我们将使用O(n)次额外space.

Answer 2

我使用的方法不是动态规划，而是保留一个尾随指针，该指针跟随距离列表的前向迭代，紧靠参数指定的 max_distance 间隙。每当它可以安全地指向一个新的 table 并且仍然满足所需的距离间隙时，这个尾随指针就会增加。对于每条指令，指针告诉我们哪个 table 是“下一个”（实际上，“前一个”相对于前向迭代，“下一个”相对于后向迭代）。

其他一切都是簿记问题，以确保该指针位于正确的位置。这是烦人的部分。

时间复杂度是线性的，因为推动后向指针的内部循环执行的总次数永远不会超过 n 次。 Space 复杂度为 O(1)。

def next_valid_tables(dists, max_dist):

    # keeps track of the gap between the left index and the current table
    running_dist = 0

    # O(n), makes the coding easier but not a necessary expense
    dists = [0] + dists 

    left = 0
    result = []

    for i, dist in enumerate(dists):
        running_dist += dist

        # Move the left index forward as long as we can still
        # satisfy the running_dist >= max_dist requirement.
        # The - 1 and + 1s handle the width of a single table.
        while left < i and running_dist - dists[left] - 1 >= max_dist:
            running_dist -= dists[left] + 1
            left += 1

        running_dist += 1 # Add the width of this table

        # The left pointer now points at the nearest valid table 
        # (or 0) so it's the result for this element
        result.append(left)
    
    return result

if __name__ == "__main__":
    print(next_valid_tables([2, 4, 1], 6)) # => [0, 0, 1, 2]
    # 1 2 3 4  <-- table idxes
    #  4 4 1   <-- dists
    # 0 1 2 2  <-- next table idxes

    print(next_valid_tables([4, 4, 1], 2)) # => [0, 1, 2, 2]
    # 1 2 3 4  <-- table idxes
    #  2 4 1   <-- dists
    # 0 1 2 2  <-- next table idxes

    print(next_valid_tables([2, 1, 1, 1, 1, 2, 6,], 6)) # => [0, 0, 0, 1, 1, 2, 4, 7]
    # 1 2 3 4 5 6 7 8  <-- table idxes
    #  2 1 1 1 1 2 6   <-- dists
    # 0 0 0 1 1 2 4 7  <-- next table idxes

查找下一个有效 Table

Finding Next Valid Table

python

algorithm

dynamic-programming

data-structures