C++の3つの等しい部分

0と1の配列Aが1つあるとすると、これらの部分がすべて同じバイナリ値を表すように、配列を3つの空でない部分に分割する必要があります。それが可能な場合は、i + 1

• A [0]、A [1]、...、A[i]は最初の部分です;

• A [i + 1]、A [i + 2]、...、A [j-1]は2番目の部分であり、

• A [j]、A [j + 1]、...、A[A.length-1]は3番目の部分です。

3つの部分はすべて等しいバイナリ値を持っています。それが不可能な場合は、[-1、-1]を返します。

したがって、入力が[0,1,0,1,1]の場合、出力は[0,4]

これを解決するには、次の手順に従います-

• 関数getIdx（）を定義します。これにより、配列a、左、右、

  が取得されます。

• （左<右およびa [左]は0と同じ）、do-

  • （左に1つ増やします）

• 右<（int）a.size（）、do-

  • a[左]がa[右]と等しくない場合は、-1を返します

  • （左に1つ増やす）、（右に1つ増やす）

• 左に戻る-1

• メインの方法から、次のようにします-

• サイズ2の配列retを定義します。これに-1を入力します

• num：=0、n：=Aのサイズ

• 初期化i：=0の場合、i

  • num：=num + 1（A [i]が1と同じ）の場合、それ以外の場合は0

• num mod 3が0に等しくない場合、-

  • retを返す

• 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の場合、-

  • retを返す

• secondEnd：=getIdx（A、firstEnd + 1、idx）

• secondEnd <0の場合、-

  • retを返す

• {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, ]