สมมติว่าเรามีเลขฐานสองเลขฐานสองและค่า 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,1,0] .
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
เจ :=0
-
ค่า :=0
-
ตอบ :=999999
-
loc :=รายการใหม่
-
สำหรับแต่ละดัชนี i และค่า x เป็น nums ทำ
-
ถ้า 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
-
เจ :=เจ + 1
-
-
ถ้าขนาดของ loc -j เท่ากับ k แล้ว
-
ans :=ขั้นต่ำของ ans และ val
-
-
-
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
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
