最近有3D /LED TV 的deal么？# Living
m*g
1 楼
如题，例子：[0,1,1,1,1,0,0,1], and the result should be [1,1,0,0]
有没有O(n)runtime and O(1) space的solution？
谢谢！
有没有O(n)runtime and O(1) space的solution？
谢谢！
s*i
2 楼
有关注的么？去年BF前sear有个sony 46寸的deal，今年会再来么？
s*e
3 楼
dp题，我的思路，大家看看对不对
O(n)runtime and O(n) space的solution:
create an array of length n, len[n], len[i] represent the length of subarray
which has equal number of 1 and 0 ending at index i. Initially, set all the
element len[] to be 0.
len[i] = len[i - 1] + 2 if arr[i] = 1 - arr[i - len[i - 1] - 1]
len[i] = 0 otherwise
then scan array len[], find out the largest one
optimized solution, O(n)runtime and O(1) space的solution:
actaully, we do not need to keep array len[] since len[i] only depends on
len[i - 1], for each i, if we know len[i - 1] we can get len[i], we need
another two variables maxSubarrayLen and maxEndingIndex to record the max
length of subarray and the ending index of this subarray respectively
O(n)runtime and O(n) space的solution:
create an array of length n, len[n], len[i] represent the length of subarray
which has equal number of 1 and 0 ending at index i. Initially, set all the
element len[] to be 0.
len[i] = len[i - 1] + 2 if arr[i] = 1 - arr[i - len[i - 1] - 1]
len[i] = 0 otherwise
then scan array len[], find out the largest one
optimized solution, O(n)runtime and O(1) space的solution:
actaully, we do not need to keep array len[] since len[i] only depends on
len[i - 1], for each i, if we know len[i - 1] we can get len[i], we need
another two variables maxSubarrayLen and maxEndingIndex to record the max
length of subarray and the ending index of this subarray respectively
s*n
4 楼
有问题啊：比如01111000，访问最后一个0
s*e
5 楼
恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，keep
ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
subarray时，判断是否可以跟previous合并，还是O(1)space的
【在 s******n 的大作中提到】
: 有问题啊：比如01111000，访问最后一个0
ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
subarray时，判断是否可以跟previous合并，还是O(1)space的
【在 s******n 的大作中提到】
: 有问题啊：比如01111000，访问最后一个0
s*n
6 楼
不是O(1)space的吧，要判断和previous能否合并，要不就保留以前的结果space>O(1)
，要不重新查time>O(n)。
【在 s**********e 的大作中提到】
: 恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，keep
: ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
: subarray时，判断是否可以跟previous合并，还是O(1)space的
，要不重新查time>O(n)。
【在 s**********e 的大作中提到】
: 恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，keep
: ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
: subarray时，判断是否可以跟previous合并，还是O(1)space的
s*e
7 楼
不需要保留以前的所有结果，只需要记录下previous就可以，扫描的同时更新previous
s*n
8 楼
不太明白，你写个例子或者程序
previous
【在 s**********e 的大作中提到】
: 不需要保留以前的所有结果，只需要记录下previous就可以，扫描的同时更新previous
previous
【在 s**********e 的大作中提到】
: 不需要保留以前的所有结果，只需要记录下previous就可以，扫描的同时更新previous
s*e
9 楼
public static void longestSubarray(int[] arr){
int prevSubarrayLen = 0;
int preSubarrayEndingIndex = -1;
int longestLen = 0;
int longestEndingIndex = -1;
int preLen = 0;
for(int i=1;i
preLen += 2;
if(i-preLen == preSubarrayEndingIndex)
preLen += prevSubarrayLen;
if(preLen > longestLen){
longestLen = preLen;
longestEndingIndex = i;
}
}else if(preLen > 0){
prevSubarrayLen = preLen;
preSubarrayEndingIndex = i - 1;
preLen = 0;
}
}
System.out.println(
"start index："+(longestEndingIndex - longestLen + 1) +
" end index："+ longestEndingIndex +
" length："+ longestLen);
}
int prevSubarrayLen = 0;
int preSubarrayEndingIndex = -1;
int longestLen = 0;
int longestEndingIndex = -1;
int preLen = 0;
for(int i=1;i
preLen += 2;
if(i-preLen == preSubarrayEndingIndex)
preLen += prevSubarrayLen;
if(preLen > longestLen){
longestLen = preLen;
longestEndingIndex = i;
}
}else if(preLen > 0){
prevSubarrayLen = preLen;
preSubarrayEndingIndex = i - 1;
preLen = 0;
}
}
System.out.println(
"start index："+(longestEndingIndex - longestLen + 1) +
" end index："+ longestEndingIndex +
" length："+ longestLen);
}
s*n
10 楼
感觉有问题，在扩展当前的subarray的时候，因为当前subarray的首端-1，会冲掉
preSubarray，不能单用一个变量来存presubarray。
【在 s**********e 的大作中提到】
: public static void longestSubarray(int[] arr){
: int prevSubarrayLen = 0;
: int preSubarrayEndingIndex = -1;
: int longestLen = 0;
: int longestEndingIndex = -1;
: int preLen = 0;
: for(int i=1;i
: preLen += 2;
: if(i-preLen == preSubarrayEndingIndex)
preSubarray，不能单用一个变量来存presubarray。
【在 s**********e 的大作中提到】
: public static void longestSubarray(int[] arr){
: int prevSubarrayLen = 0;
: int preSubarrayEndingIndex = -1;
: int longestLen = 0;
: int longestEndingIndex = -1;
: int preLen = 0;
: for(int i=1;i
: preLen += 2;
: if(i-preLen == preSubarrayEndingIndex)
e*e
11 楼
你这个办法应该不行。
想0101010101010101010101
这样的你方法好像就不对。
想0101010101010101010101
这样的你方法好像就不对。
s*e
12 楼
没看明白，能不能给个反例？
【在 s******n 的大作中提到】
: 感觉有问题，在扩展当前的subarray的时候，因为当前subarray的首端-1，会冲掉
: preSubarray，不能单用一个变量来存presubarray。
【在 s******n 的大作中提到】
: 感觉有问题，在扩展当前的subarray的时候，因为当前subarray的首端-1，会冲掉
: preSubarray，不能单用一个变量来存presubarray。
s*n
13 楼
其实有一邪招：用原数组作为DP用，把0/1放最高位，最后恢复。
e*e
14 楼
这个题目不要DP。
比如如下的数组
0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
求每个位置的和(就是1 的数目）
0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
求每个偶数位置需要的1的数字（有相同的0,1）
0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
求两组的差
0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
找距离最远的两个一样的数字
2,从4,16
注意查查边缘，因为有可能答案是从一个奇数位到另外一个奇数位置。
不过这个答案肯定会包含一个最大的从偶数位到偶数位的。
就是0,0,1,1,0,0,0,0,1,1,1,1
比如如下的数组
0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
求每个位置的和(就是1 的数目）
0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
求每个偶数位置需要的1的数字（有相同的0,1）
0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
求两组的差
0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
找距离最远的两个一样的数字
2,从4,16
注意查查边缘，因为有可能答案是从一个奇数位到另外一个奇数位置。
不过这个答案肯定会包含一个最大的从偶数位到偶数位的。
就是0,0,1,1,0,0,0,0,1,1,1,1
e*e
15 楼
上面我的办法稍微改动一下，就是O(N) O(1)space的solution.
H*r
16 楼
O(1)space 是难点
【在 e*****e 的大作中提到】
: 上面我的办法稍微改动一下，就是O(N) O(1)space的solution.
【在 e*****e 的大作中提到】
: 上面我的办法稍微改动一下，就是O(N) O(1)space的solution.
e*e
17 楼
O(1)不难啊，搞一个
typedef
{
int dif;
int start;
int end;
};
的数组，里面存了这个程序所能支持的所有的diff
因为这个和input 无关，我们假设支持-10，到10.
typedef
{
int dif;
int start;
int end;
};
的数组，里面存了这个程序所能支持的所有的diff
因为这个和input 无关，我们假设支持-10，到10.
H*r
18 楼
max diff might be of the order of the size of the array
so does min diff
【在 e*****e 的大作中提到】
: O(1)不难啊，搞一个
: typedef
: {
: int dif;
: int start;
: int end;
: };
: 的数组，里面存了这个程序所能支持的所有的diff
: 因为这个和input 无关，我们假设支持-10，到10.
so does min diff
【在 e*****e 的大作中提到】
: O(1)不难啊，搞一个
: typedef
: {
: int dif;
: int start;
: int end;
: };
: 的数组，里面存了这个程序所能支持的所有的diff
: 因为这个和input 无关，我们假设支持-10，到10.
e*e
19 楼
不要钻牛角尖吗，这个方法一般的情况都可以handle，handle不了的我就直接说我不能
处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
一定要O(1)space.
那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
个bitmap是O(1)space呢，还是O(n).
处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
一定要O(1)space.
那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
个bitmap是O(1)space呢，还是O(n).
m*i
20 楼
没看懂什么意思
这个如何O(n)time
这个如何O(n)time
b*e
21 楼
His answer is not too far from being correct. In fact, it'd be much easier
if we put -1 at the 0 positions. Then all that we need to do is to get the
sum array and do a counting sort. It's still O(n) space though.
【在 m****i 的大作中提到】
: 没看懂什么意思
: 这个如何O(n)time
if we put -1 at the 0 positions. Then all that we need to do is to get the
sum array and do a counting sort. It's still O(n) space though.
【在 m****i 的大作中提到】
: 没看懂什么意思
: 这个如何O(n)time
c*l
22 楼
Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
【在 e*****e 的大作中提到】
: 这个题目不要DP。
: 比如如下的数组
: 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
: 求每个位置的和(就是1 的数目）
: 0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
: 求每个偶数位置需要的1的数字（有相同的0,1）
: 0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
: 求两组的差
: 0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
: 找距离最远的两个一样的数字
【在 e*****e 的大作中提到】
: 这个题目不要DP。
: 比如如下的数组
: 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
: 求每个位置的和(就是1 的数目）
: 0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
: 求每个偶数位置需要的1的数字（有相同的0,1）
: 0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
: 求两组的差
: 0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
: 找距离最远的两个一样的数字
l*o
23 楼
如何O(1)时间在两组的差里找两个一样的数字（同时const space）？
【在 e*****e 的大作中提到】
: 这个题目不要DP。
: 比如如下的数组
: 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
: 求每个位置的和(就是1 的数目）
: 0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
: 求每个偶数位置需要的1的数字（有相同的0,1）
: 0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
: 求两组的差
: 0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
: 找距离最远的两个一样的数字
【在 e*****e 的大作中提到】
: 这个题目不要DP。
: 比如如下的数组
: 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
: 求每个位置的和(就是1 的数目）
: 0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
: 求每个偶数位置需要的1的数字（有相同的0,1）
: 0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
: 求两组的差
: 0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
: 找距离最远的两个一样的数字
l*o
24 楼
re
【在 c****l 的大作中提到】
: Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
【在 c****l 的大作中提到】
: Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
c*p
25 楼
bitmap这个应该还是O(n)的吧。。。
【在 e*****e 的大作中提到】
: 不要钻牛角尖吗，这个方法一般的情况都可以handle，handle不了的我就直接说我不能
: 处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
: 定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
: 一定要O(1)space.
: 那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
: 个bitmap是O(1)space呢，还是O(n).
【在 e*****e 的大作中提到】
: 不要钻牛角尖吗，这个方法一般的情况都可以handle，handle不了的我就直接说我不能
: 处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
: 定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
: 一定要O(1)space.
: 那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
: 个bitmap是O(1)space呢，还是O(n).
b*e
26 楼
// You can run this code in your browser console, e.g. firebug with
firefox or chrome console.
var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
var getMaxZeroOneSeq = function(a) {
var sum = 0;
var max = 0;
var map = {0: 0}; // for (var i = 0; i < a.length; i++) {
if (a[i] == 1) {
sum++;
} else { // if (a[i] == 0)
sum--;
}
if (map[sum] == null) {
map[sum] = i;
} else {
max = Math.max(max, i - map[sum] + 1);
}
}
return max;
};
getMaxZeroOneSeq(a);
【在 l****o 的大作中提到】
: 如何O(1)时间在两组的差里找两个一样的数字（同时const space）？
firefox or chrome console.
var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
var getMaxZeroOneSeq = function(a) {
var sum = 0;
var max = 0;
var map = {0: 0}; // for (var i = 0; i < a.length; i++) {
if (a[i] == 1) {
sum++;
} else { // if (a[i] == 0)
sum--;
}
if (map[sum] == null) {
map[sum] = i;
} else {
max = Math.max(max, i - map[sum] + 1);
}
}
return max;
};
getMaxZeroOneSeq(a);
【在 l****o 的大作中提到】
: 如何O(1)时间在两组的差里找两个一样的数字（同时const space）？
s*o
27 楼
for {1,1,0} your method returns 3
【在 b***e 的大作中提到】
: // You can run this code in your browser console, e.g. firebug with
: firefox or chrome console.
: var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
: var getMaxZeroOneSeq = function(a) {
: var sum = 0;
: var max = 0;
: var map = {0: 0}; // : for (var i = 0; i < a.length; i++) {
: if (a[i] == 1) {
: sum++;
【在 b***e 的大作中提到】
: // You can run this code in your browser console, e.g. firebug with
: firefox or chrome console.
: var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
: var getMaxZeroOneSeq = function(a) {
: var sum = 0;
: var max = 0;
: var map = {0: 0}; // : for (var i = 0; i < a.length; i++) {
: if (a[i] == 1) {
: sum++;
b*e
28 楼
Modified boundary condition.
【在 s******o 的大作中提到】
: for {1,1,0} your method returns 3
【在 s******o 的大作中提到】
: for {1,1,0} your method returns 3
c*9
29 楼
写了一个，感觉上应该满足
void longsubequal(int* a,int len)
{
for(int i=0;i
if(a[i]==0)
a[i]=-1;
}
int prevleft = 0;
int prevright = 0;
int currentleft = 0;
int currentright = 0;
int maxlen = 0;
int pos = 0;
while(pos
currentleft = pos;
currentright = pos+1;
int sum=0;
while(currentleft>0&¤tright
sum = a[currentleft]+a[currentright];
if(currentleft==prevright)
{
currentleft = prevleft;
currentleft--;
currentright++;
}
else if(sum==0)
{
currentleft--;
currentright++;
}
else if(sum!=0)
break;
}
if(currentright-currentleft-1>maxlen)
{
maxlen = currentright-currentleft-1;
prevleft = currentleft+1;
prevright = currentright-1;
}
pos++;
}
int start = prevleft;
for(int i=0;i
if(a[start]==-1)
cout<<0;
else
cout<<1;
start++;
}
}
void longsubequal(int* a,int len)
{
for(int i=0;i
if(a[i]==0)
a[i]=-1;
}
int prevleft = 0;
int prevright = 0;
int currentleft = 0;
int currentright = 0;
int maxlen = 0;
int pos = 0;
while(pos
currentleft = pos;
currentright = pos+1;
int sum=0;
while(currentleft>0&¤tright
sum = a[currentleft]+a[currentright];
if(currentleft==prevright)
{
currentleft = prevleft;
currentleft--;
currentright++;
}
else if(sum==0)
{
currentleft--;
currentright++;
}
else if(sum!=0)
break;
}
if(currentright-currentleft-1>maxlen)
{
maxlen = currentright-currentleft-1;
prevleft = currentleft+1;
prevright = currentright-1;
}
pos++;
}
int start = prevleft;
for(int i=0;i
if(a[start]==-1)
cout<<0;
else
cout<<1;
start++;
}
}
m*g
30 楼
如题，例子：[0,1,1,1,1,0,0,1], and the result should be [1,1,0,0]
有没有O(n)runtime and O(1) space的solution？
谢谢！
有没有O(n)runtime and O(1) space的solution？
谢谢！
s*e
31 楼
dp题，我的思路，大家看看对不对
O(n)runtime and O(n) space的solution:
create an array of length n, len[n], len[i] represent the length of subarray
which has equal number of 1 and 0 ending at index i. Initially, set all the
element len[] to be 0.
len[i] = len[i - 1] + 2 if arr[i] = 1 - arr[i - len[i - 1] - 1]
len[i] = 0 otherwise
then scan array len[], find out the largest one
optimized solution, O(n)runtime and O(1) space的solution:
actaully, we do not need to keep array len[] since len[i] only depends on
len[i - 1], for each i, if we know len[i - 1] we can get len[i], we need
another two variables maxSubarrayLen and maxEndingIndex to record the max
length of subarray and the ending index of this subarray respectively
O(n)runtime and O(n) space的solution:
create an array of length n, len[n], len[i] represent the length of subarray
which has equal number of 1 and 0 ending at index i. Initially, set all the
element len[] to be 0.
len[i] = len[i - 1] + 2 if arr[i] = 1 - arr[i - len[i - 1] - 1]
len[i] = 0 otherwise
then scan array len[], find out the largest one
optimized solution, O(n)runtime and O(1) space的solution:
actaully, we do not need to keep array len[] since len[i] only depends on
len[i - 1], for each i, if we know len[i - 1] we can get len[i], we need
another two variables maxSubarrayLen and maxEndingIndex to record the max
length of subarray and the ending index of this subarray respectively
s*n
32 楼
有问题啊：比如01111000，访问最后一个0
s*e
33 楼
恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，keep
ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
subarray时，判断是否可以跟previous合并，还是O(1)space的
【在 s******n 的大作中提到】
: 有问题啊：比如01111000，访问最后一个0
ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
subarray时，判断是否可以跟previous合并，还是O(1)space的
【在 s******n 的大作中提到】
: 有问题啊：比如01111000，访问最后一个0
s*n
34 楼
不是O(1)space的吧，要判断和previous能否合并，要不就保留以前的结果space>O(1)
，要不重新查time>O(n)。
【在 s**********e 的大作中提到】
: 恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，keep
: ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
: subarray时，判断是否可以跟previous合并，还是O(1)space的
，要不重新查time>O(n)。
【在 s**********e 的大作中提到】
: 恩，原算法有问题，漏掉了这种情况，不过把这种情况考虑进去应该就对了吧，keep
: ending index of previous subarray, 每次计算以当前index为结束的0,1个数相同
: subarray时，判断是否可以跟previous合并，还是O(1)space的
s*e
35 楼
不需要保留以前的所有结果，只需要记录下previous就可以，扫描的同时更新previous
s*n
36 楼
不太明白，你写个例子或者程序
previous
【在 s**********e 的大作中提到】
: 不需要保留以前的所有结果，只需要记录下previous就可以，扫描的同时更新previous
previous
【在 s**********e 的大作中提到】
: 不需要保留以前的所有结果，只需要记录下previous就可以，扫描的同时更新previous
s*e
37 楼
public static void longestSubarray(int[] arr){
int prevSubarrayLen = 0;
int preSubarrayEndingIndex = -1;
int longestLen = 0;
int longestEndingIndex = -1;
int preLen = 0;
for(int i=1;i
preLen += 2;
if(i-preLen == preSubarrayEndingIndex)
preLen += prevSubarrayLen;
if(preLen > longestLen){
longestLen = preLen;
longestEndingIndex = i;
}
}else if(preLen > 0){
prevSubarrayLen = preLen;
preSubarrayEndingIndex = i - 1;
preLen = 0;
}
}
System.out.println(
"start index："+(longestEndingIndex - longestLen + 1) +
" end index："+ longestEndingIndex +
" length："+ longestLen);
}
int prevSubarrayLen = 0;
int preSubarrayEndingIndex = -1;
int longestLen = 0;
int longestEndingIndex = -1;
int preLen = 0;
for(int i=1;i
preLen += 2;
if(i-preLen == preSubarrayEndingIndex)
preLen += prevSubarrayLen;
if(preLen > longestLen){
longestLen = preLen;
longestEndingIndex = i;
}
}else if(preLen > 0){
prevSubarrayLen = preLen;
preSubarrayEndingIndex = i - 1;
preLen = 0;
}
}
System.out.println(
"start index："+(longestEndingIndex - longestLen + 1) +
" end index："+ longestEndingIndex +
" length："+ longestLen);
}
s*n
38 楼
感觉有问题，在扩展当前的subarray的时候，因为当前subarray的首端-1，会冲掉
preSubarray，不能单用一个变量来存presubarray。
【在 s**********e 的大作中提到】
: public static void longestSubarray(int[] arr){
: int prevSubarrayLen = 0;
: int preSubarrayEndingIndex = -1;
: int longestLen = 0;
: int longestEndingIndex = -1;
: int preLen = 0;
: for(int i=1;i
: preLen += 2;
: if(i-preLen == preSubarrayEndingIndex)
preSubarray，不能单用一个变量来存presubarray。
【在 s**********e 的大作中提到】
: public static void longestSubarray(int[] arr){
: int prevSubarrayLen = 0;
: int preSubarrayEndingIndex = -1;
: int longestLen = 0;
: int longestEndingIndex = -1;
: int preLen = 0;
: for(int i=1;i
: preLen += 2;
: if(i-preLen == preSubarrayEndingIndex)
e*e
39 楼
你这个办法应该不行。
想0101010101010101010101
这样的你方法好像就不对。
想0101010101010101010101
这样的你方法好像就不对。
s*e
40 楼
没看明白，能不能给个反例？
【在 s******n 的大作中提到】
: 感觉有问题，在扩展当前的subarray的时候，因为当前subarray的首端-1，会冲掉
: preSubarray，不能单用一个变量来存presubarray。
【在 s******n 的大作中提到】
: 感觉有问题，在扩展当前的subarray的时候，因为当前subarray的首端-1，会冲掉
: preSubarray，不能单用一个变量来存presubarray。
s*n
41 楼
其实有一邪招：用原数组作为DP用，把0/1放最高位，最后恢复。
e*e
42 楼
这个题目不要DP。
比如如下的数组
0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
求每个位置的和(就是1 的数目）
0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
求每个偶数位置需要的1的数字（有相同的0,1）
0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
求两组的差
0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
找距离最远的两个一样的数字
2,从4,16
注意查查边缘，因为有可能答案是从一个奇数位到另外一个奇数位置。
不过这个答案肯定会包含一个最大的从偶数位到偶数位的。
就是0,0,1,1,0,0,0,0,1,1,1,1
比如如下的数组
0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
求每个位置的和(就是1 的数目）
0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
求每个偶数位置需要的1的数字（有相同的0,1）
0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
求两组的差
0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
找距离最远的两个一样的数字
2,从4,16
注意查查边缘，因为有可能答案是从一个奇数位到另外一个奇数位置。
不过这个答案肯定会包含一个最大的从偶数位到偶数位的。
就是0,0,1,1,0,0,0,0,1,1,1,1
e*e
43 楼
上面我的办法稍微改动一下，就是O(N) O(1)space的solution.
H*r
44 楼
O(1)space 是难点
【在 e*****e 的大作中提到】
: 上面我的办法稍微改动一下，就是O(N) O(1)space的solution.
【在 e*****e 的大作中提到】
: 上面我的办法稍微改动一下，就是O(N) O(1)space的solution.
e*e
45 楼
O(1)不难啊，搞一个
typedef
{
int dif;
int start;
int end;
};
的数组，里面存了这个程序所能支持的所有的diff
因为这个和input 无关，我们假设支持-10，到10.
typedef
{
int dif;
int start;
int end;
};
的数组，里面存了这个程序所能支持的所有的diff
因为这个和input 无关，我们假设支持-10，到10.
H*r
46 楼
max diff might be of the order of the size of the array
so does min diff
【在 e*****e 的大作中提到】
: O(1)不难啊，搞一个
: typedef
: {
: int dif;
: int start;
: int end;
: };
: 的数组，里面存了这个程序所能支持的所有的diff
: 因为这个和input 无关，我们假设支持-10，到10.
so does min diff
【在 e*****e 的大作中提到】
: O(1)不难啊，搞一个
: typedef
: {
: int dif;
: int start;
: int end;
: };
: 的数组，里面存了这个程序所能支持的所有的diff
: 因为这个和input 无关，我们假设支持-10，到10.
e*e
47 楼
不要钻牛角尖吗，这个方法一般的情况都可以handle，handle不了的我就直接说我不能
处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
一定要O(1)space.
那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
个bitmap是O(1)space呢，还是O(n).
处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
一定要O(1)space.
那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
个bitmap是O(1)space呢，还是O(n).
m*i
48 楼
没看懂什么意思
这个如何O(n)time
这个如何O(n)time
b*e
49 楼
His answer is not too far from being correct. In fact, it'd be much easier
if we put -1 at the 0 positions. Then all that we need to do is to get the
sum array and do a counting sort. It's still O(n) space though.
【在 m****i 的大作中提到】
: 没看懂什么意思
: 这个如何O(n)time
if we put -1 at the 0 positions. Then all that we need to do is to get the
sum array and do a counting sort. It's still O(n) space though.
【在 m****i 的大作中提到】
: 没看懂什么意思
: 这个如何O(n)time
c*l
50 楼
Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
【在 e*****e 的大作中提到】
: 这个题目不要DP。
: 比如如下的数组
: 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
: 求每个位置的和(就是1 的数目）
: 0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
: 求每个偶数位置需要的1的数字（有相同的0,1）
: 0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
: 求两组的差
: 0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
: 找距离最远的两个一样的数字
【在 e*****e 的大作中提到】
: 这个题目不要DP。
: 比如如下的数组
: 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
: 求每个位置的和(就是1 的数目）
: 0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
: 求每个偶数位置需要的1的数字（有相同的0,1）
: 0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
: 求两组的差
: 0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
: 找距离最远的两个一样的数字
l*o
51 楼
如何O(1)时间在两组的差里找两个一样的数字（同时const space）？
【在 e*****e 的大作中提到】
: 这个题目不要DP。
: 比如如下的数组
: 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
: 求每个位置的和(就是1 的数目）
: 0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
: 求每个偶数位置需要的1的数字（有相同的0,1）
: 0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
: 求两组的差
: 0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
: 找距离最远的两个一样的数字
【在 e*****e 的大作中提到】
: 这个题目不要DP。
: 比如如下的数组
: 0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1
: 求每个位置的和(就是1 的数目）
: 0，1,2,3,4,4,4,5,6,6,6,6,6,7,8,9,10,11,12
: 求每个偶数位置需要的1的数字（有相同的0,1）
: 0，X,1,X,2,X,3,X,4,X,5,X,6,X,7,X,8,X,9
: 求两组的差
: 0，X,1,X,2,X,1,X,2,X,1,X,0,X,1,X,2,X,3
: 找距离最远的两个一样的数字
l*o
52 楼
re
【在 c****l 的大作中提到】
: Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
【在 c****l 的大作中提到】
: Isn't the answer 0,1,1,1,1,0,0,1,1,0,0,0,0,1? Did I miss anything here.
c*p
53 楼
bitmap这个应该还是O(n)的吧。。。
【在 e*****e 的大作中提到】
: 不要钻牛角尖吗，这个方法一般的情况都可以handle，handle不了的我就直接说我不能
: 处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
: 定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
: 一定要O(1)space.
: 那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
: 个bitmap是O(1)space呢，还是O(n).
【在 e*****e 的大作中提到】
: 不要钻牛角尖吗，这个方法一般的情况都可以handle，handle不了的我就直接说我不能
: 处理。max diff 要和order of size array 有关，得有多少个1啊，一般面试这么说肯
: 定够了。现实中写code啥时候一定要O(1)的space?我以前做embeded system都从来没有
: 一定要O(1)space.
: 那我随便出一题目，你用bitmap做来完成O(1),我给你个数组，1,2,3,4到n+1,你说你这
: 个bitmap是O(1)space呢，还是O(n).
b*e
54 楼
/*
You can run this code in your browser console, e.g. firebug with
firefox or chrome console.
*/
var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
var getMaxZeroOneSeq = function(a) {
var sum = 0;
var max = 0;
var map = {0: -1}; // for (var i = 0; i < a.length; i++) {
if (a[i] == 1) {
sum++;
} else { // if (a[i] == 0)
sum--;
}
if (map[sum] == null) {
map[sum] = i;
} else {
max = Math.max(max, i - map[sum]);
}
}
return max;
};
getMaxZeroOneSeq(a);
【在 l****o 的大作中提到】
: 如何O(1)时间在两组的差里找两个一样的数字（同时const space）？
You can run this code in your browser console, e.g. firebug with
firefox or chrome console.
*/
var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
var getMaxZeroOneSeq = function(a) {
var sum = 0;
var max = 0;
var map = {0: -1}; // for (var i = 0; i < a.length; i++) {
if (a[i] == 1) {
sum++;
} else { // if (a[i] == 0)
sum--;
}
if (map[sum] == null) {
map[sum] = i;
} else {
max = Math.max(max, i - map[sum]);
}
}
return max;
};
getMaxZeroOneSeq(a);
【在 l****o 的大作中提到】
: 如何O(1)时间在两组的差里找两个一样的数字（同时const space）？
s*o
55 楼
for {1,1,0} your method returns 3
【在 b***e 的大作中提到】
: // You can run this code in your browser console, e.g. firebug with
: firefox or chrome console.
: var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
: var getMaxZeroOneSeq = function(a) {
: var sum = 0;
: var max = 0;
: var map = {0: 0}; // : for (var i = 0; i < a.length; i++) {
: if (a[i] == 1) {
: sum++;
【在 b***e 的大作中提到】
: // You can run this code in your browser console, e.g. firebug with
: firefox or chrome console.
: var a = [0,1,1,1,1,0,0,1,1,0,0,0,0,1,1,1,1,1,1];
: var getMaxZeroOneSeq = function(a) {
: var sum = 0;
: var max = 0;
: var map = {0: 0}; // : for (var i = 0; i < a.length; i++) {
: if (a[i] == 1) {
: sum++;
b*e
56 楼
Modified boundary condition.
【在 s******o 的大作中提到】
: for {1,1,0} your method returns 3
【在 s******o 的大作中提到】
: for {1,1,0} your method returns 3
c*9
57 楼
写了一个，感觉上应该满足
void longsubequal(int* a,int len)
{
for(int i=0;i
if(a[i]==0)
a[i]=-1;
}
int prevleft = 0;
int prevright = 0;
int currentleft = 0;
int currentright = 0;
int maxlen = 0;
int pos = 0;
while(pos
currentleft = pos;
currentright = pos+1;
int sum=0;
while(currentleft>0&¤tright
sum = a[currentleft]+a[currentright];
if(currentleft==prevright)
{
currentleft = prevleft;
currentleft--;
currentright++;
}
else if(sum==0)
{
currentleft--;
currentright++;
}
else if(sum!=0)
break;
}
if(currentright-currentleft-1>maxlen)
{
maxlen = currentright-currentleft-1;
prevleft = currentleft+1;
prevright = currentright-1;
}
pos++;
}
int start = prevleft;
for(int i=0;i
if(a[start]==-1)
cout<<0;
else
cout<<1;
start++;
}
}
void longsubequal(int* a,int len)
{
for(int i=0;i
if(a[i]==0)
a[i]=-1;
}
int prevleft = 0;
int prevright = 0;
int currentleft = 0;
int currentright = 0;
int maxlen = 0;
int pos = 0;
while(pos
currentleft = pos;
currentright = pos+1;
int sum=0;
while(currentleft>0&¤tright
sum = a[currentleft]+a[currentright];
if(currentleft==prevright)
{
currentleft = prevleft;
currentleft--;
currentright++;
}
else if(sum==0)
{
currentleft--;
currentright++;
}
else if(sum!=0)
break;
}
if(currentright-currentleft-1>maxlen)
{
maxlen = currentright-currentleft-1;
prevleft = currentleft+1;
prevright = currentright-1;
}
pos++;
}
int start = prevleft;
for(int i=0;i
if(a[start]==-1)
cout<<0;
else
cout<<1;
start++;
}
}
相关阅读
请教下Fungus对房子影响大吗?红地炮考察画框材料回来Hardwood Floor DIY关于后院的死树的保险明天appraisor就要来appraisal house了，有什么需要注意的吗？新手买房请教问题有没有全包yard work, landscape的同学？帮忙看个房子的信息怎样自己激活已经安装的home security system邻居是低收入房，应该考虑吗？楼梯的地毯用哪个神器吸啊？中文电视频道帮忙看两栋房子的朝向（有图）买的沙发破了，能换吗？怎么选学区房? 看小学还是中学?再请纽约的大牛们帮忙，推荐个靠谱的agentabout short sale重新贷款，要求自个先付CLOSING费安装抽油烟机人工要多少钱啊？ (转载)在美国，妈妈不要给儿子洗澡、爸爸不要给女儿 (转载)