迅雷校园招聘面试题·····

lyreopera

感觉有点像算法导论里面动态规划中一个碱基配对的问题

zhaohongjian000

可以在O(m+n)内解决。

设要搜索的字符串常为n，为可能的字符建立一个hash表，保证在O(1)时间内可以确定字符是否被映射，然后遍历目标字符串，时间复杂度为O(m+n)。

youzhizhe

不可能为所有的可能的字符串都建立HASH表吧（有无限个）

youzhizhe

悲剧，没有人有想法了吗？

contiguous

就是给一个很长的字符串str 还有一个字符集比如{a,b,c} 找出str里包含{a,b,c}的最短子串。要求O(n)?
比如，字符集是a,b,c，字符串是abdcaabcx，则最短子串为abc


用两个变量 front rear 指向一个的子串区间的头和尾
用一个int cnt[255]={0}记录当前这个子串里 字符集a,b,c 各自的个数，一个变量sum记录字符集里有多少个了
rear 一直加，更新cnt[]和sum的值，直到 sum等于字符集个数
然后front++,直到cnt[]里某个字符个数为0，这样就找到一个符合条件的字串了

继续前面的操作，就可以找到最短的了

从csdn上看到的，呵呵

linux_arm

可以设计一个矩阵来解决此问题

DNFCF

无聊就试着写了一个。。。。不知道效率怎么样。。。。




因为是虚拟机里写的。。。又不会共享文件。。就截图了。。。