- 正确答案：使用位图（bitset）模拟所有可能的硬币组合所能表示的金额，从1开始逐个检查最小的无法表示的正整数。通过位运算中的左移和按位或操作，动态维护当前能组合出的所有金额。最终，找到第一个为0的位即为答案。 - 解答思路： 1. 初始化一个位图（bitset），大小至少为所有硬币面值之和加1（实际可优化），初始时只有第0位为1（表示金额0总能表示）。 2. 遍历每个硬币面值，对该面值进行左移位操作，将当前位图左移该面值位数，再与原位图进行按位或，表示加入该硬币后能组成的新金额。 3. 每次更新位图，相当于将当前所有已能表示的金额加上当前硬币面值，得到新的可表示金额。 4. 遍历完所有硬币后，从第1位开始检查位图，第一个值为0的位置就是不能组合而成的最小正整数。 - 深度知识讲解：这个问题本质是“硬币组合问题”的变种，属于动态规划（Dynamic Programming）范畴，但使用位图（bitset）可以极大优化空间和时间效率，尤其适合硬币面值较小、数量不多的场景。核心思想是：用一个二进制位表示某个金额是否可被组合。例如，bitset 的第 i 位为 1 表示金额 i 可以由若干硬币组合而成。位图的位运算优势： - 左移（<<）：将当前所有可表示金额加上一个固定值（硬币面值）。例如，若当前能表示 {0,1,2}，对应 bitset 为 111，左移3位后变为 111000，表示 {3,4,5}。 - 按位或（|）：合并两个集合。将原集合与左移后的集合合并，得到加入新硬币后的新集合。算法流程：设 bitset 的大小为 max_sum + 1（max_sum 可取所有硬币之和，或更优的上界）。初始：dp[0] = 1 对每个硬币 c： dp |= dp << c 最后遍历 dp[i]，从 i=1 开始，第一个 dp[i] == 0 的 i 就是答案。时间复杂度：O(n * max_sum / w)，其中 w 是机器字长（如64），因为 bitset 的位运算是并行的。空间复杂度：O(max_sum) 该方法特别适合面试中快速编码且高效解决小数值硬币组合问题。扩展知识： 1. 若硬币面值互质，根据“Frobenius硬币问题”，两个面值 a,b 的最大不可表示数为 ab - a - b，但三个及以上无通解公式，必须用DP或bitset。 2. 该方法也可用于子集和问题、背包问题的优化实现，尤其当数值范围不大时，bitset 是常见优化技巧。 3. 在C++中，std::bitset 或 std::vector 可实现，但 std::bitset 需要编译时确定大小，可用 boost::dynamic_bitset 或手写数组+位运算。 - 代码示例（C++风格伪代码）： ``` #include #include #include int findSmallestUnattainable(std::vector& coins) { if (coins.empty()) return 1; std::sort(coins.begin(), coins.end()); if (coins[0] > 1) return 1; // 最小硬币大于1，则1无法表示 int max_sum = 0; for (int c : coins) max_sum += c; std::bitset<10000> dp; // 假设最大和不超过10000 dp[0] = 1; // 金额0可以表示 for (int c : coins) { dp |= dp << c; // 所有可能加上当前硬币 } for (int i = 1; i <= max_sum + 1; i++) { if (!dp[i]) return i; } return max_sum + 1; // 理论上不会走到这里 } ``` 注意事项： - 位图大小需足够大，否则会溢出。可先求和，或使用动态bitset。 - 若硬币中有重复，可先去重。 - 若硬币包含1，则所有正整数都可表示，答案不存在（但题目通常隐含无1的情况）。举例验证： coins = [2, 3, 5] 初始：dp = 1 (bit0=1) 加2：dp |= dp<<2 → dp = 101 (表示0,2) 加3：dp |= dp<<3 → 原dp=101，左移3→101000，或后：101101 (0,2,3,5) 加5：dp |= dp<<5 → 左移5后与原或，得到更多组合最终检查：i=1时dp[1]==0 → 返回1 但实际：2,3,5 无法组成1，所以答案是1。另一个例子：coins = [1, 2, 5] → 能组成所有>=1的数，所以答案是？但题目问“不能组合的最小整数”，若含1则答案为无穷，但实际应返回第一个无法表示的，即若从1开始都能表示，则返回 max_sum+1？但逻辑上应是：若1存在，则所有正整数都可表示，因此最小不能表示的是不存在。但题目通常假设硬币中不含1。更典型例子：coins = [3, 4, 5] 能表示：3,4,5,6(3+3),7(3+4),8(3+5或4+4),9(4+5),10(5+5),... 但1,2无法表示 → 最小是1。因此算法正确：只要1不在可表示集合中，就返回1。关键点：若最小硬币 > 1，则1一定无法表示，答案为1。否则需继续计算。优化：可先判断最小硬币是否为1，是则继续，否则返回1。总结：bitset移位法是解决此类“可达性”问题的高效手段，利用位并行加速状态转移，是面试中展示算法优化能力的亮点。

8.23-b站笔试

全站热榜

创作者周榜