整数中1出现的次数(从1到n整数中1出现的次数)
整数中1出现的次数(从1到n整数中1出现的次数)
http://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
给定一个数n,从个位开始遍历到最高位。例如,312:
解题思路:
找出1在各个位上出现的次数之和。用dec来表示当前位上的数,d用来进位同时判断n是否到达最高位。
(1)个位上,d=10,n/d(d/10)+(若dec>1,则+d/10)/(若dec=1,则+((n-n/(d/10)(d/10))+1))=31+1=32
(2)十位上,d=100,n/d(d/10)+(若dec>1,则+d/10)/(若dec=1,则+((n-n/(d/10)(d/10))+1))=30+(2+1)=33
(3)百位上,d=1000,因为d>n,已经是该数的最高位了,n/d(d/10)+(若dec>1,则+d/10)/(若dec=1,则+(n-n/(d/10)(d/10)+1))=0+100=100
所以最终为165。
public int NumberOf1Between1AndN_Solution(int n) { int count = 0; for(int d=1;d<=n;){ d *=10; int dec=n%d/(d/10); count +=n/d*(d/10); if(dec>1){ count +=d/10; }else if(dec==1){ count +=n-n/(d/10)*(d/10)+1; } } return count; }
给自己提个醒。。(其他大佬的答案我都没看懂,我太菜了。。)