boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - find longest subarray with the equal number of 0's, 1's
相关主题
讨论个subarray sum的变种问题
INTERVIEW会假定你见过问的问题吗?
Random Array number, Find longest consecutive sequence
Rotating an array in place
这个怎么弄?
longest subarray with numbers arranged as a seq
liverampOA题目
问一道amazon的Onsite题
careercup上看的一道题
上一算法面试题
相关话题的讨论汇总
话题: int话题: startindex话题: subarray话题: length话题: endindex
进入JobHunting版参与讨论
1 (共1页)
d********w
发帖数: 363
1
Given an array of 0's and 1's. only, find the maximum length of the subarray
such that the number of 0's and 1's in that subarray are equal.
S******1
发帖数: 269
2
// Find the longest subarray with equal 1 and 0.
public static int[] longestSub(int[] inputArray) {
int length = inputArray.length;
int[][] record = new int[length][length];
//Initial
for (int i = 0; i < length; i++)
if (inputArray[i] == 1)
record[i][i] = 1;
else
record[i][i] = -1;
for (int i = 0; i < length; i++) {
for (int j = i; j < length; j++) {
if (i < j)
if (inputArray[j] == 1)
record[i][j] = record[i][j - 1] + 1;
else
record[i][j] = record[i][j - 1] - 1;
}
}
int startIndex = -1;
int endIndex = -1;
for (int i = 0; i < length; i++) {
for (int j = length - 1; j >= i; j--) {
if (record[i][j] == 0) {
startIndex = i;
endIndex = j;
break;
}
}
if (startIndex != -1 || endIndex != -1)
break;
}
int[] result = null;
if (startIndex != -1 || endIndex != -1) {
result = new int[endIndex - startIndex + 1];
for (int i = startIndex; i <= endIndex; i++)
result[i - startIndex] = inputArray[i];
}
return result;
}
public static void main(String[] args) {
int[] array = { 1, -1, 1, -1, 1, -1 };
int[] result = longestSub(array);
if(result!=null)
for (int i = 0; i < result.length; i++)
System.out.println(result[i]);
else
System.out.println("No such subarray exist");
}
b*******s
发帖数: 5216
3
把0都换成-1,就变成了求一个整数序列里面和为0的最大子串长度
复杂度O(n)
l*****a
发帖数: 14598
4
你说的这个要额外的空间吗?
不要的话怎么做,谢谢

【在 b*******s 的大作中提到】
: 把0都换成-1,就变成了求一个整数序列里面和为0的最大子串长度
: 复杂度O(n)

l*****a
发帖数: 14598
5
你说的这个要额外的空间吗?
不要的话怎么做,谢谢

【在 b*******s 的大作中提到】
: 把0都换成-1,就变成了求一个整数序列里面和为0的最大子串长度
: 复杂度O(n)

b******n
发帖数: 4509
6
这个方法好

【在 b*******s 的大作中提到】
: 把0都换成-1,就变成了求一个整数序列里面和为0的最大子串长度
: 复杂度O(n)

r*****b
发帖数: 8
7
需要额外空间
g*********s
发帖数: 1782
8
how?

【在 b*******s 的大作中提到】
: 把0都换成-1,就变成了求一个整数序列里面和为0的最大子串长度
: 复杂度O(n)

i**********e
发帖数: 1145
9
I think your method is more complicated than is needed.
The problem has a constraint that only 0's and 1's exist in the array.
We could use two counters to keep track of number of 0's and 1's met so far, and do a one-pass traverse across the array.
The length of the maximum size contiguous array with equal number of 0's and 1's must be:
2 * min( count of 0's, count of 1's ).
I know, it might seem too simple to be true, but sometimes being simple is also a virtue.
一些常见面试题的答案与总结 -
http://www.ihas1337code.com

【在 b*******s 的大作中提到】
: 把0都换成-1,就变成了求一个整数序列里面和为0的最大子串长度
: 复杂度O(n)

s********y
发帖数: 161
10
楼上 ??
0 0 1 1 1 1 1 0
D*****3
发帖数: 2683
11
ORZ

【在 b*******s 的大作中提到】
: 把0都换成-1,就变成了求一个整数序列里面和为0的最大子串长度
: 复杂度O(n)

1 (共1页)
进入JobHunting版参与讨论
相关主题
上一算法面试题
最近变硬那家的面经
贡献一个朋友在Google的面题一枚。
longest repeated substring怎么做?(亚麻刚刚被问到的题)
来道难一点的题
one amazon interview problem
Longest subarray with equal number of 1 and 0
问一道题(7)
Linkedin八月onsite面经
flag新题
相关话题的讨论汇总
话题: int话题: startindex话题: subarray话题: length话题: endindex