09 | #整数中1出现的次数(从1到n整数中1出现的次数)#

整数中1出现的次数(从1到n整数中1出现的次数)

http://www.nowcoder.com/practice/bd7f978302044eee894445e244c7eee6

通过数学归纳方法总结规律,可以类比得出这样的公式(可参考百位类比): alt

class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        long long multik = 1;
        for (int k = 0; n >= multik; k++) { /* multik代表10^k */
            long long multikTmp = multik * 10; /* 10^(k + 1) */
            res += ((n / multikTmp) * multik) + min(max((n % multikTmp) - multik + 1, 0LL), multik); /* 注意0LL */
            multik *= 10;
        }
        return res;
    }
};
每日算法 文章被收录于专栏

每日算法、玩转技术、聪明理财、幸福生活!

全部评论

相关推荐

不愿透露姓名的神秘牛友
今天 12:10
点赞 评论 收藏
分享
06-23 11:28
门头沟学院 Java
牛客91966197...:也有可能是点拒绝的时候自动弹的话术
点赞 评论 收藏
分享
程序员小白条:你是沟通了900个,不是投了900份简历,你能投900份,意味着对面都要回复你900次,你早就找到实习了,没亮点就是这样的,别局限地区,时间投的也要早,现在都要7月了
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务