题解 | #JZ31 整数中1出现的次数#

    public int NumberOf1Between1AndN_Solution(int n) {
        //出现的总数其实就是各个位置上的1的个数的和
        //当前位，n(i),cur
        //高位n(N)....n(i+1)，high
        //低位n(i-1)...n(1),low
        //注意当前位出现1的个数其实是和当前位的digital是挂钩的，比如是十分位，那么可能有10...19出现1，有10个
        //而百分位就成了100...199出现1，有100个数，以此类推
        //而像是10分位的1，有几个10...19出现呢？这就看高位了，至少会有0~high-1共有high个

        //不管是当前位是什么，总会有(0~high-1) * digital的基本盘，就是看当前位的值决定是否能多捞点
        //如果当前位是0如2007的第二位，那么在当前位可能出现1的次数为，         high*digital
        //如果当前位是1如2017的第二位，那么在当前位可能出现1的次数为           high*digital+low+1
        //如果当前位是2...9如2037的第二位，那么在当前位可能出现1的次数为       (high+1)*digital
        int cur = n % 10;
        int high = n / 10;
        int low = 0;
        int digital = 1;
        int res = 0;
        while(cur!=0||high!=0){
            res+=high*digital;
            if(cur==1){
                res+=low+1;
            }else if(cur!=0){
                res+=digital;
            }
            low += cur * digital;
            digital *= 10;
            cur = high%10;
            high /= 10;
        }
        return res;
    }