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

统计1到N的所有数中1出现的次数，只需要计算1出现在每一位上的次数

分析：N有n位，将n位数记作(x1)...(xi-1)(xi)(xi+1)...(xn), 前i-1位组成的数记作X前, 后n-i位组成的数记作X后。

一般地，求第i位为1时的数字个数，分三种情况

1. N的第i位为0：X前要小于(x1)...(xi-1)，X后随意，共((x1)...(xi-1) )*10的n-i次方个
2. N的第i位为1: 两种情况A. X前小于(x1)...(xi-1)，X后随意，同上; B. X前为(x1)...(xi-1), X 后小于等于(xi+1)...(xn),共(xi+1)...(xn) + 1个
3. N的第i位大于1: X前(x1)...(xi-1)内取值, X后随意

class Solution {
public:
    int decimalLen(int N)
    {
        int len = 1;
        
        while ((N /= 10) != 0)
        {
            len++;
        }
        
        return len;
    }

    void split(int N, int len, int loc, int &x, int &k, int &y)
    {
        int tmp = pow(10, len - loc);
        x = N / (tmp * 10);
        y = N % pow(10, len - loc);
        k = (N / tmp) % 10;
    }

    int pow(int a, int b)
    {
        int ret = 1;
        for (int i = 0; i < b; i++)
        {
            ret *= a;
        }

        return ret;
    }
    
    int NumberOf1Between1AndN_Solution(int N)
    {
        int n = decimalLen(N);
        int sum = 0;
        for (int i = 1; i <= n; i++)
        {
            int x = 0;
            int k = 0;
            int y = 0;
            split(N, n, i, x, k, y); //将n位数N以i位为准，拆分成x,k和y三分部，其中k是第i位

            if (k == 0)
            {
                sum += x * pow(10, n - i);
            }
            else if (k == 1)
            {   
                sum += x * pow(10, n - i) + (y + 1);
            }
            else
            {
                sum += (x + 1) * pow(10, n - i);
            }               
            
        }

        return sum;
    }
};