在Python中找出遇到给定条件的彩色顶点子集的数量
假设我们有一个数组colors,表示一个正则n边形的颜色。这里,这个n边形的每个顶点都随机着一种在给定数组中出现的n种不同颜色之一。我们必须找到特殊子集的多边形顶点数量,这些子集满足以下条件 –
- 子集的大小必须至少为两个。
- 如果我们从多边形中删除存在于子集中的顶点(那些顶点的相邻边也会被删除),则剩余的顶点和边形成一些连续路径。
- 这些路径中不应包含两个相同颜色的顶点。
我们必须统计出这样的子集的数量。如果答案太大,则返回结果mod 10 ^ 9 + 7。
因此,如果输入是colors = [1, 2, 3, 4],则输出将为11。
为了解决这个问题,我们将遵循以下步骤 –
- count :一个所有值都为空列表的空映射。
- n :颜色的大小
- 对于范围为0到颜色大小-1的i,请执行以下操作
- 在count[colors[i]]的末尾插入i
- answer :0
- 对于2到n的范围,请执行以下操作
- answer :answer + nCr(n,i)
- 对于count的所有键的列表中的每个i,请执行以下操作
- l0 :count[i]
- n0 :l0的大小
- 如果n0 > 1,则
- 对于0到n0-2的范围,请执行以下操作
- 对于i + 1到n0-1的范围,请执行以下操作
- d1 :l0 [j] -l0 [i]
- d2 :l0 [i] -l0 [j] + n
- 如果d1 <=n – 3或d2 <=n – 3,则
- answer :answer – 1
- 返回answer
范例
让我们看以下实现以获得更好的理解 –
from collections import defaultdict
from math import factorial
def nCr(n, i):
if n == 1:
返回1
返回阶乘(n) //阶乘(i) //阶乘(n-i)
def solve(colors):
count = defaultdict(list)
n = len(colors)
for i in range(len(colors)):
count[colors[i]].append(i)
answer = 0
for i in range(2, n+1):
answer += nCr(n, i)
for i in count.keys():
l0 = count[i]
n0 = len(l0)
if n0 > 1:
for i in range(n0-1):
for j in range(i+1, n0):
d1 = l0[j] -l0[i]
d2 = l0[i] -l0[j] + n
if d1 <= n-3 or d2 <= n-3:
answer -=1
return answer
colors = [1,2,3,4]
print(solve(colors))
输入
[1,2,3,4]
输出
11