一道腾讯笔试的压轴题解决方案

一道腾讯笔试的压轴题
有一个江洋大盗，他每次写信都是从一张报纸上剪下单词，再把单词贴在信上。假如某张报纸的单词保存在vector<string>paper 中，而信的单词保存在vector<string>letter 中，写一个算法程序判别该报纸可不可以生成该信？

[解决办法]
letter里面的单词不多的话，直接一个个在paper里面找
很多的话先对paper排个序，二分查找吧

找到一个删一个，全能找到就可以生成，否则不行
效率可能不够高
[解决办法]
1、判断pager和letter的个数，若paper的个数少于letter，则返回false；
2、将pager和letter分别按某一规则排序（减少对比的次数）；
3、循环判断letter的内容是否在pager中出现，若出现，将letter中的内容删除，执行查找下一个，如果有一个未找到，则返回false，如都找到，返回true；
4、循环中，当letter中的字符和要找的pager中的字符，要根据排序规则中断查找，换下一个查找。
[解决办法]
哈希会比快排更快点的。
Hash生成两个柱状图。
比较Paper的包含信的就OK了。
[解决办法]
我也觉得用哈希 记录每个单词出现的次数 从letter里拿出一个单词去哈希表里查找 然后-1 如果是负的了 就不成立
[解决办法]
不会用STL的向量容器啊，要是我去面试腾讯的话就杯具了。不过，如果是普通的字符串集合的包含问题，我倒想到了一种很省时的算法，那就是用trie字母树，既节省空间，时间又快。

具体来说就是用对报纸创建一个trie树，然后每输入一个信中的单词就在trie树中查找。比Hash表快、准，不会出现Hash碰撞问题。

关于trie树解决单词重现问题，可以看一下我的这篇博客：
http://blog.csdn.net/qiuzhenguang/archive/2010/03/14/5379310.aspx
[解决办法]
先排序，在二分查找咯
[解决办法]
去问了下高手：先两边hash，hash数组中存该单词出现的次数，然后再比较两个数组相同的下标对象的次数是否是信中的次数小于等于报纸中出现该单词的次数就ok了，时间复杂度是n+m+mm，n是报纸中单词的总个数，m是信中单词的总个数，mm是信中不重复的单词个数，呵呵！
[解决办法]

探讨

letter里面的单词不多的话，直接一个个在paper里面找
很多的话先对paper排个序，二分查找吧

找到一个删一个，全能找到就可以生成，否则不行
效率可能不够高

[解决办法]

探讨

去问了下高手：先两边hash，hash数组中存该单词出现的次数，然后再比较两个数组相同的下标对象的次数是否是信中的次数小于等于报纸中出现该单词的次数就ok了，时间复杂度是n+m+mm，n是报纸中单词的总个数，m是信中单词的总个数，mm是信中不重复的单词个数，呵呵！

[解决办法]
我对比一些方法： 这里假设paper:(m个单词，每个单词平均d个字母),letter:(n个单词，每个单词平均d个字母)。对于中文词语而言，一般

2~4个字左右，对于英文单词，d就要大一点，但基本上也是常数。因此d远远小于m，下面比较的时候就不考虑单词中每个字符间的比较了。


(1) 蛮力匹配：
把n中每个单词与m中的每个单词一一比较。时间复杂度为：O(m*n)。估计谁也不会选这种。

(2) 二分查找：要求，对paper建有序索引。
paper排序的时间复杂度最好为O(m*logm)。
对letter中的所有单词二分查找的时间复杂度为O(n*logm)
总的时间复杂度为O((m+n)*logm). 比蛮力查找效率要好不少。

缺点：如果换了新报纸，所有的单词都必须重新排序，需要O(m*logm)的时间来建立索引。

(3) trie树： 要求，对paper建trie索引树

paper建立trie树的时间复杂度为O(m)。
对letter中所有单词在trie树中查找的时间复杂度为O(n).
总的时间复杂度为O(m+n)。效率绝对要比二分查找好。

优势: 如果换了新报纸，重新建立一颗trie树的时间O(m)也小于二分查找建立有序索引的时间O(m*logm)要小的多。

缺点：建立trie树所需要的空间代价是很大的。如果是中文词语的trie树，那么放进全部加载进内存是很可怕的，需要把trie树用B树的方

法存储在磁盘上。详见：http://hxraid.javaeye.com/blog/618962

(4) Hash表： 要求，对paper建立Hash结构

建立Hash表结构的时间复杂度为O(m)，注意需要计算每个单词的HashCode的时候，很可能要遍历单词中的每个字母。
对letter中所有单词在Hash结构中查找的时间复杂度为O(n)。当然，这是在没有任何散列冲突的理想情况下。选择好HashCode的计算方式和散列表的大小，可以将冲突降到很低。因此我们这里不考虑冲突。
总的时间复杂度为O(m+n)。由此可见，Hash表结构与Trie树的效率都是相当的客观。

缺点：如果换报纸。为了考虑冲突的可能性，Hash结构的大小可能需要重新考虑。这一点很麻烦。当然，存储空间上应该会比Trie要好一些，但实际应用上并不比Trie方便。


