朋友们，几天前我参加了一个面试，我被一个问题绊倒了…我还没有找到一个完全相同的解决方案，用我平庸的谷歌技能，所以在这里我请求全能的堆栈与大家分享。然而，这是提示(尽我所能记住)…
你是剧院的引座员，你的工作是告诉来的客人是否可以入座。用户告诉你他们聚会的规模(numtobesated)，你告诉他们是否可以坐下。如果有足够的空间你返回一个布尔值True或False如果没有空间． 给定一行(seats[])，写一个函数返回一行是否合适。
唯一的限制是客人不能邻座
只有两个参数…
seatingProgram(seats[],numToBeSeated){}
给定数组座位[]会有一个由1和0组成的数组。1表示已占用空间，0表示空白空间。
numToBeSeated是一个大于零的非负整数
- 示例1)
席位[1,0,0,0,0,0,1,0,0)
numtobehated =3 ---->真正的
numtobehated = 4 ----->假
你可以容纳3个客人，但不能容纳4个。之后，您的数组将是这样的入住3位客人…
[1, 0, 1, 0, 1, 0, 1, 0, 1]
- 例子2)
席位[0]
numtobehated =1 ---->真正的
- 示例3)
席位[1]
numtobehated =1 ---->假
- 示例4)
席位(0,0)
numtobehated =1 ---->真正的
numtobehated =2 ---->假
解决这个问题的有效方法是什么?也许是动态规划?哈哈，我噎住了，只是用了一个for循环和一堆边缘情况的蛮力。可能在那之后就不会有回电了哈哈。但是我想有一种更优雅的方法。
为了可读性，我希望我们可以保留Python，但也欢迎其他语言。=)
您可以在您要检查的列表的第一个和末尾添加两个0，然后从index=1检查您的列表直到index=end-1，并且对于每个迭代检查三个连续的数字，如果所有这些three numbers == zero，您有一个位置并在中间插入一个人并减少numto贝特，如果numToBeSeated==0您可以通过问题:
def seatingProgram(seats, numToBeSeated):
if numToBeSeated == 0:
return True
seats = [0] + seats + [0]
for i in range(1, len(seats)-1):
if seats[i-1] == seats[i] == seats[i+1] == 0:
seats[i] = 1
numToBeSeated -= 1
if numToBeSeated == 0:
return True
return False
输出:
print(seatingProgram([1,0,0,0,0,0,1,0,0], 3))
# True
print(seatingProgram([1,0,0,0,0,0,1,0,0], 4))
# False
print(seatingProgram([0,0], 1))
# True
print(seatingProgram([0,0], 2))
# False
其他答案都是正确的，但动态规划方案实际上是最简单的
def seatingProgram(seats, n):
fulln = 0 # number of people you can seat with a guest in the preceding seat
emptyn = 0 # number of people you can seat without a guest in the preceding seat
for seat in seats:
if seat > 0:
emptyn, fulln = max(fulln, emptyn), 0
else
emptyn, fulln = max(fulln, emptyn), emptyn+1
return max(fulln, emptyn) >= n
查找非的所有连续0块与1s相邻。在每个长度为n的块中，您可以放置ceil(n/2)的来宾。
工作原理:
- 客人在一个区块的位置显然不影响其他区块的座位
- 这意味着最大化每个块是可行的
ceil(n/2)是你可以容纳的最大座位，从鸽子洞原则-如果你坐更多，那么两个将是相邻的。- 很明显这个上限是可以达到的，只要替换
1s和0s
- 很明显这个上限是可以达到的，只要替换