数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python 中查找二进制列表中和为 k 的子列表数量的程序
假设我们有一个包含 0 或 1 的二进制列表。我们还有一个名为 k 的输入，我们需要找到和等于 k 的子列表的数量。
因此，如果输入类似于 nums = [1, 0, 0, 1, 1, 1, 0, 1] k = 3，则输出将为 8，因为子列表为 [1,0,0,1,1]、[0,0,1,1,1]、[0,0,1,1,1,0]、[0,1,1,1]、[0,1,1,1,0]、[1,1,1]、[1,1,1,0] [1,1,0,1]。
为了解决这个问题，我们将遵循以下步骤 -
- sums := 一个最初包含键为 0 值为 1 的映射
- r_sum := 0
- ans := 0
- 对于 nums 中的每个 x，执行
- r_sum := r_sum + x
- ans := ans + (sums[r_sum - k] 如果 (r_sum - k) 存在，否则为 0)
- sums[r_sum] := 1 + (sums[r_sum - k] 如果 (r_sum - k) 存在，否则为 0)
- 返回 ans
示例
让我们看看以下实现以获得更好的理解 -
def solve(nums, k):
sums = {0: 1}
r_sum = 0
ans = 0
for x in nums:
r_sum += x
ans += sums.get(r_sum - k, 0)
sums[r_sum] = sums.get(r_sum, 0) + 1
return ans
nums = [1, 0, 0, 1, 1, 1, 0, 1]
k = 3
print(solve(nums, k))输入
[1, 0, 0, 1, 1, 1, 0, 1], 3
输出
8
更新于: 2021 年 10 月 16 日
150 次查看
广告