1~n整数中1出现的次数

2021-03-09

思路大致是依次统计每位1出现的次数，然后加和

具体思路：
1.从个位开始遍历到最后一位，记录当前处在第几位（i）
2.定义一个变量记录当前所处位的数值（key）
3.判断三种不同情况，对于不同的数值，计算该位可能出现1的所有次数，加到结果（sum）里

例如2104

遍历该位==0
假设遍历到十位，i==10,该位数值为0，则此时该位可能出现1的所有情况为：001x、011x、……、201x
共21种情况，即为前面的数字：n/i%10
遍历该位==1
假设遍历到百位，i==100，该位数值为1，同样的情况，依然加上为0的所有情况，不同之处在于要加上为1的情况：100、101、……、104，为后面数字+1：n%i+1
else
相比==0的情况只需要将前面的数字+1即可，比如遍历到个位，相比2100只是多2101的情况：(n/i/10+1)*i

class Solution {
    public int countDigitOne(int n) {//2104
        int sum=0;
        for(long i=1;i<=n;i*=10){//每位出现1的次数取决于前面的位数
            long key=n/i%10;//获得第i位数字
            if(key==0)
                sum+=n/i/10*i;
            else if(key==1)
                sum+=n/i/10*i+n%i+1;
            else
                sum+=(n/i/10+1)*i;
        }
        return sum;
    }
}