สมมติว่าเรามีสตริงไบนารี เราต้องหาจำนวนการแลกเปลี่ยนขั้นต่ำที่จำเป็นในการจัดกลุ่ม 1 อันทั้งหมดเข้าด้วยกันในตำแหน่งใดก็ได้ในสตริง ดังนั้นหากอินพุตเป็นเหมือน "10101001101" เอาต์พุตจะเป็น 3 วิธีแก้ปัญหาที่เป็นไปได้คือ "00000111111"
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
data :=รายการบิตจากสตริงที่กำหนด
-
ตั้งค่าหนึ่ง :=0, n:=ความยาวของ data array
-
สร้างผลรวมอาร์เรย์ของขนาด n และเติมสิ่งนี้ด้วย 0, set summ[0] :=data[0]
-
หนึ่ง :=หนึ่ง + ข้อมูล[0]
-
สำหรับฉันอยู่ในช่วง 1 ถึง n – 1
-
summ[i] :=summ[i - 1] + data[i]
-
หนึ่ง :=หนึ่ง + data[i]
-
-
ตอบ :=หนึ่ง
-
ซ้าย :=0, ขวา :=หนึ่ง – 1
-
ในขณะที่ขวา
-
ถ้าเหลือ 0 แล้ว temp :=summ[right] ไม่เช่นนั้น temp :=summ[right] –
- รวม[ซ้าย - 1]
-
ans :=ขั้นต่ำของ ans หนึ่ง – temp
-
เพิ่มขวาและซ้าย 1
-
-
กลับมาอีกครั้ง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution(object):
def solve(self, data):
data = list(map(int, list(data)))
one = 0
n = len(data)
summ=[0 for i in range(n)]
summ[0] = data[0]
one += data[0]
for i in range(1,n):
summ[i] += summ[i-1]+data[i]
one += data[i]
ans = one
left = 0
right = one-1
while right <n:
if left == 0:
temp = summ[right]
else:
temp = summ[right] - summ[left-1]
ans = min(ans,one-temp)
right+=1
left+=1
return ans
ob = Solution()
print(ob.solve("10101001101")) อินพุต
"10101001101"
ผลลัพธ์
3
