Google Code Jam 2016：如何优化Bleatrix Trotter问题的代码？

嘿，这个问题挺有意思的，我来给你拆解一下怎么搞定Bleatrix的助眠数位收集挑战～

问题回顾 #

Bleatrix的规则很简单：选一个数字N，然后依次说出N、2×N、3×N……每说一个数，就把这个数的所有数位记下来，直到集齐0-9所有10个不同的数位，就停下来睡觉。我们要算的就是她最后说出的那个数（也就是刚好集齐所有数位时的倍数），或者判断有没有可能永远凑不齐。

先提前说结论：除了N=0的情况（因为0的倍数永远是0，只能收集到0这一个数位），所有正整数N最终都能集齐所有数位——毕竟数是无限大的，总能覆盖到所有数字组合。

解题核心思路 #

• 用一个容器（比如集合或布尔数组）来追踪已经见过的数位，初始是空的。
• 从倍数k=1开始，计算当前数k×N。
• 把当前数的每一位拆分出来，加入追踪容器。
• 检查容器是否包含了0-9所有数字：如果是，返回当前的k×N；如果不是，k加1，重复前面的步骤。
• 特殊处理N=0：永远凑不齐，返回类似"INSOMNIA"的提示。

Python代码实现 #

def find_last_said_number(n):
    if n == 0:
        return "INSOMNIA"
    seen_digits = set()
    multiplier = 1
    while len(seen_digits) < 10:
        current_num = multiplier * n
        # 把数字转成字符串，遍历每一位加入集合
        for digit in str(current_num):
            seen_digits.add(digit)
        multiplier += 1
    # 因为最后一次循环multiplier加了1，所以实际的数是(multiplier-1)*n
    return (multiplier - 1) * n

# 测试几个例子
print(find_last_said_number(1))  # 输出10（1到10刚好集齐所有数位）
print(find_last_said_number(2))  # 输出90（2、4...一直到90，覆盖所有数字）
print(find_last_said_number(0))  # 输出INSOMNIA

Java代码实现 #

如果用Java写，核心逻辑一样，用布尔数组来追踪会更高效：

public class BleatrixSleepHelper {
    public static String getLastNumber(int n) {
        if (n == 0) {
            return "INSOMNIA";
        }
        boolean[] digitsSeen = new boolean[10];
        int collectedCount = 0;
        int multiplier = 1;
        int currentNumber;
        
        while (collectedCount < 10) {
            currentNumber = multiplier * n;
            int temp = currentNumber;
            // 拆分每一位数字
            while (temp > 0) {
                int digit = temp % 10;
                if (!digitsSeen[digit]) {
                    digitsSeen[digit] = true;
                    collectedCount++;
                }
                temp /= 10;
            }
            multiplier++;
        }
        return String.valueOf((multiplier - 1) * n);
    }

    public static void main(String[] args) {
        System.out.println(getLastNumber(1)); // 输出10
        System.out.println(getLastNumber(2)); // 输出90
        System.out.println(getLastNumber(0)); // 输出INSOMNIA
    }
}

小提示 #

• 用集合的好处是自动去重，不用手动判断是否已经收集过这个数位；用布尔数组的话，访问速度更快，适合性能要求高的场景。
• 一定要记得处理N=0的特殊情况，不然程序会无限循环下去。

内容的提问来源于stack exchange，提问作者Mohit Bohra