927. Trisection simulation

 927. Three equal parts

Given a by  0  and  1  Array of components  arr , Divide the array into  3  A non empty part  , Make all these parts represent the same binary value .

If it can be done , Please return whatever  [i, j], among  i+1 < j, thus ：

• arr[0], arr[1], ..., arr[i]  For the first part ;
• arr[i + 1], arr[i + 2], ..., arr[j - 1]  For the second part ;
• arr[j], arr[j + 1], ..., arr[arr.length - 1]  For the third part .
• The binary values represented by these three parts are equal .

If you can't do it , Just go back to  [-1, -1].

Be careful , When considering the binary represented by each part , It should be seen as a whole . for example ,[1,1,0]  Represents... In decimal system  6, Not really.  3. Besides , Leading zero is also Allowed Of , therefore  [0,1,1]  and  [1,1]  Represents the same value .

Example 1：

 Input ：arr = [1,0,1,0,1]
 Output ：[0,3]

Example 2：

 Input ：arr = [1,1,0,1,1]
 Output ：[-1,-1]

Example 3:

 Input ：arr = [1,1,0,0,1]
 Output ：[0,2]

Tips ：

• 3 <= arr.length <= 3 * 10^4
• arr[i]  yes  0  or  1

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/three-equal-parts
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The result of doing the question

success , This problem requires a clear simulation idea

Method ： simulation

1. 0 Because there is a leading 0, So I'm not sure , however 1 It must be able to divide into 3 Share , Here we can judge . Special all 0 return ,[0,n-1]

2. The tail 0 The number of is from the last number to the last 1 after 0 Determined by the number of , these 0 Not a leader 0 Can't erase

 3. With the tail 0 The number of , With 1 The number of , You can separate 3 Share , Finally, compare whether the three synthesized copies are all equal

class Solution {
      public int[] threeEqualParts(int[] arr) {
          int cnt = 0;
          for(int v:arr){
              cnt += v;
          }
          int n = arr.length;
          if(cnt == 0) return new int[]{0,n-1};
          if(cnt%3!=0) return new int[]{-1,-1};
          StringBuilder sb1 = new StringBuilder();
          StringBuilder sb2 = new StringBuilder();
          StringBuilder sb3 = new StringBuilder();

          int zeroCnt = 0;
          for(int i = n-1; i>=0;i--){
              if(arr[i]==1){
                  zeroCnt = n-i-1;
                  break;
              }
          }
          int curr = 0;
          int endZero = 0;
          int[] ans = new int[]{-1,-1};
          for(int i = 0; i < n; i++){
              if(curr <cnt/3||endZero<zeroCnt){
                  if(arr[i]==1){
                      sb1.append("1");
                      ++curr;
                      endZero = 0;
                  }
                  else if(sb1.length()>0) {
                      sb1.append("0");
                      endZero++;
                  }
              }else if(curr <cnt/3*2||endZero<zeroCnt*2){
                  if(ans[0]==-1) ans[0] = i-1;
                  if(arr[i]==1){
                      sb2.append("1");
                      ++curr;
                      endZero = zeroCnt;
                  }
                  else if(sb2.length()>0){
                      sb2.append("0");
                      endZero++;
                  }
              }else{
                  if(ans[1]==-1) ans[1] = i;
                  if(arr[i]==1){
                      sb3.append("1");
                      ++curr;
                  }
                  else if(sb3.length()>0) sb3.append("0");
              }
          }
          return sb1.toString().equals(sb2.toString()) && sb2.toString().equals(sb3.toString())?ans:new int[]{-1,-1};
      }
  }