1. 云栖社区>
  2. >
  3. 正文

digit-counts

作者:用户 来源:互联网 时间:2018-08-31 11:19:24

算法与数据结构

digit-counts - 摘要: 本文讲的是digit-counts, 计算数字k在0到n中的出现的次数,k可能是0~9的一个值 您在真实的面试中是否遇到过这个题。   Yes 样例 例如n=12

计算数字k在0到n中的出现的次数,k可能是0~9的一个值 您在真实的面试中是否遇到过这个题。   Yes 样例

例如n=12,k=1,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],我们发现1出现了5次 (1, 10, 11, 12) 

暴力解法:

class Solution {
public:
    int digitCounts(int k, int n) {
        int ans=0;
        for(int i=0;i<=n;i++){
            ans+=count(i,k);
        }
        return ans;
    }
    int count(int num,int k){
        string tmp=to_string(num);
        int res=0;
        for(int i=0;i<tmp.size();i++){
            if(tmp[i]-'0'==k) res++;
        }
        return res;
    }
};


线性时间复杂度O(n):

class Solution {
public:
    /*
     * param k : As description.
     * param n : As description.
     * return: How many k's between 0 and n.
     */
    int digitCounts(int k, int n) {
        // write your code here
        if(n==0){
            return k==0?1:0;
        }
        
        int digits=0;
        int p=1;
        while(n>=p){
            digits++;
            p*=10;
        }
        int back=0;
        int cur=n%10;
        int pre=n/10;
        
        int res=0;
        int cnt=1;
        while(cnt<=digits){
            if(cur>k){
                res+=(pre+1)*pow(10,cnt-1);
            }else if(cur==k){
                res+=pre*pow(10,cnt-1)+back+1;
            }else{
                res+=pre*pow(10,cnt-1);
            }
            back=cur*pow(10,cnt-1)+back;
            cur=pre%10;
            pre=pre/10;
            cnt++;
        }
        return k==0?res-10:res;
    }
};




以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索算法与数据结构 ,以便于您获取更多的相关知识。

弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率

40+云计算产品,6个月免费体验

现在注册,免费体验40+云产品,及域名优惠!

云服务器9.9元/月,大学必备