AcWing 56 从1到n整数中1出现的次数
发布日期:2021-05-28 16:30:44 浏览次数:11 分类:技术文章

本文共 1116 字,大约阅读时间需要 3 分钟。

题目描述:

输入一个整数n,求从1到n这n个整数的十进制表示中1出现的次数。

例如输入12,从1到12这些整数中包含“1”的数字有1,10,11和12,其中“1”一共出现了5次。

样例

输入: 12输出: 5

分析:

直接枚举n个数,复杂度太高。现在比如51023,对于第一个数5 > 1,若最高位是1,有10000-19999共10000种情况;第二个数就是1,左边数是0-4时,右边可以是000-999,左边数为5时,右边数是000-023,一共5*1000+24=5024种情况;第三个数为0,要使它为1,左边可以是0-50,右边可以是0-99,共5100种情况;第四个数是2,当其为1时,左边可以是0-510,右边可以是0-9,一共5100种情况;第五个数是3,当其为1,左边的数可以是0-5102,共5103种情况。1一共出现了30337次。

通过上例可以发现,我们考察某数n=abcde时,比如考察c这一位,如果c大于1,则左边可以是0-ab,右边可以是0-99;如果c等于1,左边是0-ab-1时,右边可以是0-99,左边是ab时,右边可以是0-de;如果c等于0,则左边可以是0-ab-1,右边可以是0-99。所以我们需要求出每一位左边和右边的数是什么以及当前位的权值。

所以很容易得到以下程序:

class Solution {public:    int numberOf1Between1AndN_Solution(int n) {        if(!n)  return 0;        vector
num; while(n) num.push_back(n % 10),n /= 10; int ans = 0; for(int i = num.size() - 1;i >= 0;i--){ int l = 0,r = 0,t = 1; for(int j = num.size() - 1;j > i;j--) l = l * 10 + num[j]; for(int j = i - 1;j >= 0;j--) r = r * 10 + num[j],t *= 10; ans += l * t; if(num[i] == 1) ans += r + 1; else if(num[i] > 1) ans += t; } return ans; }};

 

转载地址:https://blog.csdn.net/qq_30277239/article/details/88378719 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:AcWing 57 数字序列中某一位的数字
下一篇:AcWing 55 连续子数组的最大和

发表评论

最新留言

逛到本站,mark一下
[***.202.152.39]2024年02月11日 02时16分17秒