欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数字统计,统计在1到n之间2出现的次数

程序员文章站 2024-03-14 20:50:23
...

数字统计,统计在1到n之间2出现的次数

我的思路是把这个数从右往左进行判断,即从个位往最高位判断
我们假设一个数1234
个位,把它分为1-1230 ,和 1231-1234
个位出现次数为: 123 * 1 + 1
十位,分为1-1200,和 1201-1234
十位出现次数为: 12 * 10 + 10
百位,分为1-1000 和 1001-1234
百位出现的次数为:1 * 100 + 35
千位分为 null 和1-1234
千位出现的次数为:0 * 1000 + 0
res = 389
时间复杂度为logn

#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
scanf("%d",&n);
int x=1;
int m=n;
int res=0;
while(n){
    x=x*10;
    int l,r;
    l=m/x,r=m%x;//l代表左边部分,r代表右边部分
    res += l*(x/10);//加上右边部分的值
    if(n%10>2){res += x/10;}//大于2时+前数位级/10
    if(n%10==2){res += m%(x/10)+1;}//等于2时+不包含当前位的右边部分+1
    n=n/10;
}
cout<<res<<endl;
}
相关标签: 算法