360笔试第二题，高效解法

笔试里那个题从下界到上界遍历就可以过吗。。时间这么宽松吗

过不了

我的思路是用贪心，进制转换后得到两个字符串s1,s2，用一个ans字符串记录答案。 显然s2>s1，然后找出第一个s1[i]!=s2[i]的位置（在此之前的所有s1[i]==s2[i]都直接加到ans的末尾）。如果是最后一位就不变，否则让s1[i]=s2[i]，然后后面的所有位数全部变成k-1.这种情况得到的数字最后再和上界比较一下k-1的个数，数字大的就是答案。还有楼主你的解法没有输出答案要求的最小的符合要求的数，而且你给的样例，最小的符合要求的数是99而不是199，不过你的思路应该有可取性,可以避免我这种贪心一堆边界判断的情况。

超时

之前题目记错了。下面更正一下 解题思路：对于上面的例子，可以这样来划分区间 各个子区间除了各位其他各位数字相同，所以含“9”最多的且在相同数目中最小的一定在下面这些数字中 29,39,49，……，259,260 那么最终的结果一定在下面两者中取：2~25中“9”的个数最多且最小的那个数乘以10加上9、267. 选取的标准是那个数中9最多。 如果右边界恰好是259的话，就直接是：2~25中“9”的个数最多且最小的那个数乘以10加上9 这便形成了简单的递归思路。为了简单起见我对原来的代码做了小幅的修改，代码很丑不要见怪。 代码如下： int getnumber(int k,int l,int r){     //cout<<l<<" "<<r<<endl;     if(r<k-1)return l;//直接返回最小的l     l=l/k;     if(r%k==k-1)     {         r=r/k;         return getnumber(k,l,r)*k+(k-1);     }     else //if(r%k!=k-1)     {         r=r/k-1;         int a=r*k,b=getnumber(k,l,r)*k+k-1; //在其他参数传递的方式下countk(k,b)不用再计算一遍         return countk(k,a)>countk(k,b)?a:b;//在相等的情况下应选择b，因为b更小     } }