二進制字符串（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 .....）問題

回答

相關問題