开发者社区> 游客z3jcatjk57fiu> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

每日算法系列【LeetCode 927】三等分

简介: 给定一个由 0 和 1 组成的数组 A,将数组分成 3 个非空的部分,使得所有这些部分表示相同的二进制值。
+关注继续查看

题目描述


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

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

  • 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]。

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

示例1

输入:
[1,0,1,0,1]
输出:
[0,3]

示例2

输入:
[1,1,0,1,1]
输出:
[-1,-1]

提示

  • 3 <= A.length <= 30000
  • A[i] == 0 或 A[i] == 1

题解


这题虽然名义上是个难题,其实基本没有用到什么算法,只是代码实现上略微繁琐了一点。

想象如果这个数组能分成三个子数组,每个子数组表示的数字都相同,那么首先每个子数组中 1 的数量一定要相等!

所以我们先统计 1 的数量,如果它不是 3 的倍数,那么一定不存在划分方式,直接返回无解就行了。如果数量是 0 ,就说明数组全 0 ,那么随便划分都是合理的,任意返回就行了。

接下来将 1 的数量等分为 3 份 ,然后遍历数组,找出 3 个子数组的左右边界(注意这个边界表示的是每个子数组第一个 1 和最后一个 1 的位置)。这时候还没结束,因为最后一个子数组末尾会多出来很多 0 。所以我们需要在前两个子数组后面加上等量的 0 。

最后遍历一遍三个子数组,判断是否完全相等就行了。

听起来是很简单,代码实现的时候还是有几个小细节的。比如求边界的时候,可以利用求余操作,保存到两个数组里,这样写起来美观方便。

代码


c++

class Solution {
    public: 
    vector<int> threeEqualParts(vector<int>& A) { 
        int n = A.size();  
        int cnt1 = accumulate(A.begin(), A.end(), 0);    
        if (cnt1 % 3) return {-1, -1};  
        if (!cnt1) return {0, 2};     
        cnt1 /= 3;    
        int cnt = 0, l[3], r[3];   
        for (int i = 0; i < n; ++i) {    
            if (!A[i]) continue;    
            cnt++;     
            if ((cnt-1)%cnt1 == 0) l[(cnt-1)/cnt1] = i;    
            if (cnt%cnt1 == 0) r[(cnt-1)/cnt1] = i; 
        }      
        for (int i = 0; i < 3; ++i) { 
            r[i] += n - 1 - r[2];  
        }       
        for (int i = 0; i <= r[0]-l[0]; ++i) { 
            if (A[l[1]+i] != A[l[0]+i] || A[l[2]+i] != A[l[0]+i])  
                return {-1, -1};   
        }     
        return {r[0], r[1]+1}; 
    }
};

python

class Solution:   
    def threeEqualParts(self, A: List[int]) -> List[int]:  
        n = len(A)    
        cnt1 = sum(A)    
        if cnt1%3 != 0:   
            return [-1, -1]   
        if cnt1 == 0:     
            return [0, 2]   
        cnt1 //= 3     
        cnt = 0     
        l, r = [0]*3, [0]*3 
        for i in range(n):   
            if A[i] == 0:    
                continue  
                cnt += 1   
                if (cnt-1)%cnt1 == 0:             
                    l[(cnt-1)//cnt1] = i    
                    if cnt%cnt1 == 0:   
                        r[(cnt-1)//cnt1] = i  
                        for i in range(3):   
                            r[i] += n - 1 - r[2]   
                            if A[l[1]:r[1]+1] != A[l[0]:r[0]+1] or 
                            A[l[2]:r[2]+1] != A[l[0]:r[0]+1]:  
                                return [-1, -1]     
                            return [r[0], r[1]+1]

image.png

作者简介:godweiyang知乎同名华东师范大学计算机系硕士在读,方向自然语言处理与深度学习喜欢与人分享技术与知识,期待与你的进一步交流~


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
每日算法系列【LeetCode 329】矩阵中的最长递增路径
给定一个整数矩阵,找出最长递增路径的长度。 对于每个单元格,你可以往上,下,左,右四个方向移动。你不能在对角线方向上移动或移动到边界外(即不允许环绕)。
20 0
每日算法系列【LeetCode 684】冗余连接
在本问题中, 树指的是一个连通且无环的无向图。 输入一个图,该图由一个有着 个节点(节点值不重复 )的树及一条附加的边构成。附加的边的两个顶点包含在 到 中间,这条附加的边不属于树中已存在的边。 结果图是一个以边组成的二维数组。每一个边的元素是一对 ,满足 ,表示连接顶点 和 的无向图的边。 返回一条可以删去的边,使得结果图是一个有着 个节点的树。如果有多个答案,则返回二维数组中最后出现的边。答案边 应满足相同的格式.
13 0
每日算法系列【LeetCode 386】字典序排数
给定一个整数 n, 返回从 1 到 n 的字典顺序。 例如,给定 n = 13,返回 [1,10,11,12,13,2,3,4,5,6,7,8,9] 。 请尽可能的优化算法的时间复杂度和空间复杂度。输入的数据 n 小于等于 5,000,000。
26 0
每日算法系列【LeetCode 825】适龄的朋友
人们会互相发送好友请求,现在给定一个包含有他们年龄的数组,ages[i] 表示第 i 个人的年龄。 当满足以下条件时,A 不能给 B(A、B不为同一人)发送好友请求: age[B] <= 0.5 * age[A] + 7 age[B] > age[A] age[B] > 100 && age[A] < 100 否则,A 可以给 B 发送好友请求。 注意如果 A 向 B 发出了请求,不等于 B 也一定会向 A 发出请求。而且,人们不会给自己发送好友请求。 求总共会发出多少份好友请求?
21 0
每日算法系列【LeetCode 289】生命游戏
根据当前状态,写一个函数来计算面板上细胞的下一个(一次更新后的)状态。下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的,其中细胞的出生和死亡是同时发生的。
15 0
每日算法系列【LeetCode 233】数字 1 的个数
给定一个整数 n,计算所有小于等于 n 的非负整数中数字 1 出现的个数。
27 0
每日算法系列【LeetCode 1053】交换一次的先前排列
给你一个正整数的数组 A(其中的元素不一定完全不同),请你返回可在 一次交换(交换两数字 A[i] 和 A[j] 的位置)后得到的、按字典序排列小于 A 的最大可能排列。
22 0
「leetCode」31-下一个排列⚡️
「leetCode」31-下一个排列⚡️
10 0
leetcode算法67.二进制求和
给你两个二进制字符串,返回它们的和(用二进制表示)。 输入为 非空 字符串且只包含数字 1 和 0。
23 0
【算法千题案例】每日LeetCode打卡——73.最长回文串
📢前言 🌲原题样例:最长回文串 🌻C#方法:排序遍历 🌻Java 方法一:计数 💬总结
58 0
217
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载