计算二进制字符串中的连续数字

Question

对于家庭作业问题，我们被要求定义一个函数来计算二进制字符串中的连续位数，并返回数字。在

例如，对于二进制输入S = ‘1111000000001111000111111111111111’，函数应该返回n = [4,8,4,3,15]。在

到目前为止，我已经知道了，但我知道这是不正确的，我不知道从这里到哪里去。任何帮助都将不胜感激！在

def consecutive_length(s):
    if s == '':
        return 0
    if s[0] == 0:
        return 0
    return 1 + consecutive_length(s[1:])

注意：我们不能使用任何循环。这需要我们用递归来完成。

谢谢你！在

Answer 1

我在这里假设“11”是1的连续序列，所以“111”有2个连续的1。这个解决方案是，如果循环不是问题的话。使用索引查找“11”并继续执行，直到找不到更多。下面的程序显示了连续1的数量。在

cnt = 0
pos = -1
while True:
    try:
        pos = '111001100101111'.index('11', pos+1)
        cnt += 1
    except ValueError:
        print cnt
        break

结果：

^{pr2}$

Answer 2

这里有一个充满希望的python方法（忽略了递归地解决这类问题不是python的事实）：

def consecutive_length(s):
    def sub(idx, lst, last_char, count):
        try:
            c = s[idx]     # c will be the 'next' char
        except IndexError: # no more chars left to process
            if count:
                lst.append(count)
            return lst
        if c != last_char:
            lst.append(count)
            count = 0
        return sub(idx+1, lst, c, count+1)                            
    return sub(0, [], s[0] if s else None, 0)

在哪里

• 外部函数只接受字符串作为参数，并隐藏内部函数的附加参数
• idx是字符串的索引，我们不会在每次递归调用时分配一个新的字符串（s[idx]是O（1）iirc）
• 我们不计算字符串的长度，而是等待异常发生（EAFP—请求原谅比请求许可更容易）

测试：

^{pr2}$

Answer 3

编辑：uselpa有一个更好的方法。在

因为不允许循环：

def consecutive_length(s, output, prev_char, count):
    # if end of string, append last count and return output
    if s == '':
        output.append(count)
        return output
    # if curr_char is same as prev_char, add 1 to count and parse next char
    if s[0] == prev_char:
        return consecutive_length(s[1:], output, s[0], count + 1)
    # if curr_char is diff from prev_char, append count and reset count to 1
    else:
        prev_char = s[0]
        output.append(count)
        return consecutive_length(s[1:], output, s[0], 1)

用consecutive_length(s, [], s[0], 0)调用它。在