计算1到N中包含数字1的个数
转自:http://pandonix.iteye.com/blog/204840 Mark
N为正整数,计算从1到N的所有整数中包含数字1的个数。比如,N=10,从1,2...10,包含有2个数字1。
相信很多人都能立刻得出以下的解法:
for(n:N)
{
判断n包含1的个数;
累加计数器;
}
这是最直接的解法,但遗憾的是,时间复杂程度为O(N*logN)。因为还需要循环判断当前的n的各位数,该判断的时间复杂程度为O(logN)。
接下来就应该思考效率更高的解法了。说实话,这道题让我想起另外一道简单的算法题:
N为正整数,计算从1到N的整数和。
很多人都采用了循环求解。然后利用初等数学知识就知道S=N*(N+1)/2,所以用O(1)的时间就可以处理。
再回到本道题目,同理应该去寻找到结果R与N之间的映射关系。
分析如下:
假设N表示为a[n]a[n-1]...a[1],其中a[i](1<=i<=n)表示N的各位数上的数字。
c[i]表示从整数1到整数a[i]...a[1]中包含数字1的个数。
x[i]表示从整数1到10^i - 1中包含数字1的个数,例如,x[1]表示从1到9的个数,结果为1;x[2]表示从1到99的个数,结果为20;
当a[1]=0时,c[1] = 0;
当a[1]=1时,c[1] = 1;
当a[1]>1时,c[1] = 1;
当a[2]=1时,c[2] = a[1] +1+ c[1] + x[1];
当a[2]>1时,c[2] = a[2]*x[1]+c[1]+10;
当a[3]=1时,c[3] = a[2]*a[1] +1+ c[2] + x[2];
当a[3]>1时,c[3] = a[3]*x[2]+c[2]+10^2;
......
以此类推
当a[i]=1时,c[i] = a[i-1]*...*a[1] +1+ c[i-1]+x[i-1];
当a[i]>1时,c[i] = a[i]x[i-1]+c[i-1]+10^(i-1);
代码:
int main()
{
int N;
cin>>N; int N1=N/;
int N2=N%;
int N3;
int x=;
int y=;
int cnt=(N2==?:);
while(N1>)
{
N3=N1%;
if (N3==);
else if (N3==)
{
cnt=N2++x+cnt;
}
else
{
cnt=N3*x+cnt+y;
}
N2=*N2+N3;
N1=N1/;
x=*x+y;
y=y*;
} cout<<cnt<<endl; return ;
}
最新文章
- JVM内存管理&;GC
- ASP.NET Web 应用程序及页面生命周期
- ASP.NET MVC 使用带有短横线的html Attributes(转载)
- 10_放置街灯(Placing Lampposts,UVa 10859)
- Google Code Jam 2010 Round 1C Problem B. Load Testing
- stm32 smartcard调试--不用st8024
- Codeforces 716B Complete the Word【模拟】 (Codeforces Round #372 (Div. 2))
- Java(基础)的类与变量
- django2.0+linux服务器 ,如何让自己电脑访问
- [HNOI 2008]越狱
- DSAPI多功能组件编程应用-网络相关(中)
- Memcache分布式锁 转发 https://www.cnblogs.com/li150dan/p/9529090.html
- python之路-字符串
- 14.python与数据库之mysql:pymysql、sqlalchemy
- mybatis 调用 oracle 存储过程 select into 无记录时NO_DATA_FOUND异常处理分析
- [译] OpenStack Ocata 版本中的 53 个新功能盘点
- qstring转string
- 【Leetcode】【Medium】Add Two Numbers
- java开发_mysql中获取数据库表描述_源码下载
- js 函数节流throttle 函数去抖debounce