233. Number of Digit One (H)

Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.

Example:

Input: 13
Output: 6
Explanation: Digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.

我的答案：pseudo一遍过，第一遍错在第一个case 输入是-1

class Solution {
public:
    unordered_map<int,int> m{{0,0},{1,1}};
    
    int countDigitOne(int n) {
        if (n <= 0) return 0;
        // cout << n << endl;
        int p_max = (int)log10(n);
        int num_p_max = BuildLibrary(p_max);
        
        int first_element = n/pow(10,p_max);
        int ans = 0;
        if (first_element >= 2) {
            ans = pow(10,p_max) + num_p_max*first_element;
        }
        else {
            ans = n - pow(10,p_max) + 1 + num_p_max;
        }
        
        if (n > 10) {
            int remainder = n - pow(10, p_max)*first_element;
            ans += countDigitOne(remainder);
        }
        
        return ans;
    }
    
    int BuildLibrary(int p) { 
        // p : max digit length, eg. p=2, i=0~99
        if (m.find(p) != m.end()) {
            return m[p];
        }
        
        m[p] = pow(10, p-1) + 10*BuildLibrary(p-1); // 1..... & {0,2,3,...,9}.....
        return m[p];
    }
};

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Number of Digit One.
Memory Usage: 6.9 MB, less than 8.33% of C++ online submissions for Number of Digit One.

基本思路是：

• 首先要递归，但是递归需要用到点DP来加速

• BuildLibrary里面每个p对应的是0~10^p-1里面有几个1，退出机制有0=0，1=1两个。（一开始我忘了0=0这个退出机制）

• BuildLibrary里面，因为0到10^{p-1是全部都考虑的饱和情况，所以打头的有0到9一共10种情况，1打头的自动都+1，一共10}(p-1)个1打头的，然后其他的就是10*BuildLibrary(p-1)，加起来就是m[p]

• 回到主函数，提取出第一位的值是first，那么0~(first)*10^(p)-1是饱和的

  • 如果first==1，remainder = n-10^(p)，那么就是
    • 0~10^(p)-1: m[p]
    • 10^(p)~ n: countDigitOne(remainder) + (n-10^(p)+1)，开头的1每个元素都有，加上不考虑开头的1有几个就看remainder了
  • 如果first>=2，remainder = n-10^(p)*first，那么就是
    • 开头是1的数量：10^p
    • 不考虑开头1，不考虑remainder的数量：first*m[p]
    • 考虑remainder: countDigitOne(remainder)