LeetCode_数组_困难_927.三等分

﹏ヽ暗。殇╰゛Y 2023-10-07 20:08 41阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给定一个由 0 和 1 组成的数组 arr ，将数组分成 3 个非空的部分 ，使得所有这些部分表示相同的二进制值。

如果可以做到，请返回任何 \[i, j\]，其中 i + 1 < j，这样一来：

arr\[0\], arr\[1\], …, arr\[i\] 为第一部分；  
arr\[i + 1\], arr\[i + 2\], …, arr\[j - 1\] 为第二部分；  
arr\[j\], arr\[j + 1\], …, arr\[arr.length - 1\] 为第三部分。  
这三个部分所表示的二进制值相等。  
如果无法做到，就返回 \[-1, -1\]。

注意，在考虑每个部分所表示的二进制时，应当将其看作一个整体。例如，\[1,1,0\] 表示十进制中的 6，而不会是 3。此外，前导零也是被允许的，所以 \[0,1,1\] 和 \[1,1\] 表示相同的值。

**示例 1：**  
输入：arr = \[1,0,1,0,1\]  
输出：\[0,3\]

**示例 2：**  
输入：arr = \[1,1,0,1,1\]  
输出：\[-1,-1\]

**示例 3：**  
输入：arr = \[1,1,0,0,1\]  
输出：\[0,2\]

**提示：**  
3 <= arr.length <= 3 \* 104  
arr\[i\] 是 0 或 1

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/three-equal-parts

## 2.思路 ##

（1）将 1 的数量三等分  
思路参考[本题官方题解][Link 1]

① 用变量 cnt 来记录数组 arr 中 1 的个数，遍历数组 arr 求出 cnt 后，对其进行如下判断：  
1）如果 cnt 不是 3 的倍数，那么不可能三等分，直接返回 \[-1,-1\]；  
2）如果 cnt 为 0，则说明数组 arr 中的元素全部为 0，直接返回 \[0, arr.length - 1\]

② 用变量 partial = cnt / 3 表示三等分中每个部分 1 的个数，并且依次使用 first、second、third 来表示数组 arr 中第一个 1 出现的下标、第 partial + 1 个 1 出现的下标、第 2 \* partial + 1 个 1 出现的下标；

③ 设 len 为二进制值的长度，判断 \[first, first + len)、\[second, second + len)、\[third, third + len) 所表示的二进制是否相同，如果相同，则返回 \[first + len - 1, second + len\]；否则，返回 \[-1, -1\]；

## 3.代码实现（Java） ##

//思路1————将 1 的数量三等分
    class Solution {
        
        public int[] threeEqualParts(int[] arr) {
        
            // cnt 记录数组 arr 中 1 的个数
            int cnt = 0;
            int length = arr.length;
            for (int digit : arr) {
        
                cnt += digit;
            }
            if (cnt % 3 != 0) {
        
                // 1 的个数不为 3 的倍数时，不可能等分
                return new int[]{
        -1, -1};
            } else if (cnt == 0) {
        
                //数组 arr 中的个数全为 0
                return new int[]{
        0, length - 1};
            }
            // partial 表示三等分中每个部分 1 的个数
            int partial = cnt / 3;
            // first 记录数组 arr 中第一个 1 出现的下标
            int first = 0;
            // second 记录第 partial + 1 个 1 出现的下标
            int second = 0;
            // third 记录第 2 * partial + 1 个 1 出现的下标
            int third = 0, cur = 0;
            for (int i = 0; i < length; i++) {
        
                if (arr[i] == 1) {
        
                    if (cur == 0) {
        
                        first = i;
                    } else if (cur == partial) {
        
                        second = i;
                    } else if (cur == 2 * partial) {
        
                        third = i;
                    }
                    cur++;
                }
            }
            // len 为二进制值的长度
            int len = length - third;
            //判断 [first, first + len)、[second, second + len)、[third, third + len) 所表示的二进制是否相同
            if (first + len <= second && second + len <= third) {
        
                int i = 0;
                while (third + i < length) {
        
                    if (arr[first + i] != arr[second + i] || arr[first + i] != arr[third + i]) {
        
                        return new int[]{
        -1, -1};
                    }
                    i++;
                }
                return new int[]{
        first + len - 1, second + len};
            } else {
        
                return new int[]{
        -1, -1};
            }
        }
    }

[Link 1]: https://leetcode.cn/problems/three-equal-parts/solution/san-deng-fen-by-leetcode-solution-3l2y/