0과 1로 구성된 하나의 배열 A가 있다고 가정하고 배열을 비어 있지 않은 세 부분으로 나누어 이 모든 부분이 동일한 이진 값을 나타내도록 해야 합니다. 가능한 경우 i+1
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]을 반환합니다.
따라서 입력이 [0,1,0,1,1]과 같으면 출력은 [0,4]
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
getIdx() 함수를 정의하면 a, left, right,
동안 (left
(왼쪽으로 1씩 증가)
오른쪽 <(int)a.size() 동안 수행 -
[left]가 [right]와 같지 않으면 -1을 반환합니다.
(왼쪽으로 1증가), (오른쪽으로 1증가)
왼쪽으로 돌아가기 - 1
주요 방법에서 다음을 수행하십시오 -
크기가 2인 배열 ret를 정의하고 이것을 -1로 채웁니다.
num :=0, n :=A의 크기
initialize i :=0의 경우, i
num :=num + 1일 때 (A[i]가 1과 같을 때), 그렇지 않으면 0
num mod 3이 0과 같지 않으면 -
리턴 렛
num이 0과 같으면 -
반환 { 0, 2 }
요청 :=숫자 / 3
idx :=n - 1
initialize temp :=0의 경우 idx>=0이고 temp
temp :=temp + 1일 때 (A[idx]가 1과 같을 때), 그렇지 않으면 0
(idx를 1씩 증가)
firstEnd :=getIdx(A, 0, idx)
firstEnd <0이면 -
리턴 렛
secondEnd :=getIdx(A, firstEnd + 1, idx)
secondEnd <0이면 -
리턴 렛
{ 첫 번째 끝, 두 번째 끝 + 1 }
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<int> threeEqualParts(vector<int>& A){
vector<int> ret(2, -1);
int num = 0;
int n = A.size();
for (int i = 0; i < n; i++) {
num += (A[i] == 1);
}
if (num % 3 != 0)
return ret;
if (num == 0) {
return { 0, 2 };
}
int req = num / 3;
int idx = n - 1;
for (int temp = 0; idx >= 0 && temp < req; idx--) {
temp += A[idx] == 1;
}
idx++;
int firstEnd = getIdx(A, 0, idx);
if (firstEnd < 0)
return ret;
int secondEnd = getIdx(A, firstEnd + 1, idx);
if (secondEnd < 0)
return ret;
return { firstEnd, secondEnd + 1 };
}
int getIdx(vector<int>& a, int left, int right){
while (left < right && a[left] == 0)
left++;
while (right < (int)a.size()) {
if (a[left] != a[right])
return -1;
left++;
right++;
}
return left - 1;
}
};
main(){
Solution ob;
vector<int> v = {0,1,0,1,1};
print_vector(ob.threeEqualParts(v));
} 입력
{0,1,0,1,1} 출력
[1, 4, ]
