整数中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;
}

给自己提个醒。。(其他大佬的答案我都没看懂,我太菜了。。)

全部评论

相关推荐

04-18 00:32
已编辑
中南大学 Java
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务