美文网首页
编程之美-leetcode 233:整数中1出现的次数(从1到n

编程之美-leetcode 233:整数中1出现的次数(从1到n

作者: yesski | 来源:发表于2019-02-22 15:44 被阅读0次

    解题思路来源:
    链接:https://www.nowcoder.com/questionTerminal/bd7f978302044eee894445e244c7eee6
    来源:牛客网
    leetcode 233题
    难度:困难
    求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数?为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数(从1 到 n 中1出现的次数)。

    思路:是一道找规律的题
    以数字a= 2593,n=5为例来观察:
    对于个位数来说:有2593=25910+3,在一个完整的10里面(即0-9),5会出现一次,那么对于个位数来说,至少出现了259个5,然后再是结尾2591, 2592, 2593 这三个数的个位数上面没有出现5,因此对于个位数上面 出现5的个数是295个
    对于十位数来说:2593=25
    100+93,在一个完整的100里面,十位数上出现 5的次数是10次(50,51,52,53,54,55,56,57,58,59),所以2500这部分出现5的次数是250次,再看93这部分,又因为十位数上面,9>5,因此对于十位数上面出现5的次数是10次,
    所以 十位数上面出现5的次数是 250+10;
    对于百位数来说:2593=2*1000+593,在一个完整的1000里面,百位数上面出现5的次数是500,501,502,503,一直到599 也就是100个, 那么2000的这部分 5一共会出现200次
    对于593这部分, 由于百位数上面为5 等于我们要的5,这上面出现的次数就由他的低位决定了: 也就是93再加+1也就是算上(500)这个

    到此为止,已经计算出全部数字 5 的出现次数。

    总结一下以上的算法,可以看到,当计算右数第 i 位包含的 X 的个数时:

    image.png
    public  static  int nums(int a,int n){
            int high,tmp,cur,low,count=1;
            high=a;
            int sum=0;
            while(high!=0){
                high=a/(int)Math.pow(10,count);// 获取第i位的高位
                tmp = a%(int)Math.pow(10, count);
                cur=tmp/(int)Math.pow(10,count-1);// 获取第i位
                low=tmp%(int)Math.pow(10,count-1);// 获取第i位的低位
                if(cur==n){
                    sum+= high*(int)Math.pow(10, count-1)+low+1;
                }else if(cur<n){
                    sum+=high*(int)Math.pow(10, count-1);
                }else{
                    sum+=(high+1)*(int)Math.pow(10, count-1);
                }
                count++;
            }
            return  sum;
        }
    

    相关文章

      网友评论

          本文标题:编程之美-leetcode 233:整数中1出现的次数(从1到n

          本文链接:https://www.haomeiwen.com/subject/tqyeyqtx.html