从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(下)

简介: 从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别

从C语言到C++_26(set+map+multiset+multimap)力扣692+349+牛客_单词识别(中):https://developer.aliyun.com/article/1521954

stable_sort解析代码:

幸运的是algorithm里面有一个stable_sort,它是基于归并排序实现的,是稳定的,也就是仿函数里少写了一段:(下面代码stable_sort换成sort就不行)

class Solution {
public:
    struct Great
    {
        bool operator()(const pair<string,int>& kv1,const pair<string,int>& kv2) const
        {
            if(kv1.second > kv2.second) // 次数大的在前面
            {
                return true;
            }
            /*if(kv1.second == kv2.second && kv1.first < kv2.first)
            {
                return true;
            }*/
            return false;
        }
    };
 
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string,int> countMap;
        for(const auto& str : words) // 统计次数
        {
            countMap[str]++;
        }
 
        vector<pair<string,int>> sortV(countMap.begin(),countMap.end());
        stable_sort(sortV.begin(),sortV.end(),Great());
 
        vector<string> v;
        for(int i = 0; i < k; ++i)
        {
            v.push_back(sortV[i].first);
        }
        return v;
    }
};

multimap解析代码:

这里可以用multimap 代替stable_sort 以用来排序,可以直接用库里的仿函数:

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        map<string, int> countMap;
        for(const auto& str : words) // 统计次数
        {
            countMap[str]++;
        }
 
        multimap<int, string, greater<int>> sortMap;
        for(const auto& kv : countMap)
        {
            sortMap.insert(make_pair(kv.second,kv.first));
        }
 
        vector<string> v;
        multimap<int, string, greater<int>>::iterator it = sortMap.begin();
        for(int i = 0; i < k; ++i)
        {
            v.push_back(it->second);
            ++it;
        }
        return v;
    }
};

349. 两个数组的交集 - 力扣(LeetCode)

难度简单

给定两个数组 nums1nums2 ,返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序

示例 1:

输入:nums1 = [1,2,2,1], nums2 = [2,2]

输出:[2]


示例 2:

输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]

输出:[9,4]

解释:[4,9] 也是可通过的


提示:

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
 
    }
};

set解析代码:

如果两个数组是有序的,则可以使用双指针的方法得到两个数组的交集。

这里还需要去重,(库里还有一个去重的函数unique,加上sort也可以解决这题)

unique是不改变size的,所以很麻烦,用set(排序+去重)就是很好的选择:

两个指针分别指向两个数组的头部。每次比较两个指针指向的两个数组中的数字,

如果两个数字不相等,则将指向较小数字的指针右移一位,如果两个数字相等,

输出到vector,然后两个指针右移。当至少有一个指针超出数组范围时,遍历结束。

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());
 
        set<int>::iterator it1 = s1.begin();
        auto it2 = s2.begin();
 
        vector<int> v;
        while(it1 != s1.end() && it2 != s2.end())
        {
            if(*it1 > *it2)
            {
                ++it2;
            }
            else if(*it1 < *it2)
            {
                ++it1;
            }
            else
            {
                v.push_back(*it1); // 相等,进哪个都行
                ++it1;
                ++it2;
            }
        }
        return v;
    }
};

单词识别_牛客题霸_牛客网 (nowcoder.com)

中等  通过率:22.37%  时间限制:1秒  空间限制:32M

知识点 字符串 哈希

描述

输入一个英文句子,把句子中的单词(不区分大小写)按出现次数按从多到少把单词和次数在屏幕上输出来,次数一样的按照单词小写的字典序排序输出,要求能识别英文单词和句号。

输入描述:

输入为一行,由若干个单词和句号组成

输出描述:

输出格式参见样例。

示例1

输入:

A blockhouse is a small castle that has four openings through which to shoot.

输出:

a:2

blockhouse:1

castle:1

four:1

has:1

is:1

openings:1

shoot:1

small:1

that:1

through:1

to:1

which:1

#include <iostream>
using namespace std;
 
int main() {
    int a, b;
    while (cin >> a >> b) { // 注意 while 处理多个 case
        cout << a + b << endl;
    }
}
// 64 位输出请用 printf("%lld")

set解析代码:

1. 遍历语句字符串,从语句字符串中分离出单词

2. 每分离出一个单词,就将该单词插入到map中,map会自动统计该单词出现的次数

3. 将统计到的结果按照要求排序

4. 输出

注意:1. 统计单词时,要将单词的大小写统一,因为题目说不区分大小写,注意循环输入

     2. 利用set将统计的结果按照次数由大到小排序,如果次数一样按照字典序排序

     3. 输出排序之后的结果

#include <iostream>
using namespace std;
#include <map>
#include <set>
 
class Compare
{
public:
    bool operator()(const pair<string,int>& left, const pair<string,int>& right)
    {
        // 次数从大到小排序,如果次数相同,再按照单词字典序排序
        return left.second > right.second || left.first < right.first;
    }
};
 
int main()
{
    string s;
    while(getline(cin, s))
    {
        map<string, int> m;
        string temp;
        
        // 分割单词,采用map统计每个单词出现的次数
        for(size_t i = 0; i < s.size(); ++i)
        {
            if(s[i] == ' ' || s[i] == '.')
            {
                if(temp != "")// 一个单词解析结束
                {
                    m[temp]++;
                }
                temp = "";
            }
            else
            {
                temp += tolower(s[i]); // 题目说不区分大小写
            }
        }
        
        set<pair<string,int>, Compare> s;
        // 将map中的<单词,次数>放到set中,并按照次数升序,次数相同按照字典序规则排序
        for(auto& e : m)
        {
            s.insert(e);
        }
        for(auto& e : s) // 将统计到的结果按照要求输出
        {
            cout<<e.first<<":"<<e.second<<endl;
        }
    }
    return 0;
}

