資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中的三等分
假設我們有一個包含 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]。
因此，如果輸入類似於 [0,1,0,1,1]，則輸出將為 [0,4]
為了解決這個問題，我們將遵循以下步驟 -
定義一個函式 getIdx()，它將接收一個數組 a、left、right，
當 (left < right 且 a[left] 等於 0) 時，執行 -
(將 left 加 1)
當 right < (int)a.size() 時，執行 -
如果 a[left] 不等於 a[right]，則返回 -1
(將 left 加 1)，(將 right 加 1)
返回 left - 1
從主方法執行以下操作 -
定義一個大小為 2 的陣列 ret，並將其填充為 -1
num := 0, n := A 的大小
初始化 i := 0，當 i < n 時，更新 (將 i 加 1)，執行 -
當 (A[i] 等於 1) 時，num := num + 1，否則為 0
如果 num mod 3 不等於 0，則 -
返回 ret
如果 num 等於 0，則 -
返回 { 0, 2 }
req := num / 3
idx := n - 1
初始化 temp := 0，當 idx >= 0 且 temp < req 時，更新 (將 idx 減 1)，執行
當 (A[idx] 等於 1) 時，temp := temp + 1，否則為 0
(將 idx 加 1)
firstEnd := getIdx(A, 0, idx)
如果 firstEnd < 0，則 -
返回 ret
secondEnd := getIdx(A, firstEnd + 1, idx)
如果 secondEnd < 0，則 -
返回 ret
返回 { firstEnd, secondEnd + 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, ]
122 次檢視
