找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6390|回复: 4
收起左侧

[米群网刷题小分队] Leetcode: Number of Digit One

[复制链接]

43

主题

0

精华

301

积分

高级会员

Rank: 3Rank: 3

积分
301
发表于 7-7-2015 08:01 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
1. 每次循环只计算这一位有多少1
2. 对于每一位,分大于等于2,等于1,小于1考虑

class Solution {
public:
    int countDigitOne(int n) {
        int res=0;
        long left, right, len=1;
        if (n<=0) return 0;
        while (n>=len) {
            left = n/len;
            right = n%len;
            if ((left%10)>=2)
                res+= (left/10+1)*len;
            else if ((left%10)==1)
                res+= (left/10)*len+ (right+1);
            else
                res+= (left/10)*len;
            len *= 10;
        }
        return res;
    }
};

12

主题

0

精华

195

积分

资深会员

Rank: 2

积分
195
发表于 7-10-2015 12:21 AM | 显示全部楼层
楼主能不能解释一下啊???
想不明白
回复 支持 反对

使用道具 举报

0

主题

0

精华

2

积分

新米人

Rank: 1

积分
2
发表于 7-10-2015 02:41 PM | 显示全部楼层
貌似这道题,编程之美里面有很好的解释。顺便附上代码:
   int countDigitOne(int n) {
        int ones = 0;
        for (long long m = 1; m <= n; m *= 10) {
            int a = n / m, b = n % m;
           int remain = a % 10;
           if (remain >= 2 && remain <= 9) ones += (a / 10 + 1) * m;
           else {
               ones += a / 10 * m + (a % 10 == 1) * (b + 1);
           }
        }
        return ones;
    }
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表