二进制字符串（01010 .....）问题

给定一串0和1。如何找到其中0和1的数目相等的子串的最大长度。二进制字符串（01010 .....）问题

2011-06-17 Sanjay Rajpal

+11

这是功课吗？ – greydet 2011-06-17 08:39:44

向我们展示您迄今为止所拥有的以及您卡在哪里。否则，聘请程序员为你做。 – shinkou 2011-06-17 08:43:21

添加“家庭作业”标签（假设它是作业，因为它听起来像一个CS问题，而不是一个现实的实际编程问题） – 2011-06-17 08:57:06

看到，因为你正在寻找匹配的标准，合理的算法将是最长的字符串：

start with whole string 
does string match criteria? 
yes: we're done 
no: 
    (1) find all sub strings of length (whole string - 1) 
    do any of these match the criteria? 
    yes: we're done 
    no: 
    repeat from (1) but use (whole string - 2), then (whole string - 3), etc until sub string length is 2

注意奇数长度的字符串不能满足所要求的标准，因此您可以减少程序的工作量。

你的下一个问题无疑将是'我如何在C中做这个'，这是你需要先做一些工作的地方（假设这是家庭作业，它看起来像）。你不会从这里得到'teh codez'。但是，如果您发布了一些无法按预期工作的代码，则会得到很多有用的建议，以指导您找到正确的解决方案。

来源

2011-06-17 08:55:58 Skizz

好skizz，非常感谢你的解决方案。 – 2011-06-17 12:24:59

算法的复杂性是什么？ – 2011-06-17 13:58:51

我70％确定它是n日志（n）...但数学现在有点棘手。 – Matt 2011-06-17 14:06:34

这是一个想法：将计数器对象放置在列表中的每个数字之间。现在，对于这些对象中的每一个，如果它们具有不相等的邻居（0和1，或1和0），则移除邻居，增加对象的计数器，并将其与邻居计数器对象合并。对于O（n^2）复杂度，您将不得不为O（n）对象执行总共O（n）次。

我们可以考虑一旦进入新邻居一个计数器对象的新邻居改善这种线性时间（它“吃”了当前的邻居，当它找到一个匹配。）

下面是一个例子。我会用X来对二进制串表示一个0，和Y表示1，用数字为计数器对象的当前值：

初始字符串：

X0X0X0Y0X0X0Y0Y0Y0X0X0Y

首先“打“：

X0X0 X0Y 0X0X0Y0Y0Y0X0X0Y - > X0X X0X0Y0Y0Y0X0X0Y

二 “撞”：

X0X1X0 X0Y 0Y0Y0X0X0Y - > X0X1X Y0Y0X0X0Y - > X0X Y0X0X0Y - > X X0X0Y

第三 “命中”：

X4X0 X0Y - > X4X1

没有更多的命中。您现在再次遍历所有计数器，并找到最大值，4（对） - >长度8，从索引1开始。

来源

2011-06-17 15:06:30 bdares

我在想这实际上是线性时间，但我似乎无法证明它。 – bdares 2011-06-17 15:08:48

啊，是的，考虑到计数器的新邻居不需要外部循环。这是线性时间。呵呵。这不仅仅是使用上下文无关的语法吗？ – bdares 2011-06-17 15:30:38

这是另一个可能比前面提到的运行时间更快的想法。

你有你的字符串1和0的。
保持变量“number_ones”为1的本串
保持串的初始长度的另一个变量（可选）
碱情况下，在数：初始化number_ones 1的存在的电流量字符串中
如果number_ones * 2 ==字符串的长度，你说对了，返回
否则，我们不得不缩短字符串
检查，我们投下了一个字符是一个或一个零。如果它是一个，从“number_ones”减1，否则如果它是零，则保持原样。
检查number_ones * 2 ==原始字符串的长度-n（n在本例中为1，并在每次出现错配时增加1）
重复步骤6-8直到条件为真。

对我来说，CS是关于创造性，寻找新的，更快的方式来解决明显的问题。这样可以节省你的时间，因为你只需要遍历一次字符串，然后检查下一个要删除的字符。这可能不是最好的方式，但希望它有帮助！

来源

2011-06-17 16:32:55

二进制字符串（01010 .....）问题

回答

相关问题