网站建设bxw52关键词查网站

（害，做题是真的慢，这面试给我这题我估计就傻了）

题目：
给定一个整数 n，计算所有小于等于 n 的非负整数中数字 1 出现的个数。

题解：
首先看看整数范围 0 <= n <= 10^9 不能遍历（不过这也肯定不会简单到遍历）

比如存在一个数 25103，我们应该从哪里下手呢

我们是否可以考虑，各个位置上（个位，十位…）存在 1 的情况数量，然后相加得到结果呢

我们先考虑一般情况， 数字 xxx 4 yy，百位上，存在 1 的情况数量怎么算
想一想 100，101，102，…，199是不是百位上都是 1，这种情况 100 种
在考虑一下百位前面的 xxx，是不是总共有 (xxx + 1) * 100 种
（假设 xxx 是 123，那么 123 1 yy 有 100 种，122 1 yy 有 100 种 … 000 1 yy 有 100 种）

接下来稍微扩展一下一般情况，那数字 xxxx 4 y 十位上的情况是不是就是 (xxxx + 1) * 10 种

接下来考虑特殊情况，如果数字 xxx 1 yy 百位上是 1，这怎么算呢
当前面是 xxx 时，百位上为 1 的情况只有 yy 种，但是当前面是 (xxx - n) 时，情况有 100 种
所以是不是情况是 xxx * 100 + yy 种
（假设 xxx 是 123，那么 123 1 yy 有 yy种，但 122 1 yy，则没有这种限制，有 100 种）

再一种特殊情况，如果数字 xxx 0 yy 百位上是 0，这怎么算呢
其实就是当前面是 xxx 时，百位上为 1 的情况为 0 种，当前面是 （xxx - n) 时，情况也都有 100 种
所以情况是 xxx * 100 种

接下来写代码就行了

class Solution {
public:int countDigitOne(int n) {int res = 0;int f = 1;int nn = n / 10;while(nn != 0) {nn = nn / 10;f = f * 10;}int flag = 0;while(f != 0) {int t = n / f;n = n % f;if(t == 1) {res = res + n + 1 + flag * f;}else if(t == 0) {res = res + flag * f;}else {res = res + (flag + 1) * f;}flag = flag * 10 + t;f = f / 10;}return res;}
};