剑指 Offer 43. 1～n 整数中 1 出现的次数 (opens new window)

1.按位搜索

核心思路是按照个位、十位...讨论每个位置上面的1的个数。其中left保存当前位左边的数值，right保存右边的数值，mid保存当前位上的值。其中根据mid的大小情况统计个数时可能存在以下几种情况，下面以5233为例，当前位为百位2：

• mid>1：表明当前已经出现过(5100~5199)，结果加上数位大小
• mid==1：表明当前正在进行，结果加上right+1。相当于5100~5133，那么需要加上33
• mid==0：表明right部分还没够到5100第一个1的位置。

这种题拿例子举例比较好，以54321为例

• 个位上每经过一次0~9循环1就出现一次，则个位上1出现的次数为5432+1次（若个位数为0，则1在个位上出现5432次）；

• 十位上，1出现的次数为543*10+1*10次（若十位数为1，则十位上1出现次数为543*10+2次）

• 百位上，1出现的次数为54*100+1*100次（若百位数为1，则百位上1出现次数为54*100+22次）；

• 千位上，1出现的次数为5*1000+1*1000次（若千位数为1，则千位上1出现次数为5*1000+322次）；

• 万位上，1出现次数为0*10000+1*10000次 代码如下：

class Solution {
    public int countDigitOne(int n) {
        long res=0;
        long base=10;
        while(base/10<=n){
            long left=n/base;
            long right=n%(base/10);
            long mid=(n-left*base)/(base/10);
            res+=left*(base/10);
            if(mid==1) res+=right+1;
            else if(mid==0) res+=0;
            else  res+=base/10;
            base*=10;
        }
        return (int)res;
    }
}

2.数位dp

定义dp[i]表示前i+1位的所有十进制数出现1的次数之和。