【每日刷题】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;

    }

};