1.如何获取每一位数字的 左边数字 和 右边数字？

    数字3101592，假如现在cur = 0，base = 10000（是当前考虑的位数）， high是cur左边的部分、cur是当前位的数字、low是cur右边的部分。

    high = n / （base * 10） = n / 100000 = 31

cur = (n / base) % 10 = (n / 10000) % 10 = 0

low = n % base = n % 10000 = 1592

2.出现的次数取决于小于n的那些数，分情况讨论。

计算1出现的次数需要计算所有位上1出现的次数的加和，所以要遍历每一位，不断更新当前位前后的数字是什么。假设当前位是1时，计算1出现的次数。

  • 当cur = 0时

还是拿31 0 1592举例子，如果当前位出现1了，那必然是high是0-30区间内，因为如果是311开头就比n要大了。当high是0-30的时候，无论low怎么选都比n小，所以low的选法可以有0-9999种，而low的选法正好=base10000。将high * base就是这种情况下1出现的次数。

  • 当cur = 1时

cur = 1时 比如说310 1 592，需要分类讨论：

high从0 - 309时，low可以是0-999。所以是和cur = 0的情况一样的 => high * base

high是310时（1种选法），low只能是0 - 592（593种选法，是low + 1），low如果再大于592就比n要大了。 => 1 * （low + 1）

所以1的出现次数是（high * base） + （low + 1）

  • 当cur > 1时

cur大于1时，不需要再去考虑high和low怎么选不会比n大了。比如3101 5 92，high可以从 0 - 3101 而 low 可以从 0 - 99，所以直接就是 （high + 1） * base。

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int base = 1;
        int cnt = 0;
        while(base <= n) {
            int high = n / (base * 10);
            int low = n % base;
            int cur = (n / base) % 10;
            if(cur == 0) {
                cnt += high * base;
            }
            else if(cur == 1) {
                cnt += (high * base) +  (low + 1);
            }
            else {
                cnt += (high + 1) * base;
            }
            base *= 10;
        }
        return cnt;
    }
};