902.最大为N的数字组合

链接：902.最大为N的数字组合
难度：Hard
标签：数组、数学、字符串、二分查找、动态规划
简介：返回 可以生成的小于或等于给定整数 n 的正整数的个数 。

题解 1 - cpp

• 编辑时间：2022-10-18
• 内存消耗：8MB
• 编程语言：cpp
• 解法介绍：先统计少一位数的情况，再对于位数相同的情况进行遍历。

class Solution {
public:
    int getCnt(int n, int &first, int &firstNum) {
        int ans = 0;
        for (; n; n /= 10) {
            ans++;
            if (n < 10) first *= n, firstNum = n;
            else first *= 10;
        }
        return ans;
    }
    int atMostNGivenDigitSet(vector<string>& digits, int n, bool empty = true) {
        if (n == 0) return 0;
        if (n < 10) {
            int idx = digits.size() - 1;
            while (idx >= 0 && digits[idx][0] - '0' > n) idx--;
            return idx + 1;
        }
        int firstNum, first = 1, cnt = getCnt(n, first, firstNum), sum = 0, ans = 0;
        for (int i = 1; i < cnt; i++) sum += pow(digits.size(), i);
        int idx = digits.size() - 1;
        string s = to_string(n);
        while (idx >= 0 && digits[idx][0] - '0' > firstNum) idx--;
        if (idx < 0) return empty ? sum : 0;
        if (digits[idx][0] - '0' == firstNum) {
            int _first = 0, _firstNum = 0;
            if (getCnt(n - first, _first, _firstNum) == cnt - 1) ans += atMostNGivenDigitSet(digits, n - first, false);
            idx--;
        }
        ans += (idx + 1) * pow(digits.size(), cnt - 1);
        return empty ? ans + sum : ans;
    }
};