7

我得到一个看起来像这样的字符串:

1011010100

我的任务是找到一个子字符串的长度,其中空值的数量总是<=个数。这应该总是在从右到左和从左到右“扫描”子字符串时发生。所以在这个例子中,答案是:

10110101 => 8

我知道复杂度应该是 O(n) 或 O(n log n),因为长度可以达到 10^6

有任何想法吗?

4

3 回答 3

1

O(n)解决方案实际上非常简单,通过构建“高度数组”,表示 1 相对于 0 的数量。所以高度为 2 意味着 1 比 0 多 2 个。一旦在某些条件下执行一些极大值检查,我们就会遍历高度数组。

关键观察

请注意,满足条件的子数组的高度必须在开始时最小,在结束时最大(相对于子数组,而不是整个数组)。

问题中样本的高度数组可以这样绘制,并带有标记的答案:

       v
   /\/\/\
/\/ \
^

证明:

假设开始时高度不是最小值,这意味着子数组内部有一个点高度低于开始。此时,0的个数应该大于1的个数。矛盾。

假设最后的高度不是最大值,这意味着子数组中有一个点的高度大于结尾,比如在 index 处j。然后在 indexj到末尾有 0 多于 1 (因为高度减小),所以当我们从右到左“扫描”子数组时,我们会发现 index 处的 0 多于 1 j。矛盾。

算法

现在问题可以解释为找到最长的子数组,它以子数组中的最高高度结束,同时保持最小值不超过开始时的高度。这与 klrmlr 提到的最大子数组问题非常相似(“数组的连续子序列”更好地称为“子数组”)。这个想法不是保持一个O(n)状态,而是保持“迄今为止的最大值”和“此时的最大值”。

遵循该算法,下面是伪代码,遍历数组一次:

过程 Balance_Left_Right

  1. 记录迄今为止的最低点和最高点
  2. 如果此时的高度低于目前为止的最低点,则将起点改为该点之后的索引
  3. 如果此时的高度高于或等于迄今为止的最高点,那么这是一个有效的子数组,记录长度(以及开始和结束索引,如果你喜欢)

然而,我们很快就会看到这个测试用例的问题(正如 Adam Jackson 通过个人交流指出的那样):,1100101可视化如下:

/\
/ \/\/

正确答案是 3(最后 101 个),但上面的算法会得到 2(前 11 个)。这是因为我们的答案显然隐藏在一座“高山”后面(即答案的最低点不低于山,而答案的最高点不高于山)。

因此,我们需要确保在运行过程 Balance_Left_Right(上图)时,没有隐藏答案的“高山”。因此解决方案是从右侧遍历数组一次,尝试将数组划分为多个部分,在每个部分中,此属性保持:“1 的数量始终 >= 0 的数量,从右侧遍历",而且对于每个部分,它不能再向左扩展。

然后,在每个部分中,当从左侧遍历时,将在该部分的末尾具有最大高度,这就是最大值。并且可以证明,有了这个属性, balance_left_right 方法就可以找到本节的正确答案。因此,我们只需在每个部分上调用 balance_left_right 方法,然后从中取最大答案。

现在,您可能会问,为什么在每个部分上运行 Balance_Left_Right 就足够了?这是因为答案要求属性从左侧和右侧保持,因此它必须位于其中一个部分内,因为每个部分都满足一半的属性。

该算法仍然是O(n)因为我们只访问每个元素两次,一次从右侧,一次从左侧。

最后一个测试用例将被划分如下:

/|\ |
/ | \|/\/
** ***

其中仅使用标有星号 (*) 的部分。

所以新算法如下:

过程 Max_Balance_Left_Right

  1. 从右边开始对输入进行分区,其中 1 >= 0 的数量(使用右边的 Balance_Left,或者可以称之为 Balance_right)
  2. 在每个分区上运行 Balance_Left_Right
  3. 取最大值

这是Python中的代码:

def balance_left_right(arr):
    lower = 0
    upper = -2**32
    lower_idx = 0 # Optional
    upper_idx = -1 # Optional
    result = (0,0,0)
    height = 0
    length = 0
    for idx, num in enumerate(arr):
        length += 1
        height += 1 if num==1 else -1
        if height<lower:
            lower = height # Reset the lowest
            upper = height # Reset the highest
            lower_idx = idx+1 # Optional, record the starting point
            length = 0 # Reset the answer
        if height>=upper:
            upper = height
            upper_idx = idx # Optional, record the end point
            if length > result[0]: # Take maximum length
                result = (length, lower_idx, upper_idx)
    return result

