สมมติว่าเรามีอาร์เรย์ A เท่ากับ 0 และ 1 วินาที เราต้องแบ่งอาร์เรย์ออกเป็น 3 ส่วนที่ไม่ว่าง เพื่อให้ส่วนทั้งหมดเหล่านี้แทนค่าไบนารีเดียวกัน หากเป็นไปได้ ให้ส่งคืน [i, j] ใดๆ ที่มี i+1
-
A[0], A[1], ..., A[i] เป็นส่วนแรก;
-
A[i+1], A[i+2], ..., A[j-1] เป็นส่วนที่สอง และ
-
A[j], A[j+1], ..., A[A.length - 1] คือส่วนที่สาม
ทั้งสามส่วนมีค่าไบนารีเท่ากัน หากไม่สามารถทำได้ ให้ส่งคืน [-1, -1]
ดังนั้น หากอินพุตเท่ากับ [0,1,0,1,1] เอาต์พุตจะเป็น [0,4]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดฟังก์ชัน getIdx() ซึ่งจะรับอาร์เรย์ a, ซ้าย, ขวา,
-
ในขณะที่ (ซ้าย <ขวาและ a[ซ้าย] เหมือนกับ 0) ทำ −
-
(เพิ่มขึ้นเหลือ 1)
-
-
ในขณะที่ขวา <(int)a.size() ทำ -
-
ถ้า a[left] ไม่เท่ากับ a[right] ให้คืนค่า -1
-
(เพิ่มขึ้นทางซ้าย 1), (เพิ่มขึ้นทางขวา 1)
-
-
กลับซ้าย - 1
-
จากวิธีหลัก ให้ทำดังต่อไปนี้ −
-
กำหนดอาร์เรย์ ret ขนาด 2 เติมด้วย -1
-
num :=0, n :=ขนาดของ A
-
สำหรับการเริ่มต้น i :=0 เมื่อ i
-
num :=num + 1 เมื่อ (A[i] เท่ากับ 1) มิฉะนั้น 0
-
-
ถ้า num mod 3 ไม่เท่ากับ 0 แล้ว −
-
รีเทิร์น
-
-
ถ้า num เท่ากับ 0 แล้ว −
-
กลับ { 0, 2 }
-
-
req :=num / 3
-
idx :=n - 1
-
สำหรับการเริ่มต้น temp :=0 เมื่อ idx>=0 และ temp
-
temp :=temp + 1 เมื่อ (A[idx] เหมือนกับ 1) มิฉะนั้น 0
-
-
(เพิ่ม idx ขึ้น 1)
-
firstEnd :=getIdx(A, 0, idx)
-
ถ้า firstEnd <0 แล้ว −
-
รีเทิร์น
-
-
SecondEnd :=getIdx(A, firstEnd + 1, idx)
-
ถ้าวินาทีสุดท้าย <0 แล้ว −
-
รีเทิร์น
-
-
กลับ { firstEnd, secondEnd + 1 }
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include <bits/stdc++.h> using namespace std; void print_vector(vector<auto> v){ cout << "["; for(int i = 0; i<v.size(); i++){ cout << v[i] << ", "; } cout << "]"<<endl; } class Solution { public: vector<int> threeEqualParts(vector<int>& A){ vector<int> ret(2, -1); int num = 0; int n = A.size(); for (int i = 0; i < n; i++) { num += (A[i] == 1); } if (num % 3 != 0) return ret; if (num == 0) { return { 0, 2 }; } int req = num / 3; int idx = n - 1; for (int temp = 0; idx >= 0 && temp < req; idx--) { temp += A[idx] == 1; } idx++; int firstEnd = getIdx(A, 0, idx); if (firstEnd < 0) return ret; int secondEnd = getIdx(A, firstEnd + 1, idx); if (secondEnd < 0) return ret; return { firstEnd, secondEnd + 1 }; } int getIdx(vector<int>& a, int left, int right){ while (left < right && a[left] == 0) left++; while (right < (int)a.size()) { if (a[left] != a[right]) return -1; left++; right++; } return left - 1; } }; main(){ Solution ob; vector<int> v = {0,1,0,1,1}; print_vector(ob.threeEqualParts(v)); }
อินพุต
{0,1,0,1,1}
ผลลัพธ์
[1, 4, ]