#include "map&set.h"
using namespace std;
void test_set1()
{
set<int> s1;
s1.insert(1);
s1.insert(11);
s1.insert(3);
s1.insert(4);
s1.insert(1);
s1.insert(2);
set<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
vector<int> v = { 3, 2, 1, 1, 6, 8 };
set<int> s2(v.begin(), v.end());
for (auto e : s2)
{
cout << e << " ";
}
cout << endl;
set<int> s3 = { 3, 2, 1, 1, 6, 8 };
s3.erase(3);
for (auto e : s3)
{
cout << e << " ";
}
cout << endl;
auto pos = s3.find(3);
if (pos != s3.end())
{
cout << *pos << endl;
s3.erase(pos);
}
else
{
cout << "找不到" << endl;
}
}
void test_set2()
{
set<int> myset;
// 10 20 30 40 50 60 70 80 90
for (size_t i = 1; i < 10; i++)
{
myset.insert(i * 10);
}
for (auto e : myset)
{
cout << e << " ";
}
cout << endl;
auto itlow = myset.lower_bound(30);
auto itup = myset.upper_bound(60);
// 10, 20, 70, 80, 90
myset.erase(itlow, itup);
for (auto e : myset)
{
cout << e << " ";
}
cout << endl;
}
void test_set3()
{
multiset<int> s1;
s1.insert(1);
s1.insert(11);
s1.insert(3);
s1.insert(4);
s1.insert(1);
s1.insert(2);
s1.insert(2);
s1.insert(1);
s1.insert(2);
s1.insert(1);
multiset<int>::iterator it = s1.begin();
while (it != s1.end())
{
cout << *it << " ";
++it;
}
cout << endl;
auto pos = s1.find(2);
while (pos != s1.end())
{
cout << *pos << " ";
++pos;
}
cout << endl;
}
void test_map1()
{
//对于 map 这个类，其类模板参数有两个，分别对应 key 和 value 的类型
// map 中insert() 方法的形参是一个 pair类型的参数
// pair这个类型的类模板参数也有两个，
// pair 这个类中有两个成员变量，分别为 first 和 second
// 对应 key 和value
map<string, string> dict;
// 以下是给insert 传入参数的四种方式
//
// 方式一：直接创建一个pair 类型的对象
pair<string, string> kv1("sort", "排序");
dict.insert(kv1);
// 方式二：类比方式一，但是不创建具体对象，创建一个匿名对象
dict.insert(pair<string, string>("left", "左边"));
// 方式三：使用make_pair 这个函数，返回一个 pair 类型的对象，make_pair的实现如下：
// template <class T1, class T2>
// pair <T1, T2> make_pair (T1 x, T2 y)
// {
// return ( pair<T1, T2> (x, y) );
// }
dict.insert(make_pair("right", "右边"));
// 方式四
// 注意：
// 下面实际上叫做使用了pair 这个类中的 多参数构造函数的特性，可以使用数组进行传参
// 发生了隐式类型转换，将 { "right", "右边" }这个数组的类型转换成 pair 类型的参数
dict.insert({ "right", "右边" });
//map<string, string>::iterator it = dict.begin();
auto it = dict.begin();
while (it != dict.end())
{
//对下面这几句话的解释
// 1. 不能使用cout << *it << endl; 来打印 map 中的键值对，
// 这是因为对 it 进行解引用，得到的是一个 pair 类型的变量
// 2. 可以对迭代器解引用后 得到 pair 类型的变量，
// 然后再对 类使用 . 操作符访问其内部的成员变量
// 3. 如果对map中 map<K, V>::iterator 这个迭代器类型调用 operator->() 这个运算符重载
// 将得到一个 pair* 类型的结构体指针变量，
// 然后再对这个结构体指针变量使用 -> 操作符访问 其内部的成员变量
// 4. 3.中访问变量可以写成it.operator->()->first这一段代码
// 如果按照常规的运算符重载的使用方式应该简化成it.->->first
// 然而，编译器可以将这段代码进行简化，直接使用it->first即可访问
// 5. 普通迭代器iterator的第一个成员变量是被const 进行修饰的，也就是key值不能修改
// 但是第二个成员变量，也就是value 可以修改
// const_iterator 的两个成员变量都不能修改
cout << (*it).first << ":" << (*it).second << endl;
cout << it.operator->()->first << ":" << it.operator->()->second << endl;
//cout << it.->->first << ":" << it.->->second << endl;
cout << it->first << ":" << it->second << endl;
it->second += 'x';
cout << it->first << ":" << it->second << endl;
++it;
}
cout << endl;
// 只有使用 对象 = {};的形式，如下所示，
// 才属于map的构造函数中 利用 initializer_list 的情况
//map<string, string> dict2 = { {"string", "字符串"}, {"erase", "删除"}, {"insert", "插入"} };
for (auto& kv : dict)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
void test_map2()
{
string strs[] = { "苹果", "西瓜", "苹果", "樱桃", "西瓜", "樱桃", "苹果", "桃子", "苹果" };
// 统计水果出现的次数
map<string, int> countMap;
for (auto& str : strs)
{
//map 对象在调用 [] 这个运算符重载的时候V& operator[] (const key_type& k);
// 这个运算符重载的功能是：
// case1. 如果 str 不在countMap中，
// 将会在这个 countMap中插入一个键值为str的对象σ
// σ的类型是 pair，σ的第一个成员是 str，σ的第二个成员是一个类型为 V的 匿名对象
// 此时返回 该匿名对象的值
// case2. 如果 str 在countMap中，
// 此时将直接返回 在countMap中 key值 为 str 的 那个结点对应的 value 的值
// 注意！！！！！！！！！！！！！！！！！
// 由于所有类型(包括内置类型)都有匿名对象，且内置类型的匿名对象的取值为0,0.0,'0'
countMap[str]++;
//auto it = countMap.find(str);
//if (it == countMap.end())
//{
// 对于map 中 insert方法，
// 如果key 存在，则插入失败，返回一个pair
// 这个 对象的第一个成员是key 所在结点的迭代器，第二个成员是false
// 如果key 不存在，则插入成功，返回一个pair
// 这个 对象的第一个成员是 指向新插入的 key 所在结点的迭代器，第二个成员是true
// countMap.insert({ str, 1 });
//}
//else
//{
// it->second++;
//}
}
countMap["桃子"];
for (auto& kv : countMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
//map<int, string> sortMap;
multimap<int, string> sortMap;
for (auto& kv : countMap)
{
// case1: 如果sortMap是map<int, string>类型的变量，那么
// case1.1 sortMap[kv.second] = kv.first;
// 会让value值相同的两个结点中前一个节点被覆盖
// case1.2 sortMap.insert({ kv.second, kv.first });
// 会让value值相同的两个结点中后一个节点被覆盖
// case2: 如果sortMap是multimap<int, string>类型的变量，那么
// 只能使用sortMap.insert({ kv.second, kv.first });创建 sortMap 的结点
// 因为multimap没有对 [] 进行运算符重载，这是因为一个 key值可能 对应多个value
//sortMap[kv.second] = kv.first;
sortMap.insert({ kv.second, kv.first });
}
cout << endl;
for (auto& kv : sortMap)
{
cout << kv.first << ":" << kv.second << endl;
}
cout << endl;
}
//V& operator[](const K& key)
//{
// 对于下面的代码中调用了insert方法需要注意的是：
// 1. 对于case2，也就是this 指针指向的map对象中，已经存在一个 key值的结点
// 此时insert方法 并不会把匿名对象插入
// 2. insert方法返回的 是一个 pair类型的对象α
// 不管是 case1，还是case2，α的第一成员都是指向
// map 中那个关键字为key 的结点的迭代器
// pair<iterator, bool> ret = insert(make_pair(key, V()));
// iterator it = ret.first;
// return it->second;
//}
void test_map3()
{
map<string, string> dict;
dict.insert({ "string", "字符串" });
//map对象利用 [] 这个运算符重载可以实现：
// 1. 插入，第一次创建一个 含有 key 值的结点，并且其对应的value是 匿名对象
// 操作：dict[全新的key值];
// 2. 修改，对已有key值的结点的value值进行修改
// 操作：dict[已有的key值] = 新的value值
// 2.1 插入加修改：dict[全新的key值] = 新的value值;
// 3. 查找：找到 已有key值的节点 对应的value
//dict["string"];不会将 dict 中关键字是"string"的那个结点的 value 的值更改为匿名对象
dict["string"];
//dict["string"] = "字符";会将 dict 中关键字是"string"的那个结点的 value 的值更改为"字符"
dict["string"] = "字符";
//dict["erase"];会先插入一个关键字是"erase"的新结点
// 再将这个新结点的 value 的值更改为匿名对象
dict["erase"];
//dict["erase"] = "删除";会将 dict 中关键字是"erase"的那个结点的 value 的值更改为"删除"
dict["erase"] = "删除";
string str;
cin >> str;
//set 和 map中都有 count 方法，可以找到对象中一个关键字key 对应了几个结点
if (dict.count(str))
{
cout << "这个关键字在字典中" << endl;
}
else
{
cout << "这个关键字不在字典中" << endl;
}
}
//例题1：随机链表的复制
//给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，
//该指针可以指向链表中的任何节点或空节点。
//构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，
//其中每个新节点的值都设为其对应的原节点的值。
//新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，
//并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
//例如，如果原链表中有 X 和 Y 两个节点，其中 X.random-- > Y 。
//那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-- > y 。
//返回复制链表的头节点。
//用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。
//每个节点用一个[val, random_index] 表示：
//val：一个表示 Node.val 的整数。
//random_index：随机指针指向的节点索引(范围从 0 到 n - 1)如果不指向任何节点，则为 null 。
//你的代码 只 接受原链表的头节点 head 作为传入参数。
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
class Solution {
public:
Node* copyRandomList(Node* head) {
map<Node*, Node*> nodeMap;
Node* copyhead = nullptr, * copytail = nullptr;
Node* cur = head;
//先用一个while循环将建立一个 nodeMap对象
// 这个对象中的每一个元素都使用原链表中的节点的地址作为key
// 并且每个key对应的value同样是 Node*类型的地址，
// 每个地址都存着和 对应位置的key 中相同val的值
while (cur)
{
if (copytail == nullptr)
{
copyhead = copytail = new Node(cur->val);
}
else
{
copytail->next = new Node(cur->val);
copytail = copytail->next;
}
nodeMap[cur] = copytail;
cur = cur->next;
}
cur = head;
Node* copy = copyhead;
//再利用一个while循环进行深拷贝，
// 通过nodeMap[cur->random]找到原链表对应的random 结点集合
// 通过copy->random = nodeMap[cur->random];
// 一个个把这些random结点与 拷贝链表的random域 进行连接
while (cur)
{
if (cur->random == nullptr)
{
copy->random = nullptr;
}
else
{
copy->random = nodeMap[cur->random];
}
cur = cur->next;
copy = copy->next;
}
return copyhead;
}
};
//例题2：前K个高频单词
//给定一个单词列表 words 和一个整数 k ，返回前 k 个出现次数最多的单词。
//返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
//示例 1：输入 : words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
//输出 : ["i", "love"]
//解析 : "i" 和 "love" 为出现次数最多的两个单词，均为2次。
//注意，按字母顺序 "i" 在 "love" 之前。
class Solution {
public:
vector<string> topKFrequent(vector<string>& words, int k) {
}
};
//二叉搜索树
int main()
{
//test_map1();
test_map2();
//test_map3();
return 0;
}
![[方法] Unity 实现仿《原神》第三人称跟随相机 v1.0](https://img-blog.csdnimg.cn/direct/30728630f95d436babe5bf4d116a8f4b.png)
