当前位置：首页 > 编程日记 > 正文

1049 Counting Ones

编程日记 2024-09-07 22:40:00

1. 这一题起初我用递归的方式，还写了一个数整数有多少个1的函数，OneNum[i] = OneNum[i-1]+countOne(i);毫不意外地出现了段错误，也就是递归调用的次数太多。

2. 看了参考书，得到了思路上的启发：

给定一个数12，我们可以数从1到12，在个位上和十位上1这个数字各自出现了多少次，然后将二者相加。个位上在1-10中1出现了一次，在11-12中1出现了1次，共2次；十位上在10-12中1出现了3次，3+2=5。

如果一个数字还看不出规律，再举一个数123。个位上在1-10中出现1次，11-20中出现1次，……，120-123中出现一次，一共是123/10+1 = 13次，十位上在1-100中出现10次，在101-123中出现10次，一共是(123/100+1)*10 = 20次，百位上在100-123中出现了123-100+1=24次。

依然看不出，再举一个数1234。个位上出现1234/10+1=124次，十位上出现(1234/100+1)*10=130次，百位上出现(1200/1000+1)*100=200次，千位上出现1234-1000+1=235次。

依稀有些眉目了，但是刚才举得例子都是从大到小，现在再举一例4111。个位上出现4111/10+1=412次，10位上出现4111/100*10+(1-0+1)=412次，百位上出现4111/1000*100+(4111%100+1)=412次，千位上出现1*1000次。

可以看出如果当前位上的数字大于1，该位置上1出现多少次仅仅取决于前面的数字，如果等于1还取决于后面的数字。现在再举1例看看小于1的情况。

4001

对于个位：4001/10+1

对于10位：4001/100

对于100位：4001/1000

对于1000位：1*1000

abcde

e所在位:if(e<1)abcd,if(e>=1)abcd+1

d所在位：if(d<1)abc*10,if(d==1)abc*10+e+1,if(d>1)(abc+1)*10

c所在位：if(c<1)ab*100,if(c==1)ab*100+de+1,if(c>1)(ab+1)*100

b所在位：if(b<1)a*1000,if(b==1)a*1000+cde+1,if(b>1)(a+1)*1000

a所在位：if(a==1)bcde+1,if(a>1)1*10000

对于最低位和最高位可以特判。

将读入的整数n转化为字符串str,L为字符串的长度

首先将字符串翻转，最低位对应下标0。

if(str[0]<1)one_count += n/pow(10,i+1);else one_count += n/pow(10,i+1)+1；

最高位对应下标L-1

if(str[L-1]==1)one_count += n%pow(10,L)+1;else one_count += 1*pow(10,L)

对于当中任意位i

if(str[i]<1)one_count += n/pow(10,i+1)*pow(10,i)

if(str[i]==1)one_count += n/pow(10,i+1)*pow(10,i)+n%pow(10,i)+1

if(str[i]>1)one_count += (n/pow(10,i+1)+1)*pow(10,i)

注意一些细节：

1. pow得到的是浮点数，如果在mod后面会报错，如果在除号后面会导致除法的结果是浮点数，因此要在前面加强制类型转换。

新习得的方法：

1.从特殊到一般找规律

2.如果出错，用自己的测试用例debug

AC代码

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<bits/stdc++.h>
#include<stdlib.h>
#include<time.h>using namespace std;
typedef long long LL;const int maxn = 110;
const int MOD = 1000000007;
const int INF = 1000000000;//INF:下确界  
const LL SUP = (1LL<<63)-1;//SUP:上确界 
const double eps = 1e-5;int main(){int n;scanf("%d",&n);char temp[20],str[20];sprintf(temp,"%d",n);int L = strlen(temp);for(int i=0;i<L;i++){//将字符串反转 str[i] = temp[L-1-i];}int count_one = 0; //最低位 if(str[0]-'0'<1)count_one += n/10;else count_one += n/10+1;//最高位if(L-1>0){//防止只有1位数的特殊情况 if(str[L-1]-'0'==1)count_one += n%(int)pow(10,L-1)+1;else count_one += 1*(int)pow(10,L-1);}//中间位for(int i=1;i<L-1;i++){if(str[i]-'0'<1)count_one += n/(int)pow(10,i+1)*(int)pow(10,i);else if(str[i]-'0'==1)count_one += n/(int)pow(10,i+1)*(int)pow(10,i)+n%(int)pow(10,i)+1;else if(str[i]-'0'>1)count_one += (n/(int)pow(10,i+1)+1)*(int)pow(10,i);} printf("%d",count_one);return 0;
}

https://www.dkcj.cn/info/17741.html

1049 Counting Ones

相关文章：

Oracle:递归查询（树形结构数据）

FIN_WAIT_2

网页制作知识：XHTML 和 DOCTYPE 切换

1003 我要通过！

微信电视来了微信遥控传屏弹幕统统有

机器学习-线性回归LinearRegression

使用Windows的SHFileOperation外壳函数实现文件操作

(C++)寻找1-100以内所有素数，复杂度为O(nsqrt(n))与O(nloglogn)的两种方法

这样就算会了PHP么？-10

个人项目-小学四则运算 “软件”之初版

如何清晰地思考

1015 Reversible Primes

跨平台表空间传输(摘自eygle《循序渐进Oracle》)

EditPlus集成Java编译和运行命令组建轻量级Java SE开发工具

单例测试模式中【饿汉式】与【懒汉式】的区别

1078 Hashing

C# 多线程参数传递

Android 中自定义控件和属性(attr.xml,declare-styleable,TypedArray)的方法和使用

排序学习之---快速排序

1059 Prime Factors

适用于SQL Server生产环境DBA的七大技巧

关于PCA算法的一点学习总结

1096 Consecutive Factors

百度DisConf分布式配置框架源码试读（一）HttpClient 长连接

开篇第一题：经典中的经典！

(C++)高精度整数的存储、读入、比较和四则运算

TP-link 设置MAC地址过滤

flask的客户端服务端

1023 Have Fun with Numbers

Oracle中Hint深入理解(原创)