algorithm - 检查双空上的位串

Question

我的任务是编写一个算法来获取位字符串长度（如果这是正确的翻译）并计算所有不包含双空值的位字符串。

例如：“10101”会计算在内，而“10010”不会计算在内。

我的问题是，我不知道位串的正确数据类型，有人可以帮忙吗？

Answer 1

你的意思是你想找到给定长度的不包含“00”的位串的数量？

您可以在 O(log(the_length)) 时间内完成此操作。好的算法实际上根本不使用任何位串，因此不需要位串数据类型。

但是，如果您想实际制作位串并对其进行计数，请使用对您来说最简单的方法——整数或 1 和 0 的字符串。您的语言可能更容易操作字符串并检查它们是否有双零。无论您使用什么数据类型，这都需要 O(2^the_length) 时间。这很好，因为你只是在学习，但无论如何它都很慢，所以不要太担心选择最有效的表示。