資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告