[leetcode] 233. Number of Digit One解題レポート

タイトルリンク:https://leetcode.com/problems/number-of-digit-one/
Given an integer n, count the total number of digit 1 appearing in all non-negative integers less than or equal to n.
For example: Given n = 13, Return 6, because digit 1 occurred in the following numbers: 1, 10, 11, 12, 13.
Hint:
Beware of overflow.
考え方:いくつかの法則を見つけることができます.
1.n=9の場合、1つのみ
2.n=99では、すべてのビット数が10回表示されるため、1ビット数が10回表示され、1ビット数が10回表示されるだけで、10-19の場合であるため、n=99では1が10*1+10=20で表示される.
3.n=999では、n=99が10回含まれ、100ビットで1が100回、100-199が現れることに相当するため、n=999では1が10*20+100=300の回数で現れる.
4,n=9999の場合、n=9999を10回含むことに相当し、千位に1000回1が現れるのは1000-199であるため、n=9999の場合1の出現回数は10*300+1000=4000である.
法則を見ることができます
1.nの最高位>1の場合、kをn桁と同じ最小値、すなわち10,100,1000…とする.　sum = n/10 * count(k-1) + k + count(n%k); 2.nの最高位=1の場合、kをn桁と同じ最小値、すなわち10,100,1000…とする.　sum = count(k-1) + n%k + count(n%k);
その原則は最高位から低位への再帰の処理である.
コードは次のとおりです.

class Solution {
public:
    int cal(int n)
    {
        if(n ==0) return 0;
        if(n <10) return 1;
        string str = to_string(n);
        int len = str.size(), k=pow(10, len-1);
        if(n/k > 1) return n/k * hash[len-2]+k + cal(n%k);
        return hash[len-2] + n%k+1 + cal(n%k);
    }
    int countDigitOne(int n) {
        if(n <=0 ) return 0;
        string str = to_string(n);
        int i = 0;
        hash.push_back(1);
        while(++i < str.size()-1)
            hash.push_back(pow(10, i) + 10* hash[i-1]);
        return cal(n);
    }
private:
    vector<int> hash;
};