给定一个string数组article及其大小n及一个待统计单词word,请返回该单词在数组中出现的频数。文章的词数在1000以内。
struct Node{ char data; int cnt; int ch[2],next;// 0 left child, 1 right child Node(){} Node(char c):data(c){cnt=ch[0]=ch[1]=next=0;} }; struct Trie{ Node* node; int nodecount; Trie(){ node=new Node[500005]; node[0]=Node('n'); nodecount=1; } ~Trie(){ delete [] node; } int appendnode(char x){ node[nodecount]=Node(x); return nodecount++; } void append(int id,const char* str){ while(*str){ if(*str==node[id].data){ if(!str[1])node[id].cnt++; if(!node[id].next&&str[1]){ node[id].next=appendnode(str[1]); } id=node[id].next; str++; }else{ int cid=*str<node[id].data?0:1;//0 left child, 1 right child if(!node[id].ch[cid]){ node[id].ch[cid]=appendnode(str[0]); } id=node[id].ch[cid]; } } } int find(int id,const char *str){ while(*str){ if(*str==node[id].data){ if(!str[1])return id; if(!node[id].next){ return -1; } id=node[id].next; str++; }else{ int cid=*str<node[id].data?0:1;//0 left child, 1 right child if(!node[id].ch[cid]){ return -1; } id=node[id].ch[cid]; } } return -1; } }; class Frequency { public: int getFrequency(vector<string> article, int n, string word) { Trie trie; for(int i=0;i<n;i++){ trie.append(0,article[i].c_str()); } int id=trie.find(0,word.c_str()); return trie.node[id].cnt; } };
C++ 一句话:
return count(article.begin(), article.end(), word);
//看了一遍,有位大神使用trie树实现的,但是是用c++,我就给一个java实现的吧,思路就是那位c++大神的 import java.util.*; class TrieNode { private TrieNode[] children; public boolean isWord; public int cnt; public TrieNode() { children = new TrieNode[26]; isWord = false; cnt = 0; } public void insert(String word, int index) { if (index == word.length()) { isWord = true; ++cnt; return; } int c = word.charAt(index) - 'a'; if (children[c] == null) { children[c] = new TrieNode(); } children[c].insert(word, index + 1); } public TrieNode search(String word, int index) { if (index == word.length()) { return this; } int c = word.charAt(index) - 'a'; if (children[c] == null) { return null; } return children[c].search(word, index + 1); } } public class Frequency { public int getFrequency(String[] article, int n, String word) { // write code here TrieNode root = new TrieNode(); for (String str : article) { root.insert(str, 0); } if (word == null || word.length() == 0) { return 0; } TrieNode ans = root.search(word, 0); if (ans != null && ans.isWord == true) { return ans.cnt; } return 0; } }
/** *看到你们写得好复杂,可能是算法工程师该有的品质和本能,c语言和c++学得并不算好, *所以比较中情java,闲话少说,我来分享一下我自己的算法,我是每一次都拿那个word去 *和那篇文章的每一个字符串比,如果相等的话,就count+1,判断结束,返回count **/public class Frequency {
import java.util.*; /* 思路:感觉有好多种方法做这道题目,我就选择其中最传统的把,就是顺序遍历过去 */ public class Frequency { public int getFrequency(String[] article, int n, String word) { int count=0; for(int i=0;i<n;i++){ if(article[i].equals(word)) count++; } return count; } } 运行时间:82ms 占用内存:10368k
int getFrequency(vector<string> article, int n, string word) {
/* 思路1:直接遍历 */ /* class Frequency { public: int getFrequency(vector<string> article, int n, string word) { int count = 0; for(int i=0;i<n;i++){ if(article[i]==word){ count++; } } return count; } }; */ /* 思路2:使用哈希表 */ class Frequency { public: int getFrequency(vector<string> article, int n, string word) { unordered_map<string,int> map; for(int i=0;i<n;i++){ map[article[i]]++; } return map[word]; } };
class Frequency { public: int getFrequency(vector<string> article, int n, string word) { // write code here map<string,int> mm; for(int i=0;i<article.size();++i){ auto iter=mm.find(article[i]); if(iter!=mm.end()){ iter->second++; }else{ mm.insert(pair<string, int>(article[i],1)); } } auto iter=mm.find(word); if(iter!=mm.end()){ return iter->second; }else{ return 0; } } };
class TrieNode(object): def __init__(self,value=None,count=0,parent = None): self.value = value self.count = count self.parent = parent self.children = {} class Trie(object): def __init__(self): self.root = TrieNode() def insert(self,sequence): cur_node = self.root for item in sequence: if item not in cur_node.children: child = TrieNode(value=item,count=0,parent=cur_node) cur_node.children[item] = child cur_node = child else: cur_node = cur_node.children[item] #cur_node.count+=1 cur_node.count+=1 def search(self,sequence): cur_node = self.root mark = True for item in sequence: if item not in cur_node.children: mark = False break else: cur_node = cur_node.children[item] if mark==0: return 0 else: return cur_node.count class Frequency: def getFrequency(self, article, n, word): trie = Trie() for i in range(n): trie.insert(article[i]) return trie.search(word)