面试被问 “百元百鸡” 算法题，我从懵圈到秒解的心路历程

面试被问“百元百鸡”算法题，我从懵圈到秒解的心路历程

最近在面试中，一道看似简单的算法题把我难住了，题目是这样的：给定100元钱，需要购买100只鸡，其中公鸡每只5元，母鸡每只3元，小鸡1元能买3只，并且要求三种鸡都必须购买，问有哪些购买组合？刚听到这个问题时，我脑袋里瞬间闪过暴力枚举的思路，但又隐隐觉得面试官不会这么轻易放过我，肯定还有更优解，于是开启了一段紧张刺激的解题之旅。

一、初始思路：暴力枚举的尝试

最直观的想法就是用暴力枚举法，把所有可能的公鸡、母鸡、小鸡数量组合都遍历一遍，然后判断是否满足鸡的总数为100只且总花费为100元这两个条件。在面试现场，我迅速用代码实现了这个思路：

for x in range(1, 21):  # 公鸡最多买20只，因为20 * 5 = 100
    for y in range(1, 34):  # 母鸡最多买33只，因为33 * 3 < 100
        for z in range(3, 101, 3):  # 小鸡数量是3的倍数，最多买100只
            if x + y + z == 100 and 5 * x + 3 * y + z / 3 == 100:
                print(f"公鸡: {x}只, 母鸡: {y}只, 小鸡: {z}只")

这段代码通过三层嵌套循环，分别遍历公鸡、母鸡、小鸡可能的数量范围。在最内层循环中，对每一种组合进行条件判断，如果满足“百鸡百元”的要求，就输出该组合。提交代码后，虽然成功得到了答案，但我心里清楚，这种暴力枚举的方法效率极低。时间复杂度高达O(n³)，这里n取值较大（公鸡最多20，母鸡最多33，小鸡最多100），大量的无效计算在面试场景下显然是不够理想的，面试官也顺势问我有没有优化的办法。

二、第一次优化：缩小枚举范围

经过短暂思考，我意识到可以通过对题目条件的进一步分析来缩小枚举范围。从价格角度考虑，因为总金额是100元，所以公鸡数量x最多为100 / 5 = 20只，母鸡数量y最多为100 / 3 ≈ 33只。同时，由于已经确定了公鸡和母鸡的数量，小鸡数量z可以通过z = 100 - x - y来计算，这样就可以把原本的三层循环优化为两层循环。优化后的代码如下：

for x in range(1, 21):
    for y in range(1, 34):
        z = 100 - x - y
        if z % 3 == 0 and 5 * x + 3 * y + z / 3 == 100:
            print(f"公鸡: {x}只, 母鸡: {y}只, 小鸡: {z}只")

这次优化后，循环次数大幅减少，时间复杂度降为O(n²)。从实际运行效果来看，计算速度有了明显提升。在面试中，这一优化展示了我对算法复杂度的理解以及初步优化代码的能力，面试官微微点头，继续追问是否还有更优的解法，这促使我往更深层次去思考。

三、第二次优化：利用数学关系实现质的飞跃

看着题目中的两个关键等式：数量关系x + y + z = 100和金额关系5x + 3y + z / 3 = 100，我尝试通过数学推导来简化问题。首先，将金额等式两边同时乘以3，得到15x + 9y + z = 300。然后用这个式子减去数量等式，即(15x + 9y + z) - (x + y + z) = 300 - 100，化简后得到14x + 8y = 200，进一步化简为7x + 4y = 100，解出y = (100 - 7x) / 4。

因为x、y都必须是正整数，所以100 - 7x必须是4的倍数，且100 - 7x > 0（保证y为正数），由此可以推出x的取值范围。通过分析，x只能取4的倍数，且x <= 12（当x = 16时，7x = 112 > 100），这样x的可能取值就只有4、8、12。基于这个思路，代码可以优化为：

for x in range(4, 13, 4):
    y = (100 - 7 * x) // 4
    z = 100 - x - y
    print(f"公鸡: {x}只, 母鸡: {y}只, 小鸡: {z}只")

这次优化直接将时间复杂度降低到了O(1)，循环次数固定为3次，极大地提高了算法效率。