首页 > 代码库 > 新浪笔试题之删除文本中词频最小的所有字符串
新浪笔试题之删除文本中词频最小的所有字符串
时间:2014.06.04
地点:基地二楼
--------------------------------------------------------------------------------
一、题目
题目大概是这样纸的,一个文本文件,里面有好多字符串,要求删除在整个文本中出现频率最少的字符串,如果这个最小值对应的字符串有很多,则都删除,结果是输出一个文本,保留下来的字符串用 ‘\t‘ 符号分割。
--------------------------------------------------------------------------------
二、思路
借助字典树先对文本词汇进行统计,并获得最小的出现频率,然后再对文本中每个字符串在文本中进行搜索,得到它出现的频率,如果不等于最小值,那么输出至输出文件,如果是则跳过。
--------------------------------------------------------------------------------
三、代码实现如下
#include<iostream> #include<fstream> #include<string> #include<cctype> using namespace std; class Node { static const size_t kMax = 26; static const char kBase = 'a'; public: Node() { m_num = 0; for (size_t i = 0; i<kMax; ++i) m_next[i] = nullptr; } size_t get_word_num() const { return m_num; } Node* get_son(const char ch) { return m_next[ch - kBase]; } const Node* get_son(const char ch) const { return m_next[ch - kBase]; } Node* get_son(size_t index){ return m_next[index]; } const Node* get_son(size_t index) const{ return m_next[index]; } void set_son(Node* node_ptr, char ch){ m_next[ch - kBase] = node_ptr; } void incre_word_num() { ++m_num; } void ClearWord(){ m_num = 0; } private: size_t m_num; Node* m_next[kMax]; static size_t min_num; }; using Trie = Node; Trie* CreateTrie() { Trie* trie_ptr = new Trie(); return trie_ptr; } void Insert(Trie* trie_ptr, char*s) { Node* cursor_node_ptr = trie_ptr; Node* son_node_ptr = nullptr; for (size_t i = 0; i<strlen(s); ++i) { son_node_ptr = cursor_node_ptr->get_son( static_cast<char>(tolower(s[i])) ); if (!son_node_ptr) { son_node_ptr = CreateTrie(); (*cursor_node_ptr).set_son(son_node_ptr, s[i]); } cursor_node_ptr = son_node_ptr; } cursor_node_ptr->incre_word_num(); } void Insert(Trie* trie_ptr, string s) { char* str_ptr = const_cast<char*>(s.c_str()); Insert(trie_ptr, str_ptr); } void DeleteWord(Trie* trie_ptr, char*s) { Node* cursor_node_ptr = trie_ptr; Node* son_node_ptr = nullptr; for (size_t i=0; i<strlen(s); ++i) { son_node_ptr = cursor_node_ptr->get_son(s[i]); if (!son_node_ptr) cursor_node_ptr = son_node_ptr; else return; cursor_node_ptr->ClearWord(); } } size_t Search(Trie* trie_ptr, char*s) { Node* current_node_ptr = trie_ptr; Node* son_node_ptr = nullptr; for (size_t i = 0; i<strlen(s); ++i) { son_node_ptr = (*current_node_ptr).get_son(static_cast<char>(tolower(s[i]))); if (son_node_ptr) current_node_ptr = son_node_ptr; else return false; } return current_node_ptr->get_word_num(); } size_t Search(Trie* trie_ptr, string s) { char* str_ptr = const_cast<char*>(s.c_str()); return Search(trie_ptr, str_ptr); } size_t GetMinCoun(Trie* trie_ptr) { static size_t min_cout = UINT_MAX; Node* cursor_node_ptr = nullptr; size_t word_num = trie_ptr->get_word_num(); if ((word_num != 0) && (word_num < min_cout)) min_cout = word_num; for (size_t i = 0; i < 26; ++i) { cursor_node_ptr = trie_ptr->get_son(i); if (cursor_node_ptr != nullptr) GetMinCoun(cursor_node_ptr); } return min_cout; } int main() { Trie* trie_ptr = CreateTrie(); ifstream in_file("H:\\in.txt"); string word; if (in_file.is_open()) { while (in_file >> word) Insert(trie_ptr, word); } in_file.close(); size_t count = GetMinCoun(trie_ptr); ofstream out_file("H:\\out.txt"); in_file.open("H:\\in.txt"); if (in_file.is_open()&&out_file.is_open()) { while (in_file >> word) { if (Search(trie_ptr, word) != count) out_file << word << '\t'; } } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。