数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Python程序：查找K个连续1所需的最小相邻交换次数
假设我们有一个二进制数组 nums 和一个值 k。在一次移动中，我们可以选择两个相邻的索引并交换它们的值。我们必须找到所需的最小移动次数，以便 nums 具有 k 个连续的 1。
因此，如果输入类似于 nums = [1,0,0,1,0,1,0,1]，k = 3，则输出将为 2，因为在一个交换中我们可以将数组从 [1,0,0,1,0,1,0,1] 变成 [1,0,0,0,1,1,0,1]，然后 [1,0,0,0,1,1,1,0]。
为了解决这个问题，我们将遵循以下步骤：
j := 0
val := 0
ans := 999999
loc := 一个新的列表
对于每个索引 i 和 nums 中的值 x，执行以下操作：
如果 x 不为零，则
将 i 插入到 loc 的末尾
m := (j + loc 的大小 - 1) / 2 的商
val := val + loc[-1] - loc[m] - (loc 的大小 - j) / 2 的商
如果 loc 的长度 - j > k，则
m := (j + loc 的大小) / 2 的商
val := val - loc[m] - loc[j] - (loc 的大小 - j) / 2 的商
j := j + 1
如果 loc 的大小 - j 等于 k，则
ans := ans 和 val 的最小值
返回 ans
示例
让我们看看以下实现以获得更好的理解
def solve(nums, k):
j = val = 0
ans = 999999
loc = []
for i, x in enumerate(nums):
if x:
loc.append(i)
m = (j + len(loc) - 1)//2
val += loc[-1] - loc[m] - (len(loc)-j)//2
if len(loc) - j > k:
m = (j + len(loc))//2
val -= loc[m] - loc[j] - (len(loc)-j)//2
j += 1
if len(loc)-j == k:
ans = min(ans, val)
return ans
nums = [1,0,0,1,0,1,0,1]
k = 3
print(solve(nums, k))输入
[1,0,0,1,0,1,0,1], 3
输出
2
更新于： 2021年10月7日
323 次浏览
广告