我得到一个看起来像这样的字符串:
1011010100
我的任务是找到一个子字符串的长度,其中空值的数量总是<=个数。这应该总是在从右到左和从左到右“扫描”子字符串时发生。所以在这个例子中,答案是:
10110101 => 8
我知道复杂度应该是 O(n) 或 O(n log n),因为长度可以达到 10^6
有任何想法吗?
我得到一个看起来像这样的字符串:
1011010100
我的任务是找到一个子字符串的长度,其中空值的数量总是<=个数。这应该总是在从右到左和从左到右“扫描”子字符串时发生。所以在这个例子中,答案是:
10110101 => 8
我知道复杂度应该是 O(n) 或 O(n log n),因为长度可以达到 10^6
有任何想法吗?
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
然而,我们很快就会看到这个测试用例的问题(正如 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
这是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)
。因此,为了拥有该属性,我们必须将 [相对] 高度设为正数。这可以通过使高度不小于初始高度来可视化。
这是我的算法:
从右侧开始:
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}
现在问题减少到从V
iei, 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
。因此得到了答案。
希望能帮助到你。如果您有疑问,请告诉我。谢谢。
对问题进行了两次重新编码(稍后删除了一个......)和一个滑动窗口。
您可以压缩输入以产生后续零或一的数量:
+1 -1 +2 -1 +1 -1 +1 -2
这会产生编码 A并且需要 O(n) 时间。
现在,在编码 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 表示上实现。但是,我只有在重新编码后才能完全理解这个问题。
实际上,正如 Millie Smith 善意地指出的那样,“编码 B”可能是有损的,这意味着它可能会在某些(尚未确定的)极端情况下导致较差的解决方案。但是滑动窗口算法在编码 A 上同样有效,所以甚至可能需要跳过对编码 B 的转换。(懒得重写算法的解释......)