LeetCode：计算各位数字都不同的数字个数

"C++实现计算各位数字都不同的数字个数的方法" 在给定的代码中，主要讨论了三种不同的方法来解决一个特定的问题：计算在0到10^n（不包括10^n）范围内，各位数字都不相同的整数的数量。这个问题来源于LeetCode的一个挑战，具有一定的算法和组合数学背景。以下是每种方法的详细说明： 1. **暴力回溯遍历法**： - 这种方法使用递归辅助函数`helper`，通过回溯的方式尝试构建所有可能的数字。对于每个数字的每一位，它会检查是否已经使用过该数字，并且在不允许以0开头的情况下处理0的特殊性。如果当前位数已达到目标位数`cur_n`，则增加计数器`ret_val`表示找到一个符合条件的数字。这种方法的时间复杂度是O(10^n)，因为它需要遍历所有可能的数字组合。 2. **排列组合法**： - 这种方法基于组合数学的原理，考虑到每个位置可以选择的数字数量随着已选择数字的增加而减少。例如，对于第一个位置有10个选择，第二个位置有9个选择（因为不能与第一个位置相同），依此类推。因此，对于n位数字，总的可能性可以表示为10 * 9 * ... * (11-n)。这种方法比回溯法更高效，因为它不需要实际生成所有的数字，只需计算组合数即可。 3. **查表法**： - 在问题规模较小的情况下，可以预先计算出所有可能的数字数量并存储在一个表格中。由于题目限制，n的最大值为10，所以这个方法适用于此场景。这不是一种投机取巧的方式，而是利用了问题的特性，提高了效率。 在C++代码实现中，`Solution`类包含两个公共方法，`countNumbersWithUniqueDigits`是主方法，它根据输入的n值调用适当的算法。对于n小于或等于1的情况，可以直接返回预定义的结果，对于n大于10的情况，将其限制为10，以避免不必要的计算。`helper`函数是实现回溯法的私有辅助方法，它接受当前计数值、当前位置、当前已选数字的数组以及一个记录已访问数字的标记数组。 代码中的执行结果显示，采用排列组合法的解决方案在LeetCode平台上运行时间为92ms，这表明这种方法在性能上优于暴力回溯法。