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

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

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

第七十题
方法一:直接遍历,并且按位统计
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        
        // 方法1:直接遍历n个数,每个数判断有几个1
        int num = 0;
        // 遍历到n
        for (int i = 1; i <= n; ++i)
        {
            // 直接按位判断是不是结果
            for (int a = i ; a > 0; a = a/10)
            {
                if (a%10 == 1)
                    ++num;
            }
        }
        
        return num;
    }
};


方法二:按位的价值统计
class Solution {
public:
    int NumberOf1Between1AndN_Solution(int n) {
        
        // 方法2:思路:200-300 和 300-400 出现的次数应该是一样的
        // 所以。我只要知道这一位出现过多少次就好了,
        // 比如说1-1000 在个位出现过几次100次1-9 所以总共第一位只会有一100次1,价值为1
        // 在十位的 出现过10次,每次价值为10 (11,12,13。。。)
        int ans = 0;
        int value=1;
        int num=n;
        while(num!=0)
        {
            int temp=num/10*value;
            // 判断边界
            // 如果说当前的数字大于1,说明是会出现过完整的一次
            // 假设是124 看的是十位的1,因为到了24 说明 前面的10、11、12都是全的,所以要直接加上
            if(num%10>1) 
                temp=temp+value;
            // 看到上面124 就要想到 115 这种情况,十位是1,那么出现的次数就不是value了
            // 就要看最后一位是5,说明 十位出现过5次
            // 在比如说 2158,看百位是1,就要加上最后两位的值58
            if(num%10==1)
                temp=temp+(n%value)+1;
            num/=10;
            value*=10;
            ans+=temp;
        }
        return ans;
    }
};

题解 文章被收录于专栏

一遍做剑指offer 一边保存做题步骤 并附带详细注释哦

全部评论

相关推荐

挣K存W养DOG:我记得好多人说这个公司就是白嫖方案的,现在有大体方案要让你给他展示实现细节了,也是无敌了
点赞 评论 收藏
分享
02-08 20:56
已编辑
南京工业大学 Java
在等offer的比尔很洒脱:我也是在实习,项目先不说,感觉有点点小熟悉,但是我有点疑问,这第一个实习,公司真的让实习生去部署搭建和引入mq之类的吗,是不是有点过于信任了,我实习过的两个公司都是人家正式早搭好了,根本摸不到部署搭建的
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务