为什么这个正则表达式不能匹配第二个二进制间隙？

Question

尝试解决这里列出的问题，我想尝试一下用正则表达式来捕获数字的二进制表示中的最大“二进制间隙”（零的链）。

我为此问题编写的函数如下：

def solution(N):
    max_gap = 0
    binary_N = format(N, 'b')
    list = re.findall(r'1(0+)1', binary_N)

    for element in list:
        if len(element) > max_gap:
            max_gap = len(element)

    return max_gap

它的表现相当不错。但是……由于某种原因，它不能匹配10000010000000001（66561的二进制表示）中的第二组零。9个零不在匹配列表中，所以必须是正则表达式的问题——但我看不出来哪里有问题，因为它与给定的每个其他示例都匹配！

- Barnabus

---

我认为你只需要 list = re.findall(r'1(0+)', binary_N)。不需要消耗右侧的 1。 - Wiktor Stribiżew

根据复杂度要求，你的算法是否符合要求（期望最坏时间复杂度为O(log(N))）？ 我考虑使用正则表达式，但最终决定不使用任何模块。第一个问题：使用正则表达式会增加或减少分数吗？还是这取决于考官？ 第二个问题：我想出了这个解决方案：http://pastebin.com/TNhx37JG 它有多好或多坏？如果我猜测，我会说复杂度是O(N)（因为我必须遍历所有位），但我无法猜测O(log(N))的复杂度。任何帮助都将是惊人的。谢谢！ - vabada

经过测试，它确实符合要求，尽管我承认它通过使用正则表达式略微违反了规则...你在Codility网站上尝试过你的解决方案吗？ - Barnabus

Answer 1

同一位不能包含在两个匹配项中。您的正则表达式匹配一个1后面跟着一个或多个0，并以另一个1结尾。一旦找到第一个匹配项，您将得到0000000001，它不以1开头，因此无法被您的正则表达式匹配。

如@JoachimIsaksson所提到的，如果您想匹配两组0，可以使用前瞻来检查最终的1，但不包括在匹配项中。r'1(0+)(?=1)'。

- Holloway

---

加分项是，你可以在正则表达式中使用先行断言使其不匹配（并消除）末尾的1；r'1(0+)(?=1)' - Joachim Isaksson

谢谢@JoachimIsaksson，我已经添加了。 - Holloway