f*********d
发帖数: 140 | 1 Longest subarray with equal number of 1 and 0 | c**1
发帖数: 71 | 2 array. arr[x] is the first offset you see x more 1 than 0. note x can be
negative so you need to allocate an array of 2 * input_size and set [0] at
the middle of the array.
scan input, each step get how many more 1 than 0 you have so far. and if
the corresponding arr item is already initialized, length is the diff of
two offset. max of all such length is what you want. | f*********d
发帖数: 140 | 3 Not totally understand. Could you please give a simple example? Thanks a lot!
be
【在 c**1 的大作中提到】
: array. arr[x] is the first offset you see x more 1 than 0. note x can be
: negative so you need to allocate an array of 2 * input_size and set [0] at
: the middle of the array.
: scan input, each step get how many more 1 than 0 you have so far. and if
: the corresponding arr item is already initialized, length is the diff of
: two offset. max of all such length is what you want.
| d*k
发帖数: 207 | 4 smart!
be
【在 c**1 的大作中提到】
: array. arr[x] is the first offset you see x more 1 than 0. note x can be
: negative so you need to allocate an array of 2 * input_size and set [0] at
: the middle of the array.
: scan input, each step get how many more 1 than 0 you have so far. and if
: the corresponding arr item is already initialized, length is the diff of
: two offset. max of all such length is what you want.
| f*********d
发帖数: 140 | 5 Got it. Really Nice Idea!
Just being confused by the words~
be
【在 c**1 的大作中提到】
: array. arr[x] is the first offset you see x more 1 than 0. note x can be
: negative so you need to allocate an array of 2 * input_size and set [0] at
: the middle of the array.
: scan input, each step get how many more 1 than 0 you have so far. and if
: the corresponding arr item is already initialized, length is the diff of
: two offset. max of all such length is what you want.
| s****p
发帖数: 124 | 6 You meant to convert 0 to -1, right? Otherwise, it won't work, because for i
< j, if there are same numbers of 1s and 0s between them, C[i] and C[j] won
't map to the same bucket, because C[j] = C[i] + (j-i)/2. | s***5
发帖数: 2136 | 7 O(n) space, O(n) time.
bool equal_bits(bool input[], int n, int& sta, int& end) {
// check if all elements are all 1's or all 0's
int sum = 0;
for(int i = 0; i < n; i++)
sum += input[i];
if(sum == 0 || sum == n) return false;
unordered_map freq;
int counter = 0, maxL = 0;
freq[counter] = -1;
for(int i = 0; i < n; i++) {
if(input[i])
counter++;
else
counter--;
if(freq.count(counter) == 0)
freq[counter] = i;
else {
sta = freq[counter]+1;
end = i;
maxL = max(maxL,i-freq[counter]);
}
}
return true;
} | f*********d
发帖数: 140 | 8 MARK
THANKS
【在 s***5 的大作中提到】
: O(n) space, O(n) time.
: bool equal_bits(bool input[], int n, int& sta, int& end) {
: // check if all elements are all 1's or all 0's
: int sum = 0;
: for(int i = 0; i < n; i++)
: sum += input[i];
: if(sum == 0 || sum == n) return false;
: unordered_map freq;
: int counter = 0, maxL = 0;
: freq[counter] = -1;
| m********c
发帖数: 105 | | g***9
发帖数: 159 | 10 遵照大牛的思路写了个实现：
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
int getMaxEvenSeq(vector &v) {
int n = v.size();
if (n < 2) {
return 0;
}
vector pos(2*n+1, -1);
int zeros, ones;
int i, t, diff, index, dis, ans;
zeros = ones = 0;
ans = 0;
for (i = 0; i < n; i++) {
t = v[i];
if (t == 0) {
zeros++;
}
else {
ones++;
}
diff = ones - zeros;
index = diff;
if (index < 0) {
index = (-index) + n;
}
if (pos[index] != -1) {
dis = i - pos[index];
ans = std::max(ans, dis);
}
else {
pos[index] = i;
}
}
return ans;
}
void Test() {
//int a[] = {1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0};
int a[] = {0, 0, 0, 1, 0, 0, 0};
vector v(a, a+sizeof(a)/sizeof(int));
int maxlen = getMaxEvenSeq(v);
cout << maxlen << endl;
}
int main() {
Test();
return 0;
} | | | r*c
发帖数: 167 | 11 这是随手写来的吧，牛啊！
unordered_map freq; --> unordered_map freq;
【在 s***5 的大作中提到】
: O(n) space, O(n) time.
: bool equal_bits(bool input[], int n, int& sta, int& end) {
: // check if all elements are all 1's or all 0's
: int sum = 0;
: for(int i = 0; i < n; i++)
: sum += input[i];
: if(sum == 0 || sum == n) return false;
: unordered_map freq;
: int counter = 0, maxL = 0;
: freq[counter] = -1;
| s**x
发帖数: 7506 | 12 found this
http://www.dsalgo.com/2013/03/longest-subarray-with-equal-numbe
Longest subarray with equal number of ones and zeros
Problem
You are given an array of 1's and 0's only. Find the longest subarray which
contains equal number of 1's and 0's.
Solution
We will keep a running sum of "no of ones minus no of zeros" for each index
of the array. For any two indices, if the running sum is equal, that means
there are equal number of ones and zeros between these two indices. We will
store the running sum in an array such that it acts like a hash map where
key is the running sum and value is the leftmost index of that running sum
to appear. The running sum can vary from -n to +n. So we need an array of
length 2*n+1. So for any index we can check whether this sum has occurred
before and if yes what is the left most index for it. We can do this in O(1)
time by maintaining the array. So at any index we can find the longest
equal subarray till that point. We will compare it with a maximum value and
update the maximum accordingly. So the overall complexity for the process is
O(n)
Code
public class MaxSubarrayEqualOnesZeros
{
public static void main(String[] args)
{
int[] arr =
{ 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1,
0, 1, 1, 0, 1, 0, 0, 0 };
printMaxSubarray(arr);
}
private static void printMaxSubarray(int[] arr)
{
Integer[] diffMap = new Integer[arr.length * 2 + 1];
diffMap[arr.length] = -1;
int sum = 0;
int maxLength = 0;
int maxStart = -1;
int maxEnd = -1;
for (int i = 0; i < arr.length; ++i)
{
if (arr[i] == 0)
sum -= 1;
else
sum += 1;
Integer prevIndex = diffMap[arr.length + sum];
if (prevIndex == null)
diffMap[arr.length + sum] = i;
else
{
if (i - prevIndex > maxLength)
{
maxLength = i - prevIndex;
maxStart = prevIndex + 1;
maxEnd = i;
}
}
}
System.out.println("indices (" + maxStart + "," + maxEnd + ")");
System.out.println("length=" + maxLength);
}
} | c**1
发帖数: 71 | 13 in leetcode, there is one question asking for longest substring with matched
parens. it is similar to this post but harder. | d****n
发帖数: 233 | 14 void printMaxSubarray(int[] arr)
{
int[] zeroPos = new int[arr.Length + 1];
int[] onePos = new int[arr.Length + 1];
int zeroCount = 0;
int oneCount = 0;
int start = 0;
int max = 0;
for (int i = 0; i < arr.Length; ++i)
{
if (arr[i] == 1)
{
++oneCount;
onePos[oneCount] = i;
if (oneCount <= zeroCount)
{
max = oneCount;
start = zeroPos[zeroCount - oneCount];
}
}
else
{
++zeroCount;
zeroPos[zeroCount] = i;
if (zeroCount <= oneCount)
{
max = zeroCount;
start = onePos[oneCount-zeroCount];
}
}
}
Console.WriteLine("indices (" + start + "," + (2 * max -1)+ ")");
Console.WriteLine("Length=" + 2*max);
}
which
index
will
【在 s**x 的大作中提到】
: found this
: http://www.dsalgo.com/2013/03/longest-subarray-with-equal-numbe
: Longest subarray with equal number of ones and zeros
: Problem
: You are given an array of 1's and 0's only. Find the longest subarray which
: contains equal number of 1's and 0's.
: Solution
: We will keep a running sum of "no of ones minus no of zeros" for each index
: of the array. For any two indices, if the running sum is equal, that means
: there are equal number of ones and zeros between these two indices. We will
| d****n
发帖数: 233 | 15 void printMaxSubarray2(int[] arr)
{
Stack stack = new Stack();
int max = 0;
int start = 0;
for (int i = 0; i < arr.Length; ++i)
{
if (stack.Count > 0 && (arr[stack.Peek()] + arr[i]) == 1)
{
stack.Pop();
start = stack.Count > 0 ? stack.Peek() : -1;
max = Math.Max(max, i - start);
}
else
{
stack.Push(i);
}
}
Console.WriteLine("indices (" + (start+1) + "," + ( max - 1) + "
)");
Console.WriteLine("Length=" + max);
}
【在 d****n 的大作中提到】
: void printMaxSubarray(int[] arr)
: {
: int[] zeroPos = new int[arr.Length + 1];
: int[] onePos = new int[arr.Length + 1];
: int zeroCount = 0;
: int oneCount = 0;
: int start = 0;
: int max = 0;
: for (int i = 0; i < arr.Length; ++i)
: {
| l**********1
发帖数: 415 | |
|
