資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：計算同質子字串的數量
假設我們有一個字串 s，我們需要找到 s 的同質子字串的數量。答案可能非常大，因此返回答案模 10^9+7。當字串的所有字元都相同的時候，該字串被稱為同質字串。
因此，如果輸入像 s = "xyyzzzxx"，則輸出將是 13，因為同質子字串列出如下：
1."x" 出現三次。
"xx" 出現一次。
3. "y" 出現兩次。
"yy" 出現一次。
5. "z" 出現三次。
"zz" 出現兩次。
"zzz" 出現一次。
所以，(3 + 1 + 2 + 1 + 3 + 2 + 1) = 13。
為了解決這個問題，我們將遵循以下步驟：
s := s 連線 "@"
h:= 一個新的對映
prev:= s[0]
c:= 1
對於 s 中從索引 1 到末尾的每個 i，執行以下操作：
如果 prev 與 i 不相同，則
如果 prev*c 存在於 h 中，則
h[prev*c] := h[prev*c] + 1
否則，
h[prev*c]:= 1
c:= 1
如果 prev 與 i 相同，則
c := c + 1
prev := i
fin:= 0
對於 h 中的每個 i，執行以下操作：
t:= i 的大小
k:= 0
當 t 與 0 不相同時，執行以下操作：
k := k + t
t := t - 1
fin := fin + k*h[i]
返回 fin 模 10^9+7
示例
讓我們看看以下實現，以便更好地理解：
def solve(s):
s+="@"
h={}
prev=s[0]
c=1
for i in s[1:]:
if prev!=i:
if prev*c in h:
h[prev*c]+=1
else:
h[prev*c]=1
c=1
if prev == i:
c += 1
prev = i
fin=0
for i in h:
t=len(i)
k=0
while t!=0:
k+=t
t-=1
fin+=k*h[i]
return fin % 1000000007
s = "xyyzzzxx"
print(solve(s))輸入
"xyyzzzxx"
輸出
13
更新於: 2021年10月6日
339 次瀏覽
廣告