def max_balance_left_right(arr):
    all_partitions = []
    start = 0
    end = len(arr)
    right_partitions = balance_left(reversed(arr[start:end]))
    for right_start, right_end in right_partitions:
        all_partitions.append((end-right_end, end-right_start))
    result = (0,0,0)
    for start, end in all_partitions:
        candidate = balance_left_right(arr[start:end])
        if result[0] < candidate[0]:
            result = (candidate[0], candidate[1]+start, candidate[2]+start)
    return result

def balance_left(arr):
    lower = 0
    start_idx = 0
    end_idx = -1
    height = 0
    result = []
    for idx, num in enumerate(arr):
        height += 1 if num==1 else -1
        if height < lower:
            if end_idx != -1:
                result.append((start_idx,end_idx))
            lower = height
            start_idx = idx+1
            end_idx = -1
        else:
            end_idx = idx+1
    if end_idx != -1:
        result.append((start_idx, end_idx))
    return result

test_cases = [
        [1,0,1,1,0,1,0,1,0,0],
        [0,0,1,0,1,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0,1],
        [1,1,1,0,0,0,1,0,0,1,1,0,1,1,0,1,1,0],
        [1,1,0,0,1,0,1,0,1,1,0,0,1,0,0],
        [1,1,0,0,1,0,1],
        [1,1,1,1,1,0,0,0,1,0,1,0,1,1,0,0,1,0,0,1,0,1,1]
        ]
for test_case in test_cases:
    print 'Balance left right:'
    print test_case
    print balance_left_right(test_case)
    print 'Max balance left right:'
    print test_case
    print max_balance_left_right(test_case)
    print

这将打印:

左右平衡:
[1, 0, 1, 1, 0, 1, 0, 1, 0, 0]
(8, 0, 7)
左右最大平衡:
[1, 0, 1, 1, 0, 1, 0, 1, 0, 0]
(8, 0, 7)

左右平衡:
[0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1]
(6, 12, 17)
左右最大平衡:
[0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 1]
(6, 12, 17)

左右平衡:
[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]
(8, 9, 16)
左右最大平衡:
[1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0]
(8, 9, 16)

左右平衡:
[1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0]
(10, 0, 9)
左右最大平衡:
[1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0]
(10, 0, 9)

左右平衡:
[1, 1, 0, 0, 1, 0, 1]
(2, 0, 1)
左右最大平衡:
[1, 1, 0, 0, 1, 0, 1]
(3, 4, 6)

左右平衡:
[1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1]
(5, 0, 4)
左右最大平衡:
[1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1]
(6, 8, 13)

为了您的眼睛享受,测试用例的高度数组:

第一的:
       v
   /\/\/\
/\/ \
^

第二:
\
 \/\/\ v
      \/\/\ /\/\/\
           \/ \/
            ^

第三:
                v
  /\ /\
 / \ /\/
/ \/\ /\/
        \/
         ^

第四:
         v
 /\ /\
/ \/\/\/ \/\
^ \

第五:
 /\ v
/ \/\/
    ^

第六:
    /\ v
   / \ /\
  / \/\/\/ \/\ /
 / ^ \/\/
/

关于问题的说明

由于一些读者对OP到底想要什么感到困惑,尽管问题中已经明确说明了,让我通过一些例子来解释这个问题。

首先,来自问题的任务:

我的任务是找到一个子字符串的长度,其中空值的数量总是<=个数。这应该总是发生在从右到左和从左到右“扫描”子字符串时

这指的是“加泰罗尼亚号码投票问题”或“可用更改问题”。在 Wiki 中,您可以检查“单调路径”问题,您可以将“向右移动”映射为“1”,将“向上移动”映射为“0”。

问题是找到原始数组的子数组,这样,当从左到右和从右到左遍历子数组时,这个属性成立:

到目前为止看到的 0 的数量不应超过迄今为止看到的 1 的数量。

例如,字符串1010包含从左到右的属性,因为如果我们从左到右扫描数组,总是会有比 0 多的 1。但是该属性从右到左不成立,因为从右边遇到的第一个字符是 0,所以一开始我们有更多的 0(有一个)而不是 1(没有)。

例如 OP 给出的例子,我们看到字符串的答案1011010100是前八个字符,即:10110101. 为什么?

