本文介绍了动态规划:座位安排的数目的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

在我最近面试的一家公司,这是一个很有挑战性的问题。前提是,电影院必须遵守距离规则,即每两个坐着的人之间必须至少有六英尺的距离。我们得到了一个由N个非负整数组成的列表,其中list[k]是座位k和座位k+1之间的距离,单行有N+1个座位。我们需要计算出有效的座位安排数量。

编辑:经过更多的思考,这就是我到目前为止得到的

def count(seats):
    # No seats then no arrangements can be made
    if seats == 0:
        return 0
    elif seats == 1:
        # 1 seat means 2 arrangements -- leave it empty (skip) or occupy it
        return 2
    
    if list[seats-1] < 6:
       return count(seats - 1) + counts(seats - k(seats))
    else:
       return count(seats - 1)

回想一下列表将包含座位i和座位i+1之间的距离,因此在每个座位上,我将检查当前座位和前一个座位之间的距离是>;=6还是<;6。如果该距离小于6,则我可以跳过当前座位,也可以占用它。现在有一点棘手,如果我决定占据这个座位,我的子问题不是-1,它将-(跳到下一个有效座位的座位数)。我不知道怎么才能找到这个。另一种情况则更为简单,前一个座位与当前座位之间的距离为>;=6,因此无论我是否占据当前座位,我的子问题--座位数--都会减少1。

推荐答案

您可以使用two pointer technique和动态规划来解决此问题。
这里,dp[i]代表有效组合的数量,其中第i个席位是最后使用的(最后一个->最大索引)。

编码:

def count(distances):
    pref_dist = answer = 0
    pos = pos_sum = pos_dist = 0
    dp = [1] * (len(distances) + 1)
    for i in range(len(distances)):
        pref_dist += distances[i]
        while(pref_dist - pos_dist >= 6):
            pos_dist += distances[pos]
            pos_sum += dp[pos]
            pos += 1
        dp[i + 1] += pos_sum
    return sum(dp) + 1

时间复杂性:
它是O(n),其中n是席位数(不是O(n^2)),因为while条件在整个代码执行中最多为n次(指针pos从不减少,每次条件为真则pos加1,pos上限为n)),其中的每个操作都使用一个恒定的时间。

示例:

  1. 六个座位和距离数组[5,2,4,1,2]
    Count([5,2,4,1,2])->;16
    以下是有效组合(1表示采用):
    000000 101000 000010 100001
    100000 000100 100010 010001
    010000 100100 010010 001001
    001000 010100 000001 101001

  2. 四个座位距离数组[8,10,16]
    Count([8,10,6])->;16
    每种组合都是有效的组合。四个席位=2^4组合。

这篇关于动态规划:座位安排的数目的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-21 18:55