数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找分割字符串的方法数
假设我们有一个二进制字符串 s，我们可以将 s 分割成 3 个非空字符串 s1、s2、s3，使得 (s1 连接 s2 连接 s3 = s)。我们需要找到 s 可以分割的方式数量，使得 s1、s2 和 s3 中字符 '1' 的数量相同。答案可能非常大，因此返回答案模 10^9+7。
所以，如果输入类似 s = "11101011"，则输出将为 2，因为我们可以将其分割为 "11 | 1010 | 11" 和 "11 | 101 | 011"。
为了解决这个问题，我们将遵循以下步骤
- count := 计算 s 中 1 的数量
- m := 10^9 + 7
- ans := 一个大小为 2 的数组，并填充 0
- 如果 count 模 3 不等于 0，则
- 返回 0
- 否则，当 count 等于 0 时，则
- 返回 (nCr，其中 n 是 s 的大小 -1，r 是 2) 模 m
- left := 0
- right := s 的大小 - 1
- cum_s := 0, cum_e := 0
- 当 cum_s <= count/3 的商 或 cum_e <= count/3 的商 时，执行以下操作
- 如果 s[left] 等于 "1"，则
- cum_s := cum_s + 1
- 如果 s[right] 等于 "1"，则
- cum_e := cum_e + 1
- 如果 cum_s 等于 count/3 的商，则
- ans[0] := ans[0] + 1
- 如果 cum_e 等于 count/3 的商，则
- ans[1] := ans[1] + 1
- left := left + 1
- right := right - 1
- 如果 s[left] 等于 "1"，则
- 返回 (ans[0]*ans[1]) 模 m
让我们看看以下实现以更好地理解
示例
def solve(s):
count = s.count("1")
m = 10**9 + 7
ans = [0, 0]
if count % 3 != 0:
return 0
elif count == 0:
return comb(len(s)-1,2) % m
left = 0
right = len(s)-1
cum_s = 0
cum_e = 0
while(cum_s <= count//3 or cum_e <= count//3):
if s[left] == "1":
cum_s+=1
if s[right] == "1":
cum_e+=1
if cum_s == count//3:
ans[0]+=1
if cum_e == count//3:
ans[1]+=1
left += 1
right -= 1
return (ans[0]*ans[1]) % m
s = "11101011"
print(solve(s))输入
"11101011"
输出
2
更新于: 2021年10月4日
343 次查看
广告