给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。
示例:
输入: 13 输出: 6 解释: 数字 1 出现在以下数字中: 1, 10, 11, 12, 13 。
解题思路：
1.参考：https://www.cnblogs.com/grandyang/p/4629032.html
通过上面的列举我们可以发现，100以内的数字，除了10-19之间有11个‘1’之外，其余都只有1个。如果我们不考虑[10, 19]区间上那多出来的10个‘1’的话，那么我们在对任意一个两位数，十位数上的数字(加1)就代表1出现的个数，这时候我们再把多出的10个加上即可。比如56就有(5+1)+10=16个。如何知道是否要加上多出的10个呢，我们就要看十位上的数字是否大于等于2，是的话就要加上多余的10个'1'。那么我们就可以用(x+8)/10来判断一个数是否大于等于2。
对于三位数区间 [100, 199] 内的数也是一样，除了[110, 119]之间多出的10个数之外，共21个‘1’，其余的每10个数的区间都只有11个‘1’，所以 [100, 199] 内共有21 + 11 * 9 = 120个‘1’。那么现在想想[0, 999]区间内‘1’的个数怎么求？根据前面的结果，[0, 99] 内共有20个，[100, 199] 内共有120个，而其他每100个数内‘1’的个数也应该符合之前的规律，即也是20个，那么总共就有 120 + 20 * 9 = 300 个‘1’。
代码：
class Solution { public: int countDigitOne(int n) { int res = 0, a = 1, b = 1; while (n > 0) { res += (n + 8) / 10 * a + (n % 10 == 1) * b; b += n % 10 * a; a *= 10; n /= 10; } return res; } };
对于（x+8）/10的理解：考虑res += (n + 8) / 10 * a + (n % 10 == 1) * b; n>=2和n<2会造成一个a的区别，a可以理解为个位、十分位、百分位等上1的个数，所以结合上面的描述，就是说尾数>=2的时候，就会有额外的1出现。关于这块可结合下面的解法。
2.参考：https://blog.csdn.net/geekmanong/article/details/51050854
利用数学归纳法，直接对n进行分析，归纳总结规律
例如n=abcde五位数，我们分析百位的c，主要有以下三种情况：
1）当c == 0的时候，比如13013，此时百位出现1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，12100~12199共1300个，显然这个由高位数字决定，并且受当前位数影响，结果为：（高位数字）乘以（当前位数）；
2）当c == 1的时候，比如13113，此时百位出现1的肯定包括c=0的情况，另外还需要考虑低位的情况即：00100 ~ 00113共114个，结果为：（高位数字）乘以（当前位数）+（低位数字）+1；
3）当c >= 2的时候，比如13213，此时百位出现1的是：00 100 ~ 00 199， 01 100~01 199，……，11 100~ 11 199，12 100 ~ 12 199，13100~13199，共1400个，这个仅由高位数字决定，结果为：（高位数字+1）乘以当前位数。
代码：
class Solution { public: int countDigitOne(int n) { if (n <= 0) return 0; long count = 0; long factor = 1; while (n / factor) { long lower = n%factor; long cur = (n / factor) % 10; long higher = n / (factor * 10); switch (cur) { case 0: count += higher*factor; break; case 1: count += higher*factor + lower + 1; break; default: count += (higher + 1)*factor; } factor *= 10; } return (int)count; } };