สมมติว่าเรามีสตริงไบนารี และเราสามารถสลับสองบิตใดๆ ก็ได้ เราต้องหาจำนวนสวอปขั้นต่ำที่จำเป็นในการจัดกลุ่มทั้งหมดเข้าด้วยกัน
ดังนั้น หากอินพุตเป็น s ="0111001" ผลลัพธ์จะเป็น 1 เนื่องจากเราสามารถทำการสลับเหล่านี้ได้:0111001 -> 1111000
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
- data :=รายการ 0s และ 1s จากสตริงไบนารีที่กำหนด
- ตั้งค่าหนึ่ง :=0, n:=ความยาวของอาร์เรย์ข้อมูล
- สร้างผลรวมอาร์เรย์ของขนาด n และเติมค่านี้ด้วย 0, set summ[0] :=data[0]
- หนึ่ง :=หนึ่ง + ข้อมูล[0]
- สำหรับ i ในช่วง 1 ถึง n – 1
- summ[i] :=summ[i - 1] + data[i]
- หนึ่ง :=หนึ่ง + data[i]
- แทน :=หนึ่ง
- ซ้าย :=0, ขวา :=หนึ่ง – 1
- ขณะขวา
- ถ้าเหลือ 0 แล้ว temp :=summ[right] หรือ temp :=summ[right] – summ[left - 1]
- ans :=ขั้นต่ำของ ans หนึ่ง – ชั่วคราว
- เพิ่มขวาและซ้าย 1
ตัวอย่าง (Python)
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
class Solution(object): def solve(self, s): data = list(map(int, list(s))) 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() s = "0111001" print(ob.solve(s))
อินพุต
"0111001"
ผลลัพธ์
1
