我昨天在算法测试中遇到了这个问题,我无法找到答案.它让我绝对疯狂,因为它值得大约40分.我认为大多数课程都没有正确解决,因为我在过去24小时内没有提出解决方案.
给定长度为n的任意二进制字符串,如果存在,则在字符串中找到三个均匀间隔的字符串.编写一个在O(n*log(n))时间内解决此问题的算法.
所以像这样的字符串有三个"均匀间隔"的字符串:11100000,0100100100
编辑:这是一个随机数,所以它应该可以适用于任何数字.我给出的例子是为了说明"均匀间隔"的属性.所以1001011是一个有效的数字.1,4和7是均匀间隔的.
Shr*_*saR 127
最后!跟进sdcvvc的答案中的引导,我们得到了:问题的O(n log n)算法!在你理解之后它也很简单.那些猜测FFT的人是对的.
问题是:我们给出了一个S长度为n的二进制字符串,我们希望在其中找到三个均匀间隔的1.例如,S可以是110110010,其中n = 9.它在位置2,5和8处均匀间隔1秒.
S从左向右扫描,并列出1 L的位置.对于S=110110010上述,我们有列表L = [1,2,4,5,8].该步骤是O(n).现在的问题是要找到一个长度为3的算术级数中L,即找到不同的a,b,C中L,使得BA = CB,或者等效A + C = 2b中.对于上面的例子,我们想要找到进展(2,5,8).
为每个k in创建一个多项式 p,其项为x k.对于上面的例子,我们使多项式p(x)=(x + x 2 + x 4 + x 5 + x 8).该步骤是O(n).L
使用快速傅里叶变换找到多项式q= p 2.对于上面的例子,我们得到多项式q(x)= x 16 + 2x 13 + 2x 12 + 3x 10 + 4x 9 + x 8 + 2x 7 + 4x 6 + 2x 5 + x 4 + 2x 3 + x 2.该步骤为O(n log n).
忽略除了对应于某些k in的x 2k的所有术语.对于上面的示例,我们得到的术语X 16,3× 10,X 8,X 4,X 2.如果您选择执行此步骤,则此步骤为O(n).L
这里的关键点:任何系数X 2B为b中L是精确的对数(A,C)中L,使得A + C = 2b中.[CLRS,Ex.30.1-7]一个这样的对是(b,b)总是(所以系数至少为1),但是如果存在任何其他对(a,c),则系数至少为3,来自(a,c) )和(c,a).对于上面的例子,由于AP(2,5,8),我们将x 10的系数精确地设为3.(由于上述原因,这些系数x 2b将始终为奇数.并且q中的所有其他系数将始终为偶数.)
那么,该算法将查看这些项x 2b的系数,并查看它们中的任何一个是否大于1.如果没有,则没有均匀间隔的1.如果有是一个b在L为其中的系数X 2b的是大于1,则我们知道有一些对(A,C) -以外的(B,B) -其为A + C = 2b中.要查找实际的对,我们只是尝试每一个在L(对应ç是2B-A ),看看是否有一个1在位置2B-A中S.该步骤是O(n).
总而言之,伙计们.
有人可能会问:我们需要使用FFT吗？很多答案,如测试的,flybywire的,和RSP的,建议,检查每对1S的,并认为如果有一个1在"第三"的位置,该方法可能为O工作(N log n)的基础上,直觉如果有太多的1,我们会很容易找到一个三元组,如果有太少的1,检查所有对只需要很少的时间.不幸的是,虽然这种直觉是正确的,简单的方法是为O更好(N 2),它是不是好显著.正如在sdcvvc的答案中,我们可以采用长度为n = 3 k的字符串的"Cantor-like set",在其三元表示仅具有0和2(无1)的位置处具有1.这样的字符串具有2 ķ = N (日志2)/(对数3) ≈ñ 0.63那些在它和没有均匀间隔1秒,所以检查所有对将是在它的1的数目的平方的数量级:这是4 ķ ≈ñ 1.26不幸是渐近比(N log n)的大得多.事实上,最糟糕的情况更糟糕:Leo Moser在1953年(有效地)构造了这样的弦,其中n 1-c /√(log n) 1s但没有均匀间隔的1s,这意味着在这样的弦上,简单方法将采取Θ(N 2-2C /√(log n)的) -只是一个微小的一点优于Θ(N 2),令人惊讶!
大约1秒的在长度为n,没有3对均匀隔开的那些的一个字符串(我们在上面看到的是至少最大数目Ñ 0.63从容易坎托状结构,和至少Ñ 1-C /√(log n)的与Moser的建筑) - 这是OEIS A003002.它也可以直接从OEIS A065825计算为k,使得A065825(k)≤n<A065825(k + 1).我写了一个程序来找到这些,结果发现贪婪的算法没有给出最长的字符串.例如,对于n = 9,我们可以得到5 1s(110100011)但贪婪只给4(110110000),对于n = 26我们可以得到11 1s(11001010001000010110001101)但贪婪只给8(11011000011011000000000000),并且n = 74我们可以得到22 1s(11000010110001000001011010001000000000000000010001011010000010001101000011),但贪婪只给16(11011000011011000000000000011011000011011000000000000000000000000000000000).他们确实在很多地方达成一致,直到50岁(例如38到50岁).正如OEIS的参考文献所说,似乎Jaroslaw Wroblewski对这个问题感兴趣,并且他在这些非平均集上维护着一个网站.确切的数字只有194个.
sdc*_*vvc 35
您的问题在本文(1999)中称为AVERAGE :
问题是3SUM-hard如果存在问题的子二次减少3SUM:给定n个整数的集合A,A中的元素a,b,c是否a + b + c = 0？目前尚不清楚AVERAGE是否为3SUM-hard.但是,从AVERAGE到3SUM有一个简单的线性时间减少,我们省略了其描述.
维基百科:
当整数在[-u ... u]范围内时,通过将S表示为位向量并使用FFT执行卷积,可以在时间O(n + u lg u)中求解3SUM.
这足以解决你的问题:).
什么是非常重要的是,为O(n log n)的是在零和一的数量方面的复杂性,而不是那些的计数(可以给出一个数组,如[1,5,9,15]).检查集合是否具有算术级数,1的条件是很难的,并且根据1999年的那篇论文,没有比O(n 2)更快的算法,并且推测它不存在.没有考虑到这一点的每个人都试图解决一个开放的问题.
其他有趣的信息,大多数是无关紧要的:
下限:
一个简单的下限是类似Cantor的集合(数字1..3 ^ n-1在它们的三元扩展中不包含1) - 它的密度是n ^(log_3 2)(大约0.631).因此,任何检查集合是否不是太大,然后检查所有对都不足以得到O(n log n).你必须更聪明地调查序列.这里引用了更好的下界- 它是n 1-c /(log(n))^(1/2).这意味着Cantor集不是最佳的.
上限 - 我的旧算法:
众所周知,对于大n,不包含算术级数的{1,2,...,n}的子集最多具有n /(log n)^(1/20)个元素.论文在算术级数上的三元组证明了更多:该集合不能包含超过n*2 28*(log log n/log n)1/2元素.所以你可以检查是否达到了这个界限,如果没有,天真地检查对.这是O(n 2*log log n/log n)算法,比O(n 2)快.不幸的是"On triples ......"在Springer上 - 但是第一页是可用的,Ben Green的论述可以在这里找到,第28页,定理24.
顺便说一下,这些论文是从1999年开始的 - 与我提到的第一篇论文相同,所以这可能就是为什么第一篇论文没有提到这个结果.
z *_* - 8
我正在玩创建具有最大数量的序列,并且它们都非常有趣,我得到了125位数,这里是通过尝试插入尽可能多的"1"位而找到的前3个数字:
请注意,它们都是分形(考虑到约束,这并不太令人惊讶).可能有一些事情在向后思考,也许如果字符串不是具有特征的分形,那么它必须具有重复模式？
感谢beta以更好的术语来描述这些数字.
更新: 唉,当一个足够大的初始字符串开始时,看起来模式会崩溃,例如:10000000000001:
100000000000011
10000000000001101
100000000000011011
10000000000001101100001
100000000000011011000011
10000000000001101100001101
100000000000011011000011010000000001
100000000000011011000011010000000001001
1000000000000110110000110100000000010011
1000000000000110110000110100000000010011001
10000000000001101100001101000000000100110010000000001
10000000000001101100001101000000000100110010000000001000001
1000000000000110110000110100000000010011001000000000100000100000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101
100000000000011011000011010000000001001100100000000010000010000000000000110100001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001
100000000000011011000011010000000001001100100000000010000010000000000000110100001001000001000000110001000000001000000000000000000000000000000000000000010000001000000000000001100000000110010000000010010000000000001000000001000010000010010001001000001000000000000010000000000000000000000000000000000000000000000000000000000000000000000000000000000001000000000000000011000001000000000000000000000100100000000000000000000000000000000000011001000000000000000000000010010000010000001
1000000000000110110000110100000000010011001000000000100000100000000000001101000010010000010000001100010000000010000000000000000000000000000000000000000100000010000000000000011000000001100100000000100100000000000010000000010000100000100100010010000010000000000000100000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000110000010000000000000000000001001000000000000000000000000000000000000110010000000000000000000000100100000100000011
10000000000001101100001101000000000100110010000000001000001000000000000011010000100100000100000011000100000000100000000000000000000000000000000000000001000000100000000000000110000000011001000000001001000000000000100000000100001000001001000100100000100000000000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000100000000000000001100000100000000000000000000010010000000000000000000000000000000000001100100000000000000000000001001000001000000110000000000001
我怀疑一个看起来像O(n ^ 2)的简单方法实际上会产生更好的东西,比如O(n ln(n)).需要最长时间测试的序列(对于任何给定的n)是不包含三元组的序列,并且对序列中可以包含的1的数量施加严格的限制.
我想出了一些挥手的论点,但我找不到一个整洁的证据.我将在黑暗中采取刺痛:答案是一个非常聪明的想法,教授已经知道这么久以至于看起来很明显,但这对学生来说太难了.(无论是那个,还是你在讲述它的讲座中睡觉了.)