Problem
Given an array A
of 0
s and 1
s, divide the array into 3 non-empty parts such that all of these parts represent the same binary value.
If it is possible, return any [i, j]
with i+1 < j
, such that:
A[0], A[1], ..., A[i]
is the first part;A[i+1], A[i+2], ..., A[j-1]
is the second part, andA[j], A[j+1], ..., A[A.length - 1]
is the third part.- All three parts have equal binary value.
If it is not possible, return [-1, -1]
.
Note that the entire part is used when considering what binary value it represents. For example, [1,1,0]
represents 6
in decimal, not 3
. Also, leading zeros are allowed, so [0,1,1]
and [1,1]
represent the same value.
Example 1:
Input: [1,0,1,0,1] Output: [0,3]
Example 2:
Input: [1,1,0,1,1] Output: [-1,-1]
Note:
3 <= A.length <= 30000
A[i] == 0
orA[i] == 1
Solution:
each part should have the same number of 1 s.
Find the suffix (without leading os) of the last part which should have 1/3 of the total ones.
Time complexity: O(n^2) in theory but close to O(n) in practice
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua, 44 ms class Solution { public: vector<int> threeEqualParts(vector<int>& A) { string s(begin(A), end(A)); int ones = accumulate(begin(A), end(A), 0); if (ones % 3 != 0) return {-1, -1}; if (ones == 0) return {0, A.size() - 1}; ones /= 3; int right = A.size() - 1; while (ones) if (A[right--]) --ones; string suffix(begin(s) + right + 1, end(s)); size_t l = suffix.length(); size_t left = s.find(suffix); if (left == std::string::npos) return {-1, -1}; size_t mid = s.find(suffix, left + l); if (mid == std::string::npos || mid + 2 * l > s.length()) return {-1, -1}; return {left + l - 1, mid + l}; } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment