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 | |
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 | |
D*****3
发帖数: 2683 | 11 ORZ
【在 b*******s 的大作中提到】
: 把0都换成-1，就变成了求一个整数序列里面和为0的最大子串长度
: 复杂度O(n)
|
