java - 找出可以用 1 和 0 写成的数的倍数

Question

给定数字 n (2 <= n <= 1000)，找到以 10 为底且只有数字 0 和 1 的最小非零倍数。示例:2 -> 10、3 -> 111、4 -> 100、7 -> 1001、11 -> 11、9 -> 111 111 111。

我的想法不太好: {/* n|2 和 n|5 +"000"(幻影(2,5)的最大值)-> n|3 + "111 "*/>

我认为，接下来的数字划分由数字 n 组成，其格式为 0/1。感谢您的帮助!

Answer 1

您可以使用 breadth first search .从排队开始 1 ，因为您的电话号码必须以 1 开头, 然后每次提取一个数字 x从您的队列中，查看它是否是 n 的倍数或不。如果是，则您有答案，如果不是，请插入 x * 10和 x * 10 + 1在队列中(按此顺序)。

请注意，您实际上不必存储 1 的整个字符串s 和 0 s 在你的队列中:它足以存储除以 n 的剩余部分以及一些可让您重建实际字符串的辅助信息。如果您需要有关此的更多详细信息，请回信。