43.1 ~ n 整数中 1 出现的次数 (Medium)*

class Solution {
public:
    int countDigitOne(int n) {
        if(n <= 0) {
            return 0;
        }
        if(n < 10) {
            return 1;
        }
        string num = to_string(n);
        int last = stoi(num.substr(1));
        int power = pow(10, num.length() - 1);
        if(num[0] == '1') {
            return countDigitOne(last) + countDigitOne(power - 1) + last + 1;
        }else {
            return power + (num[0] - '0') * countDigitOne(power - 1) + countDigitOne(last);
        }
    }
};