multimap解析代码:

#include <iostream>
#include <string>
#include <map>
#include <functional>
using namespace std;
 
int main() 
{
    string str;
    map<string, int> countMap;
    while(getline(cin,str))
    {
        for(int i=0,j=0;i<str.size();i++)
        {
            if(str[i]==' '||str[i]=='.')
            {
                string t=str.substr(j,i-j);
                if(isupper(t[0]))
                {
                    t[0]=tolower(t[0]);
                }
                j=i+1;
                countMap[t]++;
            }
        }
    }
 
    multimap<int, string, greater<int>> sortMap;
    for(const auto& kv : countMap)
    {
        sortMap.insert(make_pair(kv.second,kv.first));
    }
 
    for(const auto& kv : sortMap)
    {
        cout << kv.second << ":" << kv.first << endl;
    }
 
    return 0;
}

5. 笔试选择题

1. 下列说法正确的是()

A.set中的某个元素值不能被直接修改

B.map和unordered_map都是C++11提供的关联式容器

C.因为map和set的底层数据结构相同,因此在实现时set底层实际存储的是<key, key>的键值对


D.map和multimap中都重载了[]运算符


2.下面关于set的说法正确的是()


A.set中一定不能存储键值对,只能存储key


B.set可以将序列中重复性的元素去除掉


C.set中不能存储对象,因为对象字段较多,没有办法比较


D.set默认是升序,因为其默认是按照大于的方式比较的


3. 下面关于map的说法正确的是()


A.map的查询效率是O(log_2N),因为其底层使用的是二叉搜索树


B.map的key和value的类型可以相同


C.map中的有序只能是升序,不能是降序


D.map中的key可以直接修改


4. 下面关于map和set说法错误的是()


A.map中存储的是键值对,set中只储存了key


B.map和set查询的时间复杂度都是O(log_2N)


C.map和set都重载了[]运算符


D.map和set底层都是使用红黑树实现的

答案:

1. A

A:正确,因为set要保证其有序,因此set中元素不能被直接修改,若要修改可以先删除,在插入


B:错误,map是C++98中已存在的,unordered_map是C++11中才有的


C:错误,map和set底层结构都是红黑树,而其底层红黑树在实现时并没有区分是存k模型还是KV 模型


D:错误,map中key是唯一的,每个key都有与之对应的value,经常需要通过key获取value,因此 map单重载了[ ]运算符, multimap中key是可以重复的,如果重载了[ ]运算符,给定 一个key时,就没有办法返回 value了,因此,multimap中没有重载[ ]运算符


2. B


 A:错误,set中可以存储键值对,实例化set时,将set中元素类型设置为pair即可


 B:正确,因为set中的key是不能重复的


 C:错误,set中任意类型元素都可以存储,存储对象时,需要用户提供比较规则


 D:错误,set默认是升序,正确,但是其内部默认不是按照大于比较,而是按照小于比较


3. B


A:错误,map的查询效率是O(log_2N)是正确的,但map的底层结构不是二叉搜索树,而是红黑树


B:正确,key和value的类型由用户自己设置,可以相同也可以不同,取决于应用场景需要


C:错误,map可以是升序,也可是降序,默认情况下是升序,如果需要降序,需要用户在实例化 map时指定比较规则


D:错误,map中key不能修改,因为如果修改了就不能保证红黑树的特性了,即有序


4. C


 A:正确,map和set的概念


 B:正确,因map和set的底层结构都是红黑树,而红黑树是近似的平衡二叉搜索树,故查询时间 复杂度为O(log_2N)


 C:错误,map中重载了[ ]运算符,因为其需要通过key获取value,set中没有


 D:正确

本篇完。

下一部分:AVL树的介绍和模拟实现,然后是红黑树。再就是set和map的模拟实现。

目录
相关文章
|
5天前
|
C语言 C++
【C++语言】冲突-C语言:命名空间
【C++语言】冲突-C语言:命名空间
|
11天前
|
存储 人工智能 C++
map容器在C++中的具体用法以及相关注意点
map容器在C++中的具体用法以及相关注意点
14 1
|
12天前
|
程序员 C语言 C++
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
11 0
|
20天前
|
安全 Linux 编译器
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(下)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
22 0
|
20天前
|
安全 C语言 C++
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(中)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
22 0
|
20天前
|
Linux 调度 C语言
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(上)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
24 0
|
21天前
|
存储 算法 C语言
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
14 5
|
21天前
|
存储 算法 C语言
从C语言到C++_38(C++的IO流+空间适配器)STL六大组件联系(下)
从C语言到C++_38(C++的IO流+空间适配器)STL六大组件联系
29 5
|
21天前
|
算法 C语言 C++
从C语言到C++_38(C++的IO流+空间适配器)STL六大组件联系(上)
从C语言到C++_38(C++的IO流+空间适配器)STL六大组件联系
23 0
|
21天前
|
安全 程序员 C语言
从C语言到C++_37(特殊类设计和C++类型转换)单例模式(下)
从C语言到C++_37(特殊类设计和C++类型转换)单例模式
23 5