leetcode 902. Numbers At Most N Given Digit Set
题目链接
Given an array of digits which is sorted in non-decreasing order. You can write numbers using each digits[i] as many times as we want. For example, if digits = ['1','3','5'], we may write numbers such as '13', '551', and '1351315'.
Return the number of positive integers that can be generated that are less than or equal to a given integer n.
单纯的进制问题，没有0好做多了
以n是一个m位数为举例，如果是k进制，那么位数小于m的数包括，1位k个数，2位k^2 ..... m-1位k^(m-1); 把这些数相加
再计算位数为m的数，看n的当前位上的数s[i]在k个数digits的位置
如果s[i]大于k个数中j个数，那么后面低位排列组合就是：j * k^(当前第几位-1)
s[i] ==digits[j] 刚好在位置上的就计算下一位；
s[i]不在digits中就没必要继续计算了，因为没有边界问题了
class Solution {
public:int atMostNGivenDigitSet(vector<string>& digits, int n) {bool dg[10] = {false}, stl=true;for (auto c : digits) dg[c[0]-'0'] = true;long dp[11] = {0},dlen = digits.size(), rst = 0, cl;dp[0] =1;for (int i = 1 ; i < 11; i++) dp[i] = dlen*dp[i-1];auto s = to_string(n);int slen = s.size();for (int i = 0 ; i< slen; i++) {rst += dp[slen -i -1];if (stl) {cl = 0;for (int j = 0; j< s[i]- '0'; j++) if (dg[j]) cl++;if (i==slen-1 && dg[s[i]-'0']) cl++;rst += dp[slen -i -1] *cl;if(!dg[s[i]-'0']) stl = false;}}return rst-1;}
};