【每日刷题】Day127
【每日刷题】Day127
🥕个人主页：开敲🍉
🔥所属专栏：每日刷题🍍
🌼文章目录🌼
1. 349. 两个数组的交集 - 力扣（LeetCode）
2. LCR 022. 环形链表 II - 力扣（LeetCode）
3. 692. 前K个高频单词 - 力扣（LeetCode）
1. 349. 两个数组的交集 - 力扣（LeetCode）
//思路：set 数据结构的使用。
//本道题在之前刷过，不过在学习了 set 后，使用 set 来做这道题简直就是降维打击。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2)
{
vector<int> ans;
set<int> s1,s2;
//将 num1，nums2分别塞入 set 中，set既帮我们完成了排序的工作，也帮我们完成了去重的工作
s1.insert(nums1.begin(),nums1.end());
s2.insert(nums2.begin(),nums2.end());
auto p1 = s1.begin(),p2 = s2.begin();
//后续我们就可以用两个迭代器分别遍历两个 set ，记录相同的值就是交集元素
while(p1!=s1.end()&&p2!=s2.end())
{
if(*p1<*p2) p1++;
else if(*p1>*p2) p2++;
else
{
ans.push_back(*p1);
p1++;
p2++;
}
}
return ans;
}
};
2. LCR 022. 环形链表 II - 力扣（LeetCode）
//思路：set 的使用。
//同样的，本道题在之前刷的时候我们用的方法是快慢指针，这里我们使用set依然是降维打击。
class Solution {
public:
ListNode *detectCycle(ListNode *head)
{
set<ListNode*> s;
while(head)
{
if(s.count(head)) return head;//因为set不能存储重复元素，因此如果遍历到的节点指针已经存储在了 set中，则当前节点就是环的入口
s.insert(head);
head = head->next;
}
return nullptr;
}
};
3. 692. 前K个高频单词 - 力扣（LeetCode）
//思路：set 和 multiset的灵活运用。
//本题 set 和 multiset 来配合使用还是挺绕的，来作图分析
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k)
{
vector<string> ans;
set<int,greater<int>> s;
multiset<string> ms;
for(int i = 0;i<words.size();i++) ms.insert(words[i]);//将所有字符串放入 ms 中
for(auto it:ms) s.insert(ms.count(it));//记录字符串的出现次数，按照降序排序，排除重复的记录
auto its = s.begin();
while(k)
{
auto itms = ms.begin();//遍历 multiset，找当前出现次数最多的字符串
while(k&&itms!=ms.end())
{
if((*its==ms.count(*itms)&&!ans.size())||(*its==ms.count(*itms)&&*itms!=ans.back()))//处理重复的记录情况，如果这一趟就将 k 个出现最多的找完了，则结束
{
ans.push_back(*itms);
k--;
}
itms++;
}
its++;//当前最多的出现次数找完后 its++，去找出现次数第二多的
}
return ans;
}
};