233. 数字 1 的个数
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例 1：
输入：n = 13
输出：6
解释：1 10 11 12 13
示例 2：
输入：n = 0
输出：0
提示：
0 <= n <= 1e9
解析
- 有这么一个规律：
所有一位数中包含1的个数为1，
所有两位数中包含1的个数为10+1*10 = 20（10-19，11，21-81，91）
所有三位数中包含1 的个数为100+20*10=300
所有四位数中包含1 的个数为1000+300*10=4000
若dp[n] 表示n位数总共包含1的位数，则dp[n]=10**(n-1)+10*dp[n-1]。
怎么发现的呢这个规律：999中包含1的个数可以拆解为：百位为1的数100-199包含1的个数为100个数（不看十位个位）。两位数 ：0-99包含1 的个数为dp[i-1],总共10种（0-9），因此三位数总1数 = 100 + 20 * 10
- 到这里题目才刚刚开始，假如给定一个数9017，这个数1的个数是不是可以拆解为9000 和 17 种各自1的个数之和；17中1的个数为10 和 7 种 1 的个数之和。于是9017 拆解为 7 10 9000的和了，所以我们从后往前遍历每个数字。
- 如果当前位为0直接跳过，017和17中1 的位数是相同的
- 如果当前位为1，只需要计算以当前1开头的数字的个数，例如17（包含1的有10 11 12 13 14 15 16 17），如果为117（那当前位数包含的1的个数为118，也就是前边所有位组成的数+1）
- 如果当前位大于1，例如9，我们需要计算的是9000包含1的个数 =（1000-1999 + 9*dp[i-1]）.
code
class Solution {
public:
int countDigitOne(int n) {
long dp[11];
dp[0]=0;
long base=1;
// 计算固定位数包含1的个数
for(int i=1;i<=10;i++){
dp[i]=base+dp[i-1]*10;
base*=10;
}
int k=n;
vector<int> vct;
vct.push_back(0);
while(k>0){
int tmp=k%10;
vct.push_back(tmp);
k/=10;
}
// 从个位到最高位，每一位作为最高位生成的数
// 例如 9017，vct[1]=7,vct[2]=17,vct[3]=17,vct[4]=9017
long base1=10;
for(int i=2;i<vct.size();i++){
vct[i]=vct[i-1]+vct[i]*base1;
base1*=10;
}
// 计算每一位产生1的数量
int i=1,res=0;
long base2=1;
while(n>0){
int tmp=n%10;
// 当前为位1，需要加上前边所有位产生的数，
// 大于1只需要tmp*dp[i-1]+最高位为1的所有数
if(tmp>1)
res+=base2+tmp*dp[i-1];
else if(tmp==1)
res+=vct[i-1]+1+dp[i-1];
n/=10;
base2*=10;
i++;
}
return res;
}
};
