题解 | #整数中1出现的次数（从1到n整数中1出现的次数）#

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        if (n <= 0) {
            return 0;
        }
        string str = to_string(n);             
        return numberOf1(str);
    }


    int numberOf1(string str){
        int length = str.size();      
        if (length == 1) {
            return  str[0] == '0' ? 0 : 1;
        }

        // 21345为例，把他分为了1~1345和1346~21345 numFirstDigit和numOtherDigits用于统计1346~21345的1中的个数 
        // numRecursive 用于统计1~1345的个数，这样分是为了好迭代，轮询次数就是N的位数，也就是logN  + 1，复杂度就是O(logN),其中log以10为底

        //  首位为1的数有多少 1就出现了多少次（只考虑首位的1，其他位数的1不考虑 只考虑首位为最高位 比如21345 只考虑10000~21345 首位为万位 不考虑1345这种首位为千位）
        int numFirstDigit = 0;
        if(str[0] > '1') {
            //  当首位大于1时，首位为1的数即10000~19999的所有数  20000~21345首位不是1（2x...x 3x..x中首位为1的数为0）
            numFirstDigit = pow(10, length - 1);  
        }
        else if (str[0] == '1') {
            //  当首位大于1时，首位为1的数即10..0~1x..x的所有数 即(x..x - 0..0) + 1 即 x..x + 1 上一个判断也可以这么算 9999 + 1 就是10^4 
            numFirstDigit = stoi(str.substr(1)) + 1;
        }
        //  统计其他位为1的个数，再将数分为1346~11345和11346~21345 然后算后4位出现1的次数。每一段后4位其实都是0000~9999的组合
        //  以选择其中1位为1，其他位在0~9这10个数中任意选，就是10^length(其他位） 每一位都可以被选择一次 就是length*10^(length - 1)
        //    ps 统计不是排列组合的种数，是1的次数，以1211为例，选第一位为1时，1211计了一个1，选第三位为1时，也会排列出1211，但是这也只计了一个1，所以对统计1的个数来说，没有重复
        int numOtherDigits = (length - 1) * pow(10, length - 2);       
        //  如果N=31345 就要分为3段，1346~11345、11346~21345、21346~31345 所以要乘以分的段数 即首位的值
        numOtherDigits *= (str[0] - '0');   //  这里拆成两步好解释理解 实际可以写成一步 int numOtherDigits = (str[0] - '0') * (length - 1) * pow(10, length - 2);
        int numRecursive = numberOf1(str.substr(1));  

        return numFirstDigit + numOtherDigits + numRecursive;
    }
};