数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究Python程序查找满足给定条件的彩色顶点子集的数量
假设我们有一个数组colors，表示一个正n边形的颜色。这里这个n边形的每个顶点都被随机地用给定数组中存在的n种不同颜色中的一种颜色着色。我们必须找到多边形顶点的特殊子集的数量，使得这些子集满足以下条件：
- 子集的大小必须至少为二。
- 如果我们从多边形中移除存在于子集中的顶点（这些顶点的相邻边也将被移除），那么剩下的顶点和边形成一些连续的路径。
- 这些路径中都不应该包含两个相同颜色的顶点。
我们必须计算存在此类子集的数量。如果答案太大，则返回结果模10^9 + 7。
因此，如果输入类似于colors = [1,2,3,4]，则输出将为11。
为了解决这个问题，我们将遵循以下步骤：
- count := 一个空映射，其中所有值都将是一个空列表。
- n := colors的大小
- 对于范围从0到colors的大小-1的i，执行以下操作：
- 将i插入到count[colors[i]]的末尾
- answer := 0
- 对于范围从2到n的i，执行以下操作：
- answer := answer + nCr(n, i)
- 对于count的所有键的列表中的每个i，执行以下操作：
- l0 := count[i]
- n0 := l0的大小
- 如果n0 > 1，则执行以下操作：
- 对于范围从0到n0-2的i，执行以下操作：
- 对于范围从i+1到n0 - 1的j，执行以下操作：
- d1 := l0[j] -l0[i]
- d2 := l0[i] -l0[j] + n
- 如果d1 <= n-3 或 d2<= n-3，则执行以下操作：
- answer := answer - 1
- 对于范围从i+1到n0 - 1的j，执行以下操作：
- 对于范围从0到n0-2的i，执行以下操作：
- 返回answer
示例
让我们看看以下实现以更好地理解：
from collections import defaultdict
from math import factorial
def nCr(n, i):
if n==1:
return 1
return factorial(n)//factorial(i)//factorial(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
更新于: 2021年10月25日
88 次浏览
广告