สามส่วนที่เท่ากันใน C++

สมมติว่าเรามีอาร์เรย์ 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, ]