企业建站方案,用wordpress编写网站,wordpress shopkeeper,网站建设公司程序文章目录1. 题目2. 解题1. 题目
给定一个由 0 和 1 组成的数组 A#xff0c;将数组分成 3 个非空的部分#xff0c;使得所有这些部分表示相同的二进制值。
如果可以做到#xff0c;请返回任何 [i, j]#xff0c;其中 i1 j#xff0c;这样一来#xff1a;
A[0], A…
文章目录1. 题目2. 解题1. 题目
给定一个由 0 和 1 组成的数组 A将数组分成 3 个非空的部分使得所有这些部分表示相同的二进制值。
如果可以做到请返回任何 [i, j]其中 i1 j这样一来
A[0], A[1], ..., A[i] 组成第一部分 A[i1], A[i2], ..., A[j-1] 作为第二部分 A[j], A[j1], ..., A[A.length - 1]是第三部分。 这三个部分所表示的二进制值相等。
如果无法做到就返回 [-1, -1]。
注意在考虑每个部分所表示的二进制时应当将其看作一个整体。 例如[1,1,0] 表示十进制中的 6而不会是 3。 此外前导零也是被允许的所以 [0,1,1] 和 [1,1] 表示相同的值。
3 A.size 30000
A[i] 0 or A[i] 1示例
样例 1
输入[1,0,1,0,1]
输出[0,3]样例 2
输出[1,1,0,1,1]
输出[-1,-1]https://tianchi.aliyun.com/oj/245867719779445300/277517718521058001 https://leetcode-cn.com/problems/three-equal-parts/
2. 解题
就是检查每个部分尾部的0的个数一样确定开始结束位置见注释
class Solution {
public:/*** param A: an array* return: divide the array into 3 non-empty parts*/vectorint threeEqualParts(vectorint A) {// write your code hereint sum accumulate(A.begin(), A.end(), 0);if(sum%3 ! 0)//1的个数不能整除3return {-1,-1};int i, j, part sum/3, one 0, tail0 0, n A.size();if(part 0)//没有1return {0,2};for(i n-1; i 0; --i){if(A[i] 1)one;else{if(one0)tail0;//第三部分的尾部0个数}if(one part)break;}int mid0 0, start i;//start 为第三部分的可能开始点for(i--; i0 A[i] ! 1; i--){mid0;//第二第三部分中间的0的个数}if(mid0 tail0)//第二部分尾0的个数不能跟第三部分尾0一样多return {-1,-1};start - mid0-tail0;//分一部分前置0给第三部分int count 0;for(i start-1, j n-1; i 0; --i,--j){ // 比较 第二第三部分是否一样if(A[i]1) count;if(A[i] ! A[j])return {-1,-1};if(count part)//1的个数够了跳出break;}mid0 0;int start1 i;//第二分部可能的开始位置for(i--; i0 A[i] ! 1; i--){mid0;//第一第二部分中间的0的个数}if(mid0 tail0)//同上return {-1,-1};count 0;start1 - mid0-tail0;//第二部分开始的位置for(i start1-1, j n-1; i 0; --i,--j){if(A[i] 1) count;if(A[i] ! A[j])return {-1,-1};if(count part)break;}return {start1-1, start};//第一部分结束第三部分开始}
};50ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
