专栏首页vblogPAT 1049 Counting Ones (30分) 编程之美--1的个数

PAT 1049 Counting Ones (30分) 编程之美--1的个数

题目

The task is simple: given any positive integer N, you are supposed to count the total number of 1's in the decimal form of the integers from 1 to N. For example, given N being 12, there are five 1's in 1, 10, 11, and 12.

Input Specification: Each input file contains one test case which gives the positive N (≤2​30​​ ).

Output Specification: For each test case, print the number of 1's in one line.

Sample Input:

12

Sample Output:

5

解析

题意:

给定一个正整数N,求从1-N的所有正整数中,1总共出现了几次。

思路:

这道题是《编程之美》上面的一道题(第2.4节),需要通过分析来总结规律,然后总结出公式,如果暴力去“数”1的个数,显然会超时。但如果通过公式来算的话,时间复杂度就直接降到O(1)。具体分析过程比较复杂,详情参见《编程之美》2.4节“1的数目”,这里只给出结论——从右往左拆解当前数字,逐位分析每个位置出现1的次数,然后统计其规律与当前位置左右部分数字的关系,最后累加,即为结果。

以数字N=345、N=305、N=315为例,寻找十位上是1的数字个数。将数字分成3部分:百位、十位、个位

  • N=345时,从1-345345个数中,百位数字可以出现0、1、2、3四种,每种百位数字都可以跟一个数字为1十位,而每种十位数字可以跟0-9这十种数字,所以从1~345345个数中,十位数字为1的数共有(3+1)×10=40个,故十位上的1共出现40次。
  • N=305时,百位上数字依然可以出现0、1、2、3四种,但要注意,百位数字为3时,后面不能再跟数字为1十位,因为这样的数字已经大于305了,所以从1~305305个数中,十位数字为1的数共有3×10=30个,故十位上的1共出现30次。
  • N=315时,百位上数字依然可以出现0、1、2、3四种,此时要注意,百位数字为3时,后面可以再跟数字为1十位,但这样的数字个位上只能出现0-56个数,即310、311、312、313、314、315,其他数字都会大于315,所以从1~315315个数中,十位数字为1的数共有3×10+(5+1)=36个,故十位上的1共出现36次。

综上,对于任意一个数字N,当要判断从右向左数第i位上1出现的次数num时,可以将这个数字分成三部分,分别用left、current、right表示,即left=数字N在i位左侧的数字、current=数字N在第i位的数字、right=数字N在i位右侧的数字。例如数字N=123456,判断从右向左第3位也就是百位上,即数字4所在位置1出现的次数时,left=123、current=4、right=56。此时分三种情况进行计算:

  • current=0:num = left × 10i
  • current=1:num = left × 10i+ (right + 1)
  • current>1:num = (left + 1) × 10i
  • 其中10^i^就表示的是当前处理的是个位、十位、还是百位、千位.......

所以如果使用result存储最后的答案,用a表示当前是个、十、百、千位……使用left表示左边部分表示的数字,right表示右边部分表示的数字。

从右往左(从个位往高位)开始遍历,判断当前位置的字符:

  • 若是0:则在当前位置可以出现1的次数为left * a次。
  • 若是1:则在当前位置可以出现1的次数为left * a + right + 1
  • 其他(2-9):则在当前位置出现1 的次数为(left+1)*a

代码

#include <iostream>
using namespace std;

int main() {
    int n, ans = 0, radix = 1, left, right, curr;
    cin >> n;
    while (n / radix) {
        left = n / (radix * 10); curr = n / radix % 10; right = n % radix;
        if (curr == 0) ans += left * radix;
        else if (curr == 1) ans += left * radix + right + 1;
        else ans += (left + 1) * radix;
        radix *= 10;
    } 
    cout << ans;
    return 0;
}

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

我来说两句

0 条评论
登录 后参与评论

相关文章

  • PAT 1033 To Fill or Not to Fill (25分) 贪心思想

    With highways available, driving a car from Hangzhou to any other city is easy. ...

    vivi
  • 简单公司职员信息管理系统

    vivi
  • PAT 1037 Magic Coupon (25分) 贪心+排序+负负/正正得正

    The magic shop in Mars is offering some magic coupons. Each coupon has an intege...

    vivi
  • 坚守安全第一准则!腾讯智慧校园通过“三级等保”测评

    ? 近日,腾讯智慧校园系统顺利通过“国家信息系统安全等级保护”三级(以下简称“三级等保”)测评,体现了腾讯智慧校园在安全防护方面的专业实力,证明其在网络信息规...

    腾讯智慧教育
  • Leetcode 581. 最短无序连续子数组

    给定一个整数数组,你需要寻找一个连续的子数组,如果对这个子数组进行升序排序,那么整个数组都会变为升序排序。

    zhipingChen
  • Linux kernel同步机制(上篇)

    在现代操作系统里,同一时间可能有多个内核执行流在执行,因此内核其实像多进程多线程编程一样也需要一些同步机制来同步各执行单元对共享数据的访问,尤其是在多处理器系统...

    Linux阅码场
  • 浅谈IPv6的风险防御

    最近的客户,从前年开始进行ipv4到ipv6的过渡,到目前为止,大部分设备处于双栈或者部分系统没有进行过渡更新。

    FB客服
  • [数据库连接池] Java数据库连接池--DBCP浅析.

    一枝花算不算浪漫
  • 深入解析:Oracle由11g而始的数据库一致读行为的改变

    崔华,网名 dbsnake Oracle ACE Director,ACOUG 核心专家 我们都知道,在Oracle数据库中是“未commit的数据我们读不到,...

    数据和云
  • 12岁小读者使用Python暴力破解Wi-Fi密码

    这一代后浪在父母的光环加持下,猛点技能点。有些从小学开始敲基因,有些一天能写2000首诗,有些发表的论文已经达到硕士毕业水平。但是在编程领域还有另外一群后浪,有...

    行哥玩Python

扫码关注云+社区

领取腾讯云代金券