(5) 归并查找：要求，对letter和paper都建立有序索引。

对letter和paper排序的时间复杂度分别为O(m*logm)和O(n*logn)
归并查找的时间复杂度为O(m+n)
总的时间复杂度为O(m*logm+n*logn+m+n)

总结：对于这几种方法而言，我更加青睐于trie树。因为我相信报纸中的单词数量基本上是保持稳定的，不可能达到海量级别。Trie树的空间代价其实并不算什么。
[解决办法]
将vector<string>paper，vector<string>letter通通排序（比如从小到大），
循环比较,
i=0; j=0;

while(i<paper.length && i<letter.length)
{
if(paper(i)>letter(j))
{j++;}
if(paper(i)==letter(j))
{i++;j++}
if(paper(i)<letter(j))
{return FAUSE}
}
if(i<letter.length)
{return FAUSE} 

C++不是很懂，但是算法应该就这样了


[解决办法]
我把报纸上的单词按字母剪开后，就成了一堆字母了，要组成什么样的信都可以啊！
把vector<string>paper中的所有字符映射到map<char,int>A
把vector<string>letter中的所有字符映射到map<char,int>B

A,B中也就A-Za-z的字符，伪代码如下:

foreach(char x:A-Za-z) 
{
if(B[x]>A[x])
return false;
}
 retuen true;

我一个个字母的剪，这样思考问题么？
[解决办法]

C/C++ code

#include <iostream>#include <algorithm>#include <vector>#include <string>#include <map>using namespace std ;vector<string> paper ;      //已经初始化好了的 vector<string> letter ;     //同上 map<string,int> result ;int main(){      bool flag = true ;      vector<string>::iterator p = paper.begin() , l = letter.begin() ;    while (p!=paper.end()) ++result[*p++] ;    while (l!=paper.end())    {        if (result[*l++]<1) { flag = false ; break ; } //就是说paper里没有这个词     }    if (flag) cout<<"可以"<<endl ;    else cout<<"不可以"<<endl ;    return 0 ;}
[解决办法]
C/C++ code
 
 #include  <string> 
 #include  <iostream> 
 #include  <vector> 
 #include  <set> 
 using namespace std; 
  
 bool IsLetterInPaper(vector <string> paper,vector <string> letter) 
 { 
 set <string> set_string; 
 for(vector <string>::iterator vc_it = paper.begin();vc_it != paper.end();vc_it ++) 
 { 
 set_string.insert(*vc_it); 
 } 
 for(vector <string>::iterator lt_it = letter.begin();lt_it != letter.end();lt_it ++) 
 { 
 if(set_string.insert(*lt_it).second) 
 return false; 
 } 
 return true; 
 } 
 int main(int argc, char* argv[]) 
 { 
 string p[4] = {"I","love","swimming","hate"}; 
 string l[3] = {"I","love","swimming"}; 
 vector <string> paper(p,p + 4); 
 vector <string> letter(l,l+3); 
 if(IsLetterInPaper(paper,letter)) 
 cout  < < "in paper"; 
 else 
 cout  < <"not in paper"; 
 cout  < <endl; 
 while(1); 
 return 0; 
 } 
 

[解决办法]
我来一个trie树的，其实实现非常简单，这里约定单词都是由26个小写之母构成（其他的自己改）
对于单词来说一般不会很长，所以空间开销可以接受。
下面的代码考虑了单词个数的问题，上代码吧

C/C++ code
#include <iostream>#include <string>#include <vector>using namespace std;struct node {    node *next[26]; //这里假设单词都是26小写字母组成    int cnt;    node () : cnt(0)    {        memset(next,0,sizeof(next));    }};node *root;vector<node*> de;  //记录待delete的指针void insert_str(const char *str){    node *p=root;    int i=0,j;    while (str[i])    {        j=str[i]-'a';        if (p->next[j]==0)        {            p->next[j]=new node;            de.push_back(p->next[j]);        }        p=p->next[j];        i++;    }    p->cnt++; //记录单词出现的次数}int find(const char *str){    node *p=root;    int i=0,j;    while (str[i])    {        j=str[i]-'a';        if (p->next[j]==0)            return 0;        p=p->next[j];        i++;    }    if (p->cnt==0)        return 0;    else        p->cnt--;    return 1;}void release(){    size_t i;    for (i=0;i<de.size();++i)        delete de[i];}int main(){    vector<string> paper(3);    paper[0]="abc";    paper[1]="cde";    paper[2]="def";    vector<string> letter(1);    letter[0]="cde";    size_t i;    //这里可以做一些预处理    //下面针对查找的情况    root=new node;    de.push_back(root);    for (i=0;i<paper.size();++i)        insert_str(paper[i].c_str());    for (i=0;i<letter.size();++i)        if (find(letter[i].c_str())==0)        {            printf("failed!\n");            break;        }    if (i==letter.size())        printf("succeed!\n");} 
  

 

查看更多 下一篇