递归求解

n = 3421

3421 = 1000 * [1*] + 3 * [0 - 999] + 1 * [0 - 421]

999 = 100 * [1*] + 9 * [0 - 99] + 1 * [0 - 99]

99 = 10 * [1*] + 9 * [0 - 9] + 1 * [0 - 9]

421 = 100 * [1*] + 4 * [0 - 99] + 1 * [0 - 21]

21 = 10 * [1*] + 2 * [0 - 9] + 1 * [0 - 1]

3421 = 1000 * [1*] + 3 * [0 - 999] + 1 * [0 - 421] 代表 3421 中 1 的个数 为

1000 个 1_ _ _

3 个 [0 ~ 999] 中的 1 的个数

余数部分 的 [0~421] 中的 1 的个数

class Solution {
public:
    unordered_map<int , int > rec;
    int numberOf1Between1AndN_Solution(int n) {
        if (n < 1) return 0;
        else if (n <= 9) return 1;

        if (rec.count(n)) return rec[n];
        // 9981
        string ns = to_string(n);
        int f = ns[0] - '0';
        int a = pow(10, ns.size() - 1); // 1000
        int r = n % a ;// 981
        int res = 0;
        if (f > 1){
            // printf("%d = %d * [1*] + %d * [0 - %d]  +  1 * [0 - %d]\n",n, a, (f), a - 1, r);
            res += a + (f) * numberOf1Between1AndN_Solution(a - 1) + numberOf1Between1AndN_Solution(r);
        }
        else if (f == 1){
            // printf("%d = %d * [1*] + 1 * [0 - %d] + 1 * [0 - %d] \n", n, r + 1,  a - 1,  r);
            res += (r + 1) + numberOf1Between1AndN_Solution(a - 1)  + numberOf1Between1AndN_Solution(r);
        }
        rec[n] = res;
        return res;
    }
};