专栏首页小樱的经验随笔统计0到n之间1的个数[数学,动态规划dp](经典,详解)

统计0到n之间1的个数[数学,动态规划dp](经典,详解)

问题描述

给定一个十进制整数N,求出从1到N的所有整数中出现”1”的个数。

例如:N=2时 1,2出现了1个 “1” 。

N=12时 1,2,3,4,5,6,7,8,9,10,11,12。出现了5个“1”。

方法一 暴力求解

最直接的方法就是从1开始遍历到N,将其中每一个数中含有“1”的个数加起来,就得到了问题的解。

下面给出代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 int main()
 5 {
 6     int n,x,t;
 7     while(scanf("%d",&n)!=EOF)
 8     {
 9         int ans=0;
10         for(int i=1;i<=n;i++)
11         {
12             t=i;
13             while(t)
14             {
15                 if(t%10==1)
16                     ++ans;
17                 t=t/10;
18             }
19         }
20         printf("%d\n",ans);
21     }
22     return 0;
23 }

该算法的时间复杂度为O(N*lgN)

(注:此方法对较大的数据有可能会TL)

解法二 

1位数的情况:

在解法二中已经分析过,大于等于1的时候,有1个,小于1就没有。

 2位数的情况:

N=13,个位数出现的1的次数为2,分别为1和11,十位数出现1的次数为4,分别为10,11,12,13,所以f(N) = 2+4。

N=23,个位数出现的1的次数为3,分别为1,11,21,十位数出现1的次数为10,分别为10~19,f(N)=3+10。

由此我们发现,个位数出现1的次数不仅和个位数有关,和十位数也有关,如果个位数大于等于1,则个位数出现1的次数为十位数的数字加1;如果个位数为0,个位数出现1的次数等于十位数数字。而十位数上出现1的次数也不仅和十位数相关,也和个位数相关:如果十位数字等于1,则十位数上出现1的次数为个位数的数字加1,假如十位数大于1,则十位数上出现1的次数为10。

 3位数的情况:

N=123

个位出现1的个数为13:1,11,21,…,91,101,111,121

十位出现1的个数为20:10~19,110~119

百位出现1的个数为24:100~123

 我们可以继续分析4位数,5位数,推导出下面一般情况: 

假设N,我们要计算百位上出现1的次数,将由三部分决定:百位上的数字,百位以上的数字,百位一下的数字。

如果百位上的数字为0,则百位上出现1的次数仅由更高位决定,比如12013,百位出现1的情况为100~199,1100~1199,2100~2199,…,11100~11199,共1200个。等于更高位数字乘以当前位数,即12 * 100。

如果百位上的数字大于1,则百位上出现1的次数仅由更高位决定,比如12213,百位出现1的情况为100~199,1100~1199,2100~2199,…,11100~11199,12100~12199共1300个。等于更高位数字加1乘以当前位数,即(12 + 1)*100。

如果百位上的数字为1,则百位上出现1的次数不仅受更高位影响,还受低位影响。例如12113,受高位影响出现1的情况:100~199,1100~1199,2100~2199,…,11100~11199,共1200个,但它还受低位影响,出现1的情况是12100~12113,共114个,等于低位数字113+1。

综合以上分析,写出如下代码:

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<map>
 4 #include<cstring>
 5 #include<string>
 6 #include<algorithm>
 7 #include<queue>
 8 #include<vector>
 9 #include<stack>
10 #include<cstdlib>
11 #include<cctype>
12 #include<cmath>
13 #define LL long long
14 using namespace std;
15 int CountOne(int n) {
16     int cnt = 0;
17     int i = 1;
18     int current = 0, after = 0, before = 0;
19     while ((n / i) != 0) {
20         current = (n / i) % 10;
21         before = n / (i * 10);
22         after = n - (n / i) * i;
23         if (current > 1)
24             cnt = cnt + (before + 1) * i;
25         else if (current == 0)
26             cnt = cnt + before * i;
27         else if (current == 1)
28             cnt = cnt + before * i + after + 1;
29             i = i * 10;
30     }
31     return cnt;
32 }
33 int main()
34 {
35     int n;
36     while(cin>>n){
37         int res=CountOne(n);
38         cout<<res<<endl;
39     }
40     return 0;
41 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2017广东工业大学程序设计竞赛初赛 题解&源码(A,水 B,数学 C,二分 D,枚举 E,dp F,思维题 G,字符串处理 H,枚举)

    Problem A: An easy problem Description     Peter Manson owned a small house in a...

    Angel_Kitty
  • C++ 标准库之 iomanip 、操作符 ios::fixed 以及 setprecision 使用的惨痛教训经验总结

    本菜鸡自从退役之后就再也没怎么敲过 C++ 代码,在 C++ 语言下,求解关于浮点数类型的问题时,之前有碰到类似的情况,但是似乎都没有卡这块的数据,基本上用一个...

    Angel_Kitty
  • CTF入门指南(0基础)

    ctf入门指南 如何入门?如何组队? capture the flag 夺旗比赛 类型: Web 密码学 pwn 程序的逻辑分析,漏洞利用windows、lin...

    Angel_Kitty
  • Docker中配置centos容器支持ssh

    image.png 在Docker起步中,已经下载了ubuntu系统镜像,启动容器后成功执行了一个简单的系统命令 此时的容器是封闭的,下面我们就建立起和容器的沟...

    dys
  • LintCode 加一题目分析代码

    样例 给定[1,2,3] 表示 123, 返回[1,2,4] . 给定[9,9,9] 表示 999, 返回[1,0,0,0]

    desperate633
  • Spring Boot入门系列(十四)使用JdbcTemplate操作数据库,配置多数据源!

    Spring Boot 除了Mybatis数据库ORM框架,还有JdbcTemplate等数据库操作框架,同样也比较简单实用,如果是一般简单的项目,用JdbcT...

    架构师精进
  • POJ2155

    因为最近准备模板,所以把不太常用的算法又熟悉了一边,发现果然不练不行。 二维线段树,树套树 #include<iostream> #include<cstdio...

    triplebee
  • 为什么我建议你多做数据仓库项目

    2010年,我到上海的第一年。年底回老家的时候,在火车站碰到一位之前的老同事。闲聊之中,发现他在寻找新的机会,原单位是老企业,没什么活力,年轻人上升空间有限。他...

    Lenis
  • 更强大的滚动控件RecyclerView

    Dream城堡
  • 《组织行为学》--群体行为及个人感悟

      我们上一节分析了个人维度的不同价值观、行为动机、态度、满意度等相关因素,从而使我们能够更好地理解他人,提高个人认知以及促进不同相关性的人之间达成合作关系。那...

    用户3003813

扫码关注云+社区

领取腾讯云代金券