网站 个人 公司 区别是什么,做网站优化竞价区别,wordpress图片外链设置,建设银行网站支付限额怎么办文章目录 序列式容器和关联式容器map和set的介绍set构造和迭代器遍历和insertfinderaseswapclearcountlower_bound和upper_boundmultiset和set的对比 set的二个题目题目解析算法原理代码介绍一个找差集的算法同步算法题目解析算法原理代码 map构造遍历initiaizer_list 序列式容… 文章目录 序列式容器和关联式容器map和set的介绍set构造和迭代器遍历和insertfinderaseswapclearcountlower_bound和upper_boundmultiset和set的对比 set的二个题目题目解析算法原理代码介绍一个找差集的算法同步算法题目解析算法原理代码 map构造遍历initiaizer_list 序列式容器和关联式容器
序列式容器在逻辑上是线性的在物理上不一定连续它们的数据之间没有太大的关联比如交换两个位置的数依旧是序列式容器比如vector,list,deque等关联式容器在逻辑上是非线性的两个位置的关系是紧密相关的比如二叉搜索树随意交换两个位置就破坏了这棵树的结构
map和set的介绍
map和set底层是红黑树红黑树是平衡二叉搜索树平衡二叉搜索树接近完全二叉树的结构但不是完全二叉树查找效率提高了等于logN次set是key的场景map是key/value的场景。
set 支持增删查不支持改修改会改变树的性质 构造和迭代器遍历和insert int main()
{// 降序排序去重 Greater setint, greaterint t;// 升序排序去重 Less // setint t;t.insert(5);t.insert(7);t.insert(2);t.insert(5);// setint::iterator it t.begin();auto it t.begin();while(it ! t.end()){// set不管什么迭代器都不支持修改// 修改会改变其内部结构// 按二叉搜索树的排序,中序升序排序// *it 10;cout *it ;it;}cout endl;// initializer list 相同的值会插入失败t.insert({ 1,2,9,2,7 });for (auto e : t){cout e ;}cout endl;// void insert(initializer_listvalue_type ls);setstring strset { sort,insert,add };// 语法上隐式类型转换生成临时对象临时对象拷贝构造strset// 编译器直接优化为构造// setstring strset({ sort,insert,add });// 语法上构造for (auto e : strset){cout e ;}cout endl;return 0;
}find // 算法库的find O(N)
auto pos find(t.begin(), t.end(), x);
// set的find O(logN)
auto pos t.find(x);erase 删除某个位置的迭代器删除某个值返回成功删除数据的个数删除失败返回0为了兼容multiset(有数据冗余的set),这里面有多个相同的x删除迭代器区间 迭代器失效 1.删除的是根节点或只有一个孩子的节点父亲节点已经链接其他节点了去访问删除的节点是野指针节点已经变了意义变了 2.删除的节点是有两个孩子的节点替代法删除把替代的节点删除原来要删的节点的位置的迭代器失效访问会崩溃节点已经变了意义变了
int main()
{// 1.删除某个位置的迭代器setint t { 1,2,93,403,43 };for (auto e : t){cout e ;}cout endl;// 删除最小值 [first,end),升序排序t.erase(t.begin());for (auto e : t){cout e ;}cout endl;// 2.删除某个值int x;/*cin x;int num t.erase(x);if (num 0){cout num 不存在 endl;}else{cout num 删除成功 endl;}cout endl;for (auto e : t){cout e ;}cout endl;*/// 3.删除一个迭代器区间cin x;auto pos t.find(x);if(pos ! t.end()){// 删除这个节点后,该点迭代器失效t.erase(pos);// 不要访问,vs强制检查会崩溃cout *pos endl;// 访问Node节点}else{cout 不存在 endl;}for (auto e : t){cout e ;}cout endl;return 0;
}swap
交换两个树的根节点
clear
清掉数据不清空间
count
value_type其实是为multiset准备的 功能这个值在的话返回1不在返回0
cin x;
if (t.count(x))
{cout x 在 endl;
}
else
{cout x 不在 endl;
}lower_bound和upper_bound
lower_bound和upper_bound底层是按照二叉搜索树的逻辑进行查找的logN
int main()
{std::setint myset;for (int i 1; i 10; i){myset.insert(i * 10);// 10 20 30 40 50 60 70 80 90}for (auto e : myset){cout e ;}cout endl; 返回 30//auto lowit myset.lower_bound(30); 返回 50//auto upit myset.upper_bound(50); 30 40 50 // 返回 25auto lowit myset.lower_bound(25);// 返回 55auto upit myset.upper_bound(55);// 30 40 50 // 删除这段区间的值, 迭代器区间的都是[)myset.erase(lowit, upit);for (auto e : myset){cout e ;}cout endl;return 0;
}multiset和set的对比
multiset和set都在set头文件下multiset允许键值冗余,insert/find/count/erase都围绕着支持值冗余有所差异
int main()
{// 排序但是不去重multisetint t { 1,2,1,2,342 };auto it t.begin();while (it ! t.end()){cout *it ;it;}cout endl; 有多个x的话,find查找的是中序的第一个int x;cin x;//auto pos t.find(x);//while (pos ! t.end() *pos x)//{// cout *pos ;// pos;//}//cout endl;//auto pos t.find(x);//while (pos ! t.end() *pos x)//{// pos t.erase(pos);// // 删除后返回当前位置的下一个迭代器//}//cout endl;cout t.count(x) endl;t.erase(x);// erase把所有x都删除it t.begin();while (it ! t.end()){cout *it ;it;}cout endl;// 返回x的个数cout t.count(x) endl;return 0;
}set的二个题目
题目链接
题目解析 算法原理 代码
class Solution
{
public:vectorint intersection(vectorint nums1, vectorint nums2) {// 用set进行去重排序setint s1(nums1.begin(),nums1.end());setint s2(nums2.begin(),nums2.end());vectorint ret;auto it1 s1.begin();auto it2 s2.begin();while(it1 ! s1.end() it2 ! s2.end()){if(*it1 *it2){ret.push_back(*it1);it1;it2;}else if(*it1 *it2){it2;}else{it1;}}return ret;}
};介绍一个找差集的算法
差集是一个集合有另一个集合没有的数据去除两个集合共同有的数据
同步算法 题目解析
题目链接
算法原理
让节点一个一个地插入set中如果set中第一次存在一个重复的节点的话返回这个重复的节点就是循环的开始
代码
class Solution
{
public:ListNode *detectCycle(ListNode *head) {setListNode* p;ListNode* cur head;while(cur){if(p.count(cur))return cur;elsep.insert(cur);cur cur-next;}return nullptr;}
};map
map也有map和multimap之分 map支持修改但是修改的是value的值迭代器也支持修改value key-key T-value 在二叉搜索树那里就是把两个参数分开放 在map这里是把两个参数放在一个pair中封装了一层 第一个参数是key第二个参数是value
构造 int main()
{// 1.构造对象pair插入dict(有名对象)mapstring, string dict;pairstring, string kv1(auto, 一);dict.insert(kv1);// 2.匿名对象dict.insert(pairstring, string(string, 二));// 3.make_pair模版dict.insert(make_pair(vector, 三));// 4.C11dict.insert({ map,三 });// 插入时只看key,value不相等时不会更新// key相等时插入失败,map是不允许冗余的dict.insert({ map,三二 });return 0;
}遍历
结构体指针用- 对象用 . map不允许冗余unordered_map允许冗余
mapstring, string::iterator it dict.begin();
while (it ! dict.end())
{// 只支持修改value,不支持修改key// first不支持修改// 底层存的是const first // 这里是const string// it-first x;it-second x;// map不支持*it// cout *it ;// cout (*it).first : (*it).second endl;cout it-first : it-second endl;//cout it.operator-()-first : it.operator-()-second endl;// operator* 返回数据的引用 pair// operator- 返回数据的指针 pair*it;
}
cout endl;initiaizer_list
都用第一种不会用第二种的
// 1
mapstring, string dict { {left, 左边}, {right, 右边}, {insert, 插入},{ string, 字符串 } };
// 2
pairstring, string kv1(string, 一);
mapstring, string dict { kv1, pairstring, string(一, 二) };用最外层括号给给initiaizer_list里面的{}隐式类型转换为pair的两个参数
