查找位串中最長的零序列

給定一個像「0001100001」這樣的位串，我需要找到最長零序列的長度（在本例中爲4）。查找位串中最長的零序列

算法應該在O（log（b））時間執行，其中b是字符串的長度。

我所聽到的，我必須在某種程度上位左移，以達到預期的複雜性，但我不知道爲什麼......

我只知道如何做到這一點的線性時間遍歷字符串。

我該如何獲得對數時間？

2017-04-23 de_dust

只讀取輸入將已經花費O（b）時間。 – Henry

@亨利：那麼，如果我們離開這個呢？還有一種方法可以實現日誌時間嗎？從作業提示說，我需要將位左移：第一個位，然後是2位，然後是4位，8位，16位等......每次移位後，我需要使用AND功能爲那些和那會給我下一個序列，我轉移...但我不知道如何使用 –

我不能證明它，但我的直覺告訴我沒有。 – Henry

-2

由於數量將被給定爲字符串，我們可以分析使用

Integer.parseInt(String,Base)

如果我們傳遞說64是二進制百萬和最長0的長度爲6的數量，而循環應該運行log2（64）這是6，那麼這個解決方案應該是你正在尋找的。請檢查下面

public class CountZeroes { 
private static long getZeroes(String s) { 
    int x = Integer.parseInt(s,2); 
    long count = 0, maxSoFar = 0; 
    while (x > 0) { 
     System.out.println("Running"); 
     if ((x & 1) == 1) { 
      if (count > maxSoFar) { 
       maxSoFar = count; 
      } 
      count = 0; 
     } else { 
      count += 1; 
     } 
     x = x >> 1; 
    } 
    return maxSoFar; 
} 

public static void main(String[] args) { 
    System.out.println(getZeroes("10000")); 
    System.out.println(getZeroes("100000")); 
    System.out.println(getZeroes("1000000")); 
} 
}

的解決方案，我已經運行這個程序16,32和64，並在它的log（n）的工作時間，因爲是涉案人物沒有解析字符，並且同樣採用按位運算符一樣。如果這是好的，請檢查一次。

謝謝

來源

2017-04-23 16:06:23

1.'Integer.parseInt'逐字符解析字符串2.右移等效於逐字符解析（它只移位1位），所以您高效地執行兩次操作 –

我正在將一個整數而不是一個字符串它基本上將整數除以2，這應該是log（n）時間的情況。 –

將整數除以2，但它不會將位長減2，嘗試所有位爲1的數並計算將執行多少次移位 –

查找位串中最長的零序列

回答

相關問題