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;
}