好的,所以当我们从左到右遍历子数组时,我们看到 1 总是比 0 多。让我们在从左到右遍历数组时检查 1 和 0 的数量:

1:数(0)= 0,数(1)= 1
0:数(0)= 1,数(1)= 1
1:数(0)= 1,数(1)= 2
1:数(0)= 1,数(1)= 3
0:数(0)= 2,数(1)= 3
1:数(0)= 2,数(1)= 4
0:数(0)= 3,数(1)= 4
1:数(0)= 3,数(1)= 5

我们可以看到,在任何时候,0 的数量总是小于或等于 1 的数量。这就是该属性从左到右的原因。同样的检查可以从右到左进行。

那么为什么不1011010100回答呢?

让我们看看我们何时从右到左遍历字符串:

0:数(0)= 1,数(1)= 0
0:数(0)= 2,数(1)= 0
1:数(0)= 2,数(1)= 1
...

我没有进行完整遍历,因为从第一步开始就已经违反了该属性,因为我们有num(0) > num(1). 这就是字符串1011010100不满足问题约束的原因。

您还可以看到,我的“高度数组”实际上是 1 的数量和 0 的数量之间的差异,即:num(1) - num(0)。因此,为了拥有该属性,我们必须将 [相对] 高度设为正数。这可以通过使高度不小于初始高度来可视化。

于 2013-10-21T02:26:53.680 回答
1

这是我的算法:

从右侧开始:

 1. if you find 0 increment the value of count
 2. if you find 1 decrement the count

将这些值存储在一个数组中,即v[]. 例如

a[] = {1, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 1}

v[] = {0, 1, 0,-1, 0, 1, 0, 1, 2, 1, 2, 1, 0, -1}

现在问题减少到从Viei, j中查找索引v[i] < v[j]i<j

证明

如果您在这里看到i=0并且j=11是可能的答案并且值为v[i]=0, v[j]=1。这意味着直到j 我们0在字符串中有一个额外的并且v[i]=0这意味着从i to j窗口大小来看,0通过放置 extra 来取消额外的1。因此得到了答案。

希望能帮助到你。如果您有疑问,请告诉我。谢谢。

于 2013-10-21T00:04:08.623 回答
0

(几乎正确,即轻微错误)线性时间解

对问题进行了两次重新编码(稍后删除了一个......)和一个滑动窗口。

编码 A

您可以压缩输入以产生后续零或一的数量:

+1 -1 +2 -1 +1 -1 +1 -2

这会产生编码 A并且需要 O(n) 时间。

编码 B

现在,在编码 A 中,每当遇到两个连续数字的总和 > 0 时,都会进一步压缩。在编码 B中,括号中的数字表示子字符串的长度:

+2(4) -1 +1 -1 +1 -2 ==> +2(6) -1 +1 -2 ==> +2(8) -2

这也需要 O(n)。在这里,我们立即得到了解决方案:长度为 8 的字符串,其中 1 比 0 多两个。让我们尝试一个更复杂的实例(在编码 A 中给出):

+5 -8 +4

在这里,对编码 B 的转换没有帮助:

+5(5) -8 +4(4)

还要考虑以下实例(编码 B):

+5(9) -6 +4(4) -6 +5(7) -6 +4(6) -6 +5(9)

该序列将用于演示...

滑动窗口

首先,确定从左边开始的最佳解决方案:

+5 -6 +4 -6 +5 > 0 ==> 9+6+4+6+7=32

现在,扩展它以找到从第三个位置 (+4(4)) 开始的最佳解决方案:

+4 -6 +5 -6 +4 > 0 ==> 4+6+7+6+6=29

这个解决方案并不比我们发现的第一个更好。继续前行:

+5 -6 +4 -6 +5 > 0 ==> 7+6+6+6+9=34

这是最好的解决方案。该算法可以在 O(n) 中实现,因为头和尾只向前移动。

上面的简短描述并未涵盖所有细节(编码 B 左侧的负数,头尾相接,...)。此外,也许不需要重新编码,滑动窗口可以直接在 0-1 表示上实现。但是,我只有在重新编码后才能完全理解这个问题。

摆脱编码 B

实际上,正如 Millie Smith 善意地指出的那样,“编码 B”可能是有损的,这意味着它可能会在某些(尚未确定的)极端情况下导致较差的解决方案。但是滑动窗口算法在编码 A 上同样有效,所以甚至可能需要跳过对编码 B 的转换。(懒得重写算法的解释......)

于 2013-10-20T19:07:21.117 回答