本期，我将给大家带来的两道题目的讲解。主要涉及的就是哈希相关的知识点。接下来，我们一起去看看！！！
1、前k个高频单词
题目如下：
🔥 解题思路：
方法一：
首先，我先给出大概的思路。其实本题两步就可以实现：
- 第一步：使用哈希表，统计相同字符串出现的次数
- 第二步：在哈希表中，排序选出前K大的单词即可
具体思路：
- 首先我们可以利用哈希表来记录每一个单词出现的次数；
- 紧接着将哈希表中所有单词进行排序，排序时，如果两个字符串出现频率相同，那么我们让两字符串中在字典中顺序较小的排在前面，否则我们让出现频率较高的排在前面；
- 最后我们只需要保留序列中的前 k 个字符串即可。
代码如下：
class Solution { public: static bool cmp(const pair<string,int> &p1,const pair<string,int> &p2){ if(p1.second > p2.second) { return true; } if(p1.second == p2.second) { return p1.first<p2.first; } else return false; } vector<string> topKFrequent(vector<string>& words, int k) { unordered_map<string, int> num; vector<string>tmp; //首先统计单词出现的次数 for (auto& e : words) { ++num[e]; } vector<pair<string,int>> arry; for(pair<string,int> p1 : num) { arry.push_back(p1); } //进行排序操作 sort(arry.begin(),arry.end(),cmp); //对已经排好序的数组，直接输出对应的前k个即可 for(int i=0;i<k;++i) { tmp.push_back(arry[i].first); } return tmp; } };
方法二：
为了解决在给定单词列表中查找前 K 个常用单词的问题：
- 可以使用哈希映射来计算每个单词的频率；
- 然后使用优先级队列来跟踪前 K 个常用单词。
具体思路：
- 首先我们可以创建一个小根优先队列（顾名思义，就是优先队列顶端元素是最小元素的优先队列）;
- 紧接着我们可以将每一个字符串插入到优先队列中，如果优先队列的大小超过了 k，那么我们就将优先队列顶端元素弹出即可；
- 这样最终优先队列中剩下的 k 个元素就是前 k 个出现次数最多的单词。
代码如下：
class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { //计算每个单词的频率 unordered_map<string, int> num; for (auto& e : words) { num[e]++; } //使用优先级队列跟踪前 K 个常用单词 auto cmp=[](const pair<string,int> &p1,const pair<string,int> &p2){ return p1.second == p2.second ? p1.first < p2.first : p1.second > p2.second; }; priority_queue<pair<string, int>, vector<pair<string, int>>, decltype(cmp)> pq(cmp); for (auto& it : num) { pq.emplace(it); if (pq.size() > k) { pq.pop(); } } vector<string> result(k); for (int i = k - 1; i >= 0; i--) { result[i] = pq.top().first; pq.pop(); } return result; } };
方法三：
具体思路：
- 首先还是统计每种单词出现的次数；
- 紧接着再按照字符出现次数进行降序排列；
- 最后由于Map的排序是稳定的"排序算法"，所以排序后如果不同的单词有相同出现频率，会自动按字典顺序排列。
代码如下：
class Solution { public: vector<string> topKFrequent(vector<string>& words, int k) { map<string, int> num; for(auto e : words) num[e]++; multimap<int, string, greater<int>> arry; for(auto e : num) { arry.insert(make_pair(e.second, e.first)); } vector<string> res; auto it = arry.begin(); for(int i = 0; i < k; i++) { res.push_back(it->second); it++; } return res; } };
2、单词识别
题目如下：
具体思路：
- 其实本题很简单，就是利用map统计单词出现的次数并输出即可。
代码如下：
#include <iostream> #include <map> #include <string> using namespace std; int main() { string str; string tmp; map<string, int> res; while (getline(cin, str)) { for (int i = 0; i < str.size(); i++) { if (str[i] == ' ' || str[i] == ',' || str[i] == '.') { if (tmp != "") res[tmp]++; tmp = ""; } else { tmp += tolower(str[i]); } } auto it = res.begin(); while(it != res.end()) { cout<<it->first<<":"<<it->second<<endl; it++; } } return 0; } // 64 位输出请用 printf("%lld")
以上便是两道题的全部讲解。希望对大家有所帮助！！！
