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