zen me dou zai tao lun liu bei??? - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Joke - 肚皮舞运动

zen me dou zai tao lun liu bei???

zen me dou zai tao lun liu bei???# Joke - 肚皮舞运动

I*A2010-05-24 07:05

1 楼

You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
algorithm to find the maximum sub sequence which has equal number of 1s and
0s.
Examples
10101010
The longest sub sequence that satisfies the problem is the input itself
1101000

s*e2010-05-24 07:05

2 楼

hen confused

g*y2010-05-24 07:05

3 楼

我觉得这个题就是那个max length of subarray which sum to a
target value的变种。因为这个题array是binary的(意味着一段子数组的和的变化是“
连续”的)，这个性质使得不需要经典题中用到的O(n)的hashtable

c*o2010-05-24 07:05

4 楼

你要说啥？

【在 s*******e 的大作中提到】

: hen confused

i*r2010-05-24 07:05

5 楼

Minus 0.5 for each elements in the array, then the problem is converted
to finding the maximum length sub-array whose sum is zero.

i*a2010-05-24 07:05

6 楼

wo kenbeimibai ni zhashusumo. wu symo beidaichowen?

a*k2010-05-24 07:05

7 楼

who has link to the problem "finding the maximum length sub-array whose sum
is a given value"?

I*g2010-05-24 07:05

8 楼

关键是O(1)的space。
我知道有人做出了timeO(nlgn) space O(1)的算法
期待有人做出O(n)的

g*y2010-05-24 07:05

9 楼

我不是都已经说了提示了吗

【在 I*********g 的大作中提到】

: 关键是O(1)的space。
: 我知道有人做出了timeO(nlgn) space O(1)的算法
: 期待有人做出O(n)的

i*r2010-05-24 07:05

10 楼

Hmmm...
I was thinking the question was related to maxmium subarray problem or
subset sum problem. I was probably wrong.
The brutal force solution can achieve O(n^2) time complexity. To find an
O(n) solution, the problem need to be formulated as a recursion on a one-
dimensional subproblem space. I simply fail to see optimal substructures
among the prefix subproblems. Is it really possible to get an O(n) time
solution?

sum

【在 a**********k 的大作中提到】

: who has link to the problem "finding the maximum length sub-array whose sum
: is a given value"?

H*r2010-05-24 07:05

11 楼

Count number of '1' and '0'
Reconstruct the sub-sequence from result above.

space
and

【在 I**A 的大作中提到】

: You are given an array ' containing 0s and 1s. Find O(n) time and O(1) space
: algorithm to find the maximum sub sequence which has equal number of 1s and
: 0s.
: Examples
: 10101010
: The longest sub sequence that satisfies the problem is the input itself
: 1101000

l*q2010-05-24 07:05

12 楼

1。用本数组高位（除个位以外）做hash，放这个element之前的1的个数。比如如果
array[i]本来为1，array[0]到array[i-1]一共有5个1，则修改array[i]为51。这样空
间是O(1)的
2。其实对于定长的subarrays来说，如果满足1和0相等的条件，它们的1的数目必然是
相等的，也就是说它们的累积和都是相等的。所以这道题，就是在求累积和的最大差，
只不过加一个附加条件，那就是累积和必须为subarray长度的一半。这个最大差可以用
我们修改过的数组来求。类似于a0,a1,a2,...,an中求，max((aj-ai)),i(n)的，以前讨论过

g*y2010-05-24 07:05

13 楼

严格意义上来说，你修改了原数组，即便最后还原，好像也不算是真正的O(1)空间算法
? => 如果数组是只读的呢?
其实我想的那个方法也是需要你这个trick才能O(1)空间，所以我就删掉了

s*s2010-05-24 07:05

14 楼

我想到一个简单的贪心算法
两个指针从两边开始，如果整个数组1多，就从两端是1的一个移动。
例如：
101010101
开始指向第一个和最后一个1，结果发现数组多了一个1
结果两端都是1，随意反方向移动一个。
1000001
左边移动一个，右边移动一个。

s*s2010-05-24 07:05

15 楼

算法似乎有问题，我有空再想想

l*t2010-05-24 07:05

16 楼

大家看看是否正确
1.scan and count 0 and 1. 假定0多k个
2.find 0 from both ends. 去掉距离头或尾近的0，如果距离相同，任选一个。如果同
时去掉了1，k要增加。直到k=0.
ex.
110100001 k=1
->
1101000 k=1
->
110100

y*n2010-05-24 07:05

17 楼

找到反例了
1010101111111010101

【在 l**********t 的大作中提到】

: 大家看看是否正确
: 1.scan and count 0 and 1. 假定0多k个
: 2.find 0 from both ends. 去掉距离头或尾近的0，如果距离相同，任选一个。如果同
: 时去掉了1，k要增加。直到k=0.
: ex.
: 110100001 k=1
: ->
: 1101000 k=1
: ->
: 110100