[LeetCode]Numbers At Most N Given Digit Set

对于道题来说，我们可以把问题转化为，对于输入N，假设其有d位。对于给定的digits，判断位数为d且小于等于N的用digits组成的数有多少个。因为所有由digits的数组成的数，如果位数小于d，都满足小于等于N的要求。假设digits有m个，长度为d的由digits组成的数就有m^d个。
所以最后问题就落在，如何求位数等于d的小于等于N的数的数量。这样的话，我们就需要从最高位开始依次遍历：

• 如果当前位位第k位(从右向左从1开始算)，其数字为x，如果digits存在y个小于x的digit。那么我们可以肯定至少有m^(k - 1) * y个数是一定小于N的
• 对于digit大于x的数我们不需要考虑
• 如果digit中存在等于x的数，我们只靠当前位无法确定当前位取x的话，还能找到多少小于等于N的数，所以需要继续遍历下一位。

时间复杂度O(log N)，N为输入数字的大小。代码如下：