查找具有相同数量的1和0的最大子序列二进制集

Question

我在互联网上发现了以下问题,并想知道我将如何解决它:

你得到一个包含0和1的数组.找到O(n)时间和O(1)空间算法以找到具有相等数量的1和0的最大子序列.

例子:

1. 10101010 - 满足问题的最长子序列是输入本身
2. 1101000 - 满足该问题的最长子序列是110100

Answer 1

更新.

我必须完全改写我的答案.(如果你对早期版本进行了投票,那么,你被欺骗了!)

让我们再次总结一下这个简单的案例吧!

Find the longest prefix of the bit-string containing an equal number of 1s and 0s of the array.

This is trivial: A simple counter is needed, counting how many more 1s we have than 0s, and iterating the bitstring while maintaining this. The position where this counter becomes zero for the last time is the end of the longest sought prefix. O(N) time, O(1) space. (I'm completely convinced by now that this is what the original problem asked for. )

Now lets switch to the more difficult version of the problem: we no longer require subsequences to be prefixes - they can start anywhere.

经过一番来回思考,我认为可能没有线性算法.例如,考虑前缀"111111111111111111 ...".这些中的每一个可能是最长子序列的开始,没有候选子序列起始位置支配(即总是提供比其他任何位置更好的解决方案),因此我们不能丢弃它们中的任何一个(O(N)在任何步骤中,我们必须能够在O(1)时间内从线性多个候选中选择最佳起点(其具有与当前位置相等的1和0的数量).事实证明这是可行的,也很容易实现,因为我们可以根据1s(+1)和0s(-1)的运行总和来选择候选者,这最多只有N个,我们可以存储第一个位置我们在2N细胞中达到每个总和 - 请参阅下面的pmod的答案(yellowfog的评论和几何见解).

没有发现这个技巧,我用一个缓慢但确定的算法替换了一个快速但错误的(因为正确的算法比错误的算法更好!):

• 构建一个A从开始到该位置的累计数量为1 的数组,例如,如果bitstring为"001001001",则数组将为[0,0,1,1,1,2,2,2,3].使用这个,我们可以在O(1)中测试子序列(i,j)是否有效:isValid(i, j) = (j - i + 1 == 2 * (A[j] - A[i - 1]),即如果它的长度是其中1s的两倍,则它是有效的.例如,子序列(3,6)是有效的,因为6 - 3 + 1 == 2*A [6] - A [2] = 4.

• 普通老双圈:

  maxSubsLength = 0表示i = 1到N - 1表示j = i + 1表示N,如果isValid(i,j)... #maintain maxSubsLength end end

通过跳过比当前maxSubsLength短的i/j序列,使用一些分支和绑定可以加快一点,但渐近地这仍然是O(n ^ 2).慢,但有一个很大的优点:正确!

Answer 2

严格地说,答案是不存在这样的算法,因为由相等数量的零和1组成的字符串的语言不规则.

当然,每个人都忽略了这一事实,存储大小的整n是O(log n)在空间,将其视为O(1)在太空中.:-)几乎所有大的O,包括时间的,都充满了(或者说是空的)缺失log n因子,或者等价地,它们假设n受到机器字大小的限制,这意味着你真的在看一个有限的问题,一切都是O(1).

Answer 3

新解决方案: 假设我们有n位输入位阵列2*n大小的数组来保持位的位置.因此,数组元素的大小必须足够大,以保持最大位置数.对于256个输入位阵列,它需要256x2字节数组(字节足以保持255 - 最大位置).

从位数组的第一个位置开始,我们使用规则将位置从数组的中间(索引为n)开始放入数组:

1.如果我们通过"1"位则递增位置,当通过"0"位时递减

2.遇到已初始化的数组元素 - 不要更改它并记住位置之间的差异(当前减去数组元素) - 这是局部最大序列的大小.

3.每当我们达到局部最大值时,将其与全局最大值进行比较,如果后者较小则更新.

例如:位序列是0,0,0,1,0,1

   initial array index is n
   set arr[n] = 0 (position)
     bit 0 -> index--
   set arr[n-1] = 1 
     bit 0 -> index--
   set arr[n-2] = 2
     bit 0 -> index--
   set arr[n-3] = 3
     bit 1 -> index++
   arr[n-2] already contains 2 -> thus, local max seq is [3,2] becomes abs. maximum
      will not overwrite arr[n-2]
     bit 0 -> index--
   arr[n-3] already contains 3 -> thus, local max seq is [4,3] is not abs. maximum
     bit 1 -> index++
   arr[n-2] already contains 2 -> thus, local max seq is [5,2] is abs. max

因此,我们只通过整个位数组一次.这解决了这个任务吗？

input:
    n - number of bits
    a[n] - input bit-array

track_pos[2*n] = {0,};
ind = n;
/* start from position 1 since zero has
  meaning track_pos[x] is not initialized */
for (i = 1; i < n+1; i++) {
    if (track_pos[ind]) {
        seq_size = i - track_pos[ind];
        if (glob_seq_size < seq_size) {
            /* store as interm. result */
            glob_seq_size = seq_size;
            glob_pos_from = track_pos[ind];
            glob_pos_to   = i;
        }
    } else {
        track_pos[ind] = i;
    }

    if (a[i-1])
        ind++;
    else
        ind--;
}

output:
    glob_seq_size - length of maximum sequence
    glob_pos_from - start position of max sequence
    glob_pos_to   - end position of max sequence

Answer 4

暴力破解：从数组的最大长度开始计算 o 和 l。如果 o 等于 l，则完成。否则将搜索长度减少 1，并对减少长度（即最大长度减去减少长度）的所有子序列执行算法，依此类推。当减法为0时停止。