当前位置:网站首页>927. 三等分 模拟
927. 三等分 模拟
2022-07-05 05:51:00 【钰娘娘】
927. 三等分
给定一个由
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 * 10^4
arr[i]
是0
或1
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/three-equal-parts
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
做题结果
成功,此题需要比较清晰的模拟思路
方法:模拟
1. 0因为存在前导0,所以不能确定,但是1一定要能够均分为3份,此处可先判断。特别的全0返回,[0,n-1]
2. 尾部0的数目是由最后一个数的遇到最后一个1之后0的个数决定的,这些0不是前导0无法抹去
3. 有了尾部0的个数,有了1的个数,就可以分出3份了,最后比合成的三份是否全等即可
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};
}
}
边栏推荐
- wordpress切换页面,域名变回了IP地址
- Light a light with stm32
- Dichotomy, discretization, etc
- R语言【数据集的导入导出】
- 对for(var i = 0;i < 5;i++) {setTimeout(() => console.log(i),1000)}的深入分析
- Common optimization methods
- js快速将json数据转换为url参数
- 7. Processing the input of multidimensional features
- [cloud native] record of feign custom configuration of microservices
- Implement an iterative stack
猜你喜欢
剑指 Offer 06.从头到尾打印链表
Graduation project of game mall
F - Two Exam(AtCoder Beginner Contest 238)
剑指 Offer 53 - I. 在排序数组中查找数字 I
lxml. etree. XMLSyntaxError: Opening and ending tag mismatch: meta line 6 and head, line 8, column 8
游戏商城毕业设计
Personal developed penetration testing tool Satania v1.2 update
剑指 Offer 09. 用两个栈实现队列
Some common problems in the assessment of network engineers: WLAN, BGP, switch
EOJ 2021.10 E. XOR tree
随机推荐
Chapter 6 data flow modeling - after class exercises
常见的最优化方法
Convolution neural network -- convolution layer
剑指 Offer 58 - II. 左旋转字符串
Sword finger offer 53 - ii Missing numbers from 0 to n-1
LeetCode 0107.二叉树的层序遍历II - 另一种方法
Pointnet++ learning
How to adjust bugs in general projects ----- take you through the whole process by hand
Collection: programming related websites and books
Over fitting and regularization
Palindrome (csp-s-2021-palin) solution
Sword finger offer 06 Print linked list from beginning to end
Reader writer model
卷积神经网络——卷积层
[practical skills] how to do a good job in technical training?
Time complexity and space complexity
Configuration and startup of kubedm series-02-kubelet
In this indifferent world, light crying
The sum of the unique elements of the daily question
[jailhouse article] performance measurements for hypervisors on embedded ARM processors