【OJ】前K个高频单词和单词识别和两个数组的交集

个人主页 ： zxctscl
如有转载请先通知

1. 692. 前K个高频单词

1.1 分析

先试用map来统计每个单词出现的次数：

        map<string,int> dict;for(auto& e:words){dict[e]++;}

这时候单词是按照字典序排列的，但是频率是乱的。

可以直接用sort来排一下频率，在取出前k个就行。
但要用pair来排序，pair是支持比较大小的:

这里期望的是用second去比较，而不是用first，这时候，就得用一个仿函数：两个pair比较，按照scond去比较，排的是降序

struct kvCom
{bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2){return kv1.second > kv2.second;}
};

sort是一个函数模板，这里是类模板，传的是仿函数对象： sort(v.begin(),v.end(),kvCom());

排序完了，就得取出前k个的单词放在一个新vector里面：

vector<string> vRet;for(size_t i=0;i<k;++i){vRet.push_back(v[i].first);}return vRet;

此时的代码：

class Solution {
public:
struct kvCom
{bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2){return kv1.second > kv2.second;}
};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> dict;for(auto& e:words){dict[e]++;}vector<pair<string,int>> v(dict.begin(),dict.end());sort(v.begin(),v.end(),kvCom());vector<string> vRet;for(size_t i=0;i<k;++i){vRet.push_back(v[i].first);}return vRet;}
};

但是这里只过了部分的测试用例：

这里有一部分没有按照字典序排，这里是因为sort底层是快排排序不稳定，要修改可以把sort换成稳定的stable_sort: stable_sort(v.begin(),v.end(),kvCom());
这时候就可以了：

还可以修改仿函数：当second相同的时候，按照字典序从小到大排

struct kvCom
{bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2){return kv1.second > kv2.second||(kv1.second==kv2.second && kv1.first < kv2.first);}
};

1.2 代码

用稳定排序：

class Solution {
public:
struct kvCom
{bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2){return kv1.second > kv2.second;}
};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> dict;for(auto& e:words){dict[e]++;}vector<pair<string,int>> v(dict.begin(),dict.end());stable_sort(v.begin(),v.end(),kvCom());vector<string> vRet;for(size_t i=0;i<k;++i){vRet.push_back(v[i].first);}return vRet;}
};

修改仿函数：

class Solution {
public:
struct kvCom
{bool operator()(const pair<string,int>&kv1,const pair<string,int>&kv2){return kv1.second > kv2.second||(kv1.second==kv2.second && kv1.first < kv2.first);}
};vector<string> topKFrequent(vector<string>& words, int k) {map<string,int> dict;for(auto& e:words){dict[e]++;}vector<pair<string,int>> v(dict.begin(),dict.end());sort(v.begin(),v.end(),kvCom());vector<string> vRet;for(size_t i=0;i<k;++i){vRet.push_back(v[i].first);}return vRet;}
};

2. KY264 单词识别

2.1 分析

这道题和上面一样，就是多了单词的处理，把大写转换为小写，再放到map中。还要避免把空格和.给放入，就得在遍历英文句子的时候，遇到空格和符号就往后走。

2.2 代码

#include <algorithm>
#include <iostream>
#include<vector>
#include<string>
#include<map>
using namespace std;struct kvCom{bool operator()(const pair<string,int> kv1,const pair<string,int> kv2){return kv1.second>kv2.second||(kv1.second==kv2.second&&kv1.first<kv2.first);}
};int main() {string words;map<string,int> dict;while(getline(cin,words)){for(int i=0,j=0;i<words.size();i++){if(words[i]==' '||words[i]=='.'){string t=words.substr(j,i-j);if(isupper(t[0]))t[0]=tolower(t[0]);j=i+1;dict[t]++;}}vector<pair<string,int>> k(dict.begin(),dict.end());sort(k.begin(),k.end(),kvCom());for(int i=0;i<k.size();i++)cout<<k[i].first<<":"<<k[i].second<<endl;}  
}
// 64 位输出请用 printf("%lld")

3. 349. 两个数组的交集

3.1 分析

两个数组中都有重复的值，可以先用set去重，排序： set<int> s1(nums1.begin(),nums1.end()); set<int> s2(nums2.begin(),nums2.end());

两个数组都排好序了，比较两个数组，从小到大：

定义两个变量，遍历两个数组，如果两个变量对应值都相同，相同的值就是两个数组的交集，记录下之后，同时都往后走。如果两个值不相同，小的那个值对应的往后走，直到一个数组遍历完。

3.2 代码

class Solution {
public:vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {set<int> s1(nums1.begin(),nums1.end());set<int> s2(nums2.begin(),nums2.end());vector<int> ret;auto it1=s1.begin();auto it2=s2.begin();while (it1 != s1.end() && it2 != s2.end()){if(*it1<*it2){it1++;}else if(*it1>*it2){it2++;}else{ret.push_back(*it1);it1++;it2++;    }     }return ret;}
};