剑指offer ( 面试题 32) -- 从1到n整数中1出现的个数

题目描述 : 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

解题思路 : 入下图所示将数据中每一位拿出来单独处理 , 为一位记为low

1. 个位   : 从 1 增加到n ,没增加 1 , low就会增加 1 , 当low增加到 9 时就又会从 1 开始从新计算 , 而1--9 出现的周期次数取决于高位的大小 , 

• 以下图为例 : 从1--n 的增长过程中 , 1--9 一共出现了45次 , 而当 low 大于 1 时 , 在第46次周期中 1 又出现了一次 , 所以个位上 1 出现的次数 count = high*1 + 1 = 46;  
• 当为 450 时 , low为 0 时 , 这是 count =  high*1 = 45 ;

1.  十位   :  如下图所示 , 和上面的方式一样 , 只不过每增加10 , low才会增加 1 , 即 high*10 , 下图中 , low大于 1 ,证明在第5次周期中出现了 10 次 1 ,  count = high*10 + 10 ;

• 如果是407 , low 为 0 , 证明 第4次周期后就停止了 , count = high*10 = 50 ;
• 如果是417 , low 为 1 , 第5次周期中 1 出现的次数就和个数数有关 , 用 digit 记录个位数字 , count = high*10 + digit + 1

• 总结 : 在计算 1 的个数是 , 就可以归结为个位和更高位

1. 对个位来说  当个位大于0 , 那么 1 出现的次数为 high + 1                                                                                                                             当个位等于0 , 那么 1 出现的次数为 high
2. 对其它位来说，记每一位的权值为base，位值为high，该位之前的数是digit，举例如图 base 开始为 10

则：

• 若low为0，则1出现次数为 high*base
• 若low为1，则1出现次数为 high*base + digit + 1
• 若low大于1，则1出现次数为 high*base + base

• 457 = ( 45 * 1 + 1) + ( 4 * 10 +10) + ( 0 * 100 + 100)
• 407 = ( 45 * 1 + 1) + ( 4 * 10  + ( 0 * 100 + 100)
• 417 = ( 41 * 1 + 1) + ( 4 * 10 + 7 + 1) + ( 0 * 100 + 100)

代码如下 : 

class Solution {
public:
int NumberOf1Between1AndN_Solution(int n)
{
if(n<1)
return 0;
int base=1;
int high=0;
int low=n;
int count=0;
while(low){
high=low%10;
low/=10;
count+=low*base;
if(high==1)
count+=(n%base+1);
if(high>1)
count+=base;
base*=10;
}
return count;
}
};

出处 ( 传送门 )  -- https://blog.csdn.net/yi_afly/article/details/52012593#commentBox

最后

以上就是失眠未来为你收集整理的剑指offer ( 面试题 32) -- 从1到n整数中1出现的个数的全部内容，希望文章能够帮你解决剑指offer ( 面试题 32) -- 从1到n整数中1出现的个数所遇到的程序开发问题。

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