Indeed Tokyo 笔试题一道

Indeed的笔试一次一共4道,鄙人第一次做,前三题1hr就搞定了,唯独最后一题百思不得其解,后来看了大神的思路后幡然醒悟,确实脑子没转过来啊!

题目大致如下:

输入字符串 str=a[0] a[1] ... a[N] ,其中0<N<=10^5。字符串的每一位是0-9或?,需要用0-9填充各个问号的值,使得整个字符串成为一个数(允许前导0),并且满足任意连续10位上的字符(或理解成数字) a[i] a[i+1] ... a[i+9] 不重复,输出解的个数。

例如,输入”04??2?7″,输出应当为120.

 

最简单的思路当然是回溯,回溯用递归的话容易爆栈,可以自己定义栈结构。但实现完了我发现效率太低了。这种解法的时间复杂度是O(N!).

网上给了一个十分简单的思路:只计算str前10个字符有多少可能性

这样做可行否?不妨试试看。

假设已经知道了前10个字符a[0]…a[9]能得到解的数目(定作M),那么根据规则,在a[10]的时候要考虑a[1]…a[9]的情况,对于每一种a[1]到a[9]的情况而言,由于已经决定了9个数字了,那么第10个数字显然已经确定了。从这我们可以知道,解的个数肯定是不大于M的,因为假设a[10]不是个”?”并且a[10]又不等于缺的那个数字的话,那这个case是要被毙掉的。然后以此类推,检测a[11], a[12], .. a[N]. 按照这种算法,整个问题的时间复杂度是O(10! * N)=O(N).

==更新==

还有一个更高效的解法,主要思路是利用后面“循环数”得到的确定信息来填充前面的?,然后直接计算组合数即可。具体可以看http://gaomf.cn/2016/10/26/String_Fill/

========

伪代码如下:

换个说法就是,后面的数字肯定是前面10个数字的循环,因为新加的a[i]肯定是得顶替上a[i-10]的位置的。

 

2 thoughts on “Indeed Tokyo 笔试题一道

发表评论

电子邮件地址不会被公开。 必填项已用*标注