360笔试第二题，高效解法
比如，在10进制中，23~267中199中“9”最多，所以返回结果就是2。
解题思路：对于上面的例子，可以这样来划分区间
各个子区间除了各位其他各位数字相同，所以含“9”最多的一定在下面这些数字中
那么最终的结果是下面两者中的最大值：2~25中“9”的个数+1、267.
如果右边界恰好是259的话，就直接是：2~25中“9”的个数+1
这便形成了简单的递归思路。（有兴趣的，可以用循环试着写写）
相比于从左边界到右边界穷搜（我笔试中的解法）肯定会快不少。
代码如下：
int getnumber(int k,int l,int r){
//cout<<l<<" "<<r<<endl;
if(r<k)return 0;//已经递归到个位数了。
l=l/k;
if(r%k==k-1)
{
r=r/k;
return getnumber(k,l,r/k)+1;
}
else //if(r%k!=k-1)
{
int tmp=countk(k,r);
r=r/k-1;
return max(getnumber(k,l,r)+1,tmp);
}
} //计算n中数字k-1的个数
int countk(int k,int n)
{
int s=0;
while(n)
{
if(n%k==(k-1))++s;
n/=k;
}
return s;
}
海康威视公司福利 1137人发布