赞
踩
描述:计算数字k在0到n中的出现的次数,k可能是0~9的一个值
样例:例如n=12,k=1,在 [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12],我们发现1出现了5次 (1, 10, 11, 12)
之前看了很多算法思想,都很复杂,而且在LintCode里面也无法百分之百通过,说明还是存在一定的缺陷的,所以就在这不细说了。下面讲一下算法思想:
思想:假如我们把一个数看成几个十位几个各位几个百位,那么就有如下形式:(a,b,c,d,e...),对于这些关系,我们考虑下个位十位百位的情况下就有如下情况(先不考虑k=0):
个位:0000k,0001k......abcdk,共abcd+1个//k<=e
或者
0000k,0001k......(abcd-1)k,共abcd个//k>e
十位:000k0.....000k9.....(abc-1)k0...(abc-1)k9,共abc*10个//k>d
或者
000k0.....000k9.....abck0...abck9,共(abc+1)*10个//k<d
或者
000d0.....000d9.....abcd0...abcde,共abc*10+e+1个//k==d
以此类推,就可以求出来。
对于k=0的情况,如果看了上面的例子就发现想0000k,0001k...这些都要减去即可。
- public class Solution {
- /**
- * @param k: An integer
- * @param n: An integer
- * @return: An integer denote the count of digit k in 1..n
- */
- public int digitCounts(int k, int n) {
- int count = 0;
- if(n%10 >= k)
- count++;
- for(int i=10;i <= n;i *= 10){
- count += n/i*i/10;
- if((n%(i*10))/i==k)
- count += n%i+1;
- if((n%(i*10))/i>k)
- count += i;
- if(k==0)
- count -= i;
- }
- return count;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。