《剑指offer》面试题43:1-n整数中1出现的次数

题目：给定一个整数n，求1~n这n个整数中十进制表示中1出现的次数。例如，输入12,1-12这些整数中包含1的数字有1,10,11和12,1一共出现了5次。

思路：

对于数字n，计算它的第i(i从1开始，从右边开始计数)位数上包含的数字1的个数：

假设第i位上的数字为x的话，则

1.如果x > 1的话，则第i位数上包含的1的数目为：(高位数字 + 1）* 10 ^ (i-1) (其中高位数字是从i+1位一直到最高位数构成的数字)

2.如果x < 1的话，则第i位数上包含的1的数目为：(高位数字 ）* 10 ^ (i-1)

3.如果x == 1的话，则第i位数上包含1的数目为：(高位数字) * 10 ^ (i-1) +(低位数字+1) (其中低位数字时从第i - 1位数一直到第1位数构成的数字)

基于以上思路，参考代码如下：

int NumberOfDigitOne(int n) {
if( n < 0)
return 0;
int i = 1;
int high = n;
int cnt = 0;
while(high != 0)
{
high = n / pow(10 ,i);//high表示当前位的高位
int temp = n / pow(10, i - 1);
int cur = temp % 10;//cur表示第i位上的值，从1开始计算
int low = n
- temp * pow(10, i - 1);//low表示当前位的低位
if(cur < 1)
{
cnt += high * pow(10, i - 1);
}
else if(cur > 1)
{
cnt += (high + 1) * pow(10 ,i - 1);
}
else
{
cnt += high * pow(10, i - 1);
cnt += (low + 1);
}
i++;
}
return cnt;
}

测试用例：

a.功能测试（输入5、10、55、99等）。
b.边界值测试（输入0、1等）。
c.性能测试（输入较大的数字，如10000、21235等）。

参考：

https://www.cnblogs.com/wangkundentisy/p/8946858.html

最后

以上就是乐观小甜瓜为你收集整理的《剑指offer》面试题43:1-n整数中1出现的次数的全部内容，希望文章能够帮你解决《剑指offer》面试题43:1-n整数中1出现的次数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。