企业官网建设流程全解析

网站推广主要方法,安徽省建设厅网站个人怎么注册,定制东西的app,阜城网站建设价格前言 STL容器是存储与管理同类型元素的类模板#xff0c;其大致可以分为三类#xff1a; 1.顺序容器#xff1a;按照线性顺序#xff0c;连续存储数据#xff0c;以vector,deque,list为代表 2.关联容器#xff1a;基于红黑树实现#xff0c;按照关键字有序访问#…前言STL容器是存储与管理同类型元素的类模板其大致可以分为三类1.顺序容器按照线性顺序连续存储数据以vector,deque,list为代表2.关联容器基于红黑树实现按照关键字有序访问以set,map为代表3.无序关联容器基于哈希表实现高效无序访问以unordered_set/unordered_map为代表本文介绍的无序容器统一指无序关联容器。无序容器的优势与其他容器相比无序容器舍弃了顺序容器的连续存储也舍弃了关联容器的有序性但换来了几乎是全容器最快的速度。哈希表原理在无序容器内部分为两步存储一步是根据哈希函数结果直接定位的桶另一步是桶内部的链表/树这一部分通常元素极少。最核心的就是哈希表通过哈希函数将我们输入的key转换为哈希值根据该结果映射到桶数组的特定下标在桶内遍历访问我们要找到的元素。与其他容器的对比1. 序列容器vector/deque/list结构连续内存或链表查找方式线性扫描或二分需先排序代价必须逐个比较元素直到找到目标2. 有序关联容器set/map结构红黑树平衡二叉搜索树查找方式从根节点向下比较每次排除一半代价需要 log2​n 次比较且每次比较可能涉及指针跳转3. 无序关联容器unordered_set/map结构哈希表桶 链表查找方式计算哈希值 → 直接定位到桶bucket在桶内少量元素中查找代价哈希计算 O(1) 桶内查找通常 1-2 次比较直观一点画个表格看看时间复杂度的比较无序容器的优势一目了然^^操作vectorset/map(红黑树unordered_set/map查找O(n)O(logn)平均O(1)插入中间O(n)尾部O(1)O(logn)平均O(1)删除O(n)O(logn)平均O(1)判存在O(nOlogn)平均O(1)平均O(1)的复杂度一定是其他容器望尘莫及的存在。当数据量达到 1e5 时O(n) 需要遍历比较 1e5 次O(logn) 需要比较 17 次而 O(1) 只需要1 次哈希计算就能精准定位到桶。实战对比话不多说上代码。1.高频查重//给定数组回答 10 万次询问x 是否在数组中 #define size 100000 vectorintqueries(size);//十万次查询 // 方法 Avector vectorint arr(size) for (int q : queries) { if (find(arr.begin(), arr.end(), q) ! arr.end()) ; // O(n) 每次总复杂度 O(n*m) 10^10 } // 方法 Bset setint s(arr.begin(), arr.end()); for (int q : queries) { if (s.count(q)) ; // O(log n) 每次总复杂度 O(m*logn) } // 方法 Cunordered_set unordered_setint s(arr.begin(), arr.end()); for (int q : queries) { if (s.count(q)) ; // O(1) 每次总复杂度 O(m) }2.词频统计// vector 排序O(n log n) sort(words.begin(), words.end()); // 再线性扫描统计连续相同元素 // map O(n log n) mapstring, int cnt; for (auto w : words) cnt[w]; // 每次插入/修改都是 O(log n) // unordered_map O(n) unordered_mapstring, int cnt; for (auto w : words) cnt[w]; // 每次 O(1)总线性时间无序容器简介一、unordered_set无序集合无序集合存储不重复的键值内部基于哈希表实现。提供 O(1) 平均时间的插入、删除和查找。凭借着高效的增删改查无序集合非常适合用于维护一个不重复的滑动窗口或者判断存在性这也是它使用频率较高的地方。它不关注“出现次数”只关注“存在性”。特性1.唯一性unordered_setint s;//声明一个存储int类型的无序集合 s.insert(5); s.insert(5); // 第二次插入无效s内部元素仍然只有52.无序性为了追求哈希表的高速内部通过哈希函数决定顺序可认为是完全随机unordered_setint s {3, 1, 4, 1, 5}; for (int x : s) cout x ; //输出顺序任意无法提前判断具体操作1.声明#includeiostream #include unordered_set//无序集合头文件 using namespace std; unordered_setint s; // 存储 int unordered_setstring strSet; // 存储 string2.插入元素//单个插入 int x5; s.insert(x); //返回 pairiterator, bool,可以通过返回值来判断插入是否成功 //通常是有重复元素才返回false // 批量插入 vectorint v {1, 2, 3}; s.insert(v.begin(), v.end()); //判断插入 for(inti:v){ if(!s.insert(i).second){ cout有重复;//如果插入失败返回pairiterator,false可通过点运算符直接访问布尔值 } }3.查询元素unordered_setintseen; //count:集合内有该元素时返回1没有则返回0平均时间复杂度O(1) for(int i:nums){ if(!seen.count(i)){ couti重复了endl; } seen.insert(i); } //find:返回迭代器如果集合内有目标元素返回该元素没有则返回.end() auto itseen.find(x) //可以通过*it来直接修改集合中的目标元素 if(it!seen.end())cout有该元素endl; else cout无该元素endl;4.删除元素s.erase(42); // 按值删除返回删除个数0 或 1 s.erase(it); // 按迭代器删除 s.clear(); // 清空所有元素5.容量s.size(); // 元素个数不重复的数量 s.empty(); // 是否为空 s.reserve(1000); // 预分配桶数量避免 rehash适用场景1.去重利用它唯一性与插入高效的特点在不需要关注顺序的情况下直接利用无序集合复制数组可以达到去重的效果这是理论上极快的去重但如果你关注顺序以方便后续的二分等算法还是sortunique吧。//快速无序去重 vectorint nums {1, 2, 2, 3, 3, 3}; unordered_setint s(nums.begin(), nums.end()); // s 现在包含 {1, 2, 3} vectorint uniqueNums(s.begin(), s.end()); // 转回 vector顺序随机 //有序去重 sort(nums.begin(),nums.end()); auto itunique(nums.begin(),nums.end()); erase(it,nums.end());当然如果不考虑顺序它将是极方便的思路。349.两个数组的交集//给定两个数组 nums1 和 nums2 返回 它们的 交集 。 //输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。 class Solution { public: vectorint intersection(vectorint nums1, vectorint nums2) { unordered_setintst(nums1.begin(),nums1.end());//set内部自动去重 vectorintans; for(const inti:nums2){ if(st.count(i)){//判断st内部有这个元素 st.erase(i);//去除这个元素防止重复。因为set内部每个元素只有一次去除后保证ans内部元素唯一 ans.push_back(i); } } return ans; } };在本题中我们先把nums1复制到st中顺便去重然后利用快速判断存在性的特点不断判断nums2中是否有和st相同的元素即为两个数组的交集。本题中使用无序集合可以让效率提高这是相比其他容器的优势。2.存在性查询以力扣217为例/*题目给你一个整数数组 nums 。 如果任一值在数组中出现 至少两次 返回 true 如果数组中每个元素互不相同返回 false 。*/ class Solution { public: bool containsDuplicate(vectorint nums) { unordered_setintseen; for(int i:nums){ if(seen.count(i)){ return true;//有重复直接返回 } seen.insert(i);//插入元素 } return false; } };3.维护滑动窗口unordered_set中查、增、删的时间复杂度都为O1是非常好用的滑动窗口载体。3.无重复字符的最长字串//给定一个字符串 s 请你找出其中不含有重复字符的 最长 子串 的长度。 class Solution { public: int lengthOfLongestSubstring(string s) { unordered_setcharst; int right0; int left0; int ans0; for(int i0;is.length();i){ while(st.count(s[right])){//如果新进的字符已经出现就收缩左边界直到窗口内部字符无重复 st.erase(s[left]);//清除 left;//收缩 } st.insert(s[i]); right;//right在循环结束后指向窗口右边界下一个因此窗口长度为right-left ansmax(ans,(int)st.size());//st.size()返回unsiged类型显式类型转换一下才可以比较 //st.size()和right-left完全等价都是窗口长度 } return ans; } };相似的题目还有128.最长连续序列但两者也有些许区别。128.最长连续序列class Solution { public: int longestConsecutive(vectorint nums) { unordered_setints(nums.begin(),nums.end());//让无序集合装下nums直接去重且方便后续的count查找 int ans0; for(int i:s){ if(s.count(i-1)){ continue;//如果有数字前继说明此数字一定不是起始点直接下一个 } int endi;//设定序列终点 while(s.count(end1)){//如果终点下一个仍存在就让end1最终end停在最远终点 end; } ansmax(ans,end-i1);//i起点end终点长度为end-i1 } return ans; } };3是滑动窗口的直观体现字符串里每个字符都是连续的“窗口”相对比较直观。我们需要做的是不断判断新元素的重复性以维护不重复窗口从而判断长度。128则是先利用unordered_set的唯一性去重再通过快速查找目标元素锁定起始点和终点从而判断出最长的连续序列可以说是为了unordered_set量身打造的题目。二、unordered_map无序映射无序映射存储键值对const key,value将给出的key通过哈希函数算出哈希值从而对应目标value。它可以提供平均 O(1) 时间的增删查改是竞赛中最常用的字典结构。基于这种特性常常用于字符频次统计索引映射等需要映射关系的场景中。特性1.键值对存储无序映射内部存储的是键值对每个元素都是const key,value#includeunordered_map unordered_mapstring,intmp; mp[TOM]10;//TOM是key映射出10 mp[ccc]55;//ccc是key映射出552.唯一性同一个key只能存储一个valuemp[ccc]555;//会把之前的55覆盖掉3.无序性无序映射和无序集合一样都是无序的很合理吧主要意思就是遍历的时候没有固定顺序。具体操作1.声明#include unordered_map unordered_mapstring, int mp; // 基本类型 unordered_mapint, vectorint graph; // value 是vectorint类型的2.插入元素// 方式 Aoperator[] mp[apple] 5; // 若 apple 不存在会先构造默认值 0再赋值为 5 // 方式 Binsert mp.insert({banana, 3}); // 返回 pairiterator, boolbool 表示是否插入成功3.查询元素int x mp[grape]; //危险方法 若 grape 不存在会自动插入 {grape, 0} //方式 1count只查存在性 if (mp.count(apple)) { // 返回 1存在或 0不存在 cout 存在; } //和unordered_set还是挺像的。 //推荐使用这种方法因为不会添加新的键值对污染数据 //方式 2find返回迭代器推荐 auto it mp.find(apple); if (it ! mp.end()) { cout key: it-first; // 访问 keyconst不可修改 cout value: it-second; // 访问 value it-second 100; // 可以修改 value }值得注意的是1.it返回的是键值对的迭代器所以需要用-first来访问key-second访问value2.对于无序映射而言如果你声明一个先前没有声明的key它会自动帮你补上value04.删除元素mp.erase(apple); // 按 key 删除返回删除个数0 或 1 mp.erase(it); // 按迭代器删除 mp.clear(); // 清空一般建议通过迭代器删除5.遍历方法无序映射的遍历方式很有意思主要有三种酌情自选。//三种遍历方法 //1.迭代器 for(auto itmap.begin();it!map.end();it){ coutit-first:it-secondendl;//迭代器-frist指向key,-second指向value } //2.键值对 for(const autopair:map){//pair本身就是一个键值对通过.访问key/value coutpair.first:pair.secondendl; } //3.结构绑定 for(const auto[key,value]:map){//key.value直接把键值对内部的键和值复制出来了 coutkey:valueendl; }适用场景1.频次统计当需要记住某个元素出现的次数时可以使用mptype,int将元素本身作为key次数作为value。出现一次时直接mp[key]从而统计次数。350.两个数组的交集II//给你两个整数数组 nums1 和 nums2 请你以数组形式返回两数组的交集。 //返回结果中每个元素出现的次数应与元素在两个数组中都出现的次数一致 //如果出现次数不一致则考虑取较小值。可以不考虑输出结果的顺序。 class Solution { public: vectorint intersect(vectorint nums1, vectorint nums2) { unordered_mapint,intmp; vectorintans; for(int i:nums1){ mp[i];//数值-次数一次循环map统计数字的出现次数 } for(int i:nums2){ if(mp[i]0){ mp[i]--;//使用一次就让value-- ans.push_back(i); } } return ans; } };先用map统计nums1中出现的数字及其次数建立映射关系。再遍历一遍nums2有重复就让mp中对应的元素--来保证ans内部pb的次数是最小出现次数。另一题思路类似也是找到出现次数之间的关系。383.赎金信//给你两个字符串ransomNote 和 magazine //判断 ransomNote 能不能由 magazine 里面的字符构成。 //如果可以返回 true 否则返回 false 。 //magazine 中的每个字符只能在 ransomNote 中使用一次。 class Solution { public: bool canConstruct(string ransomNote, string magazine) { unordered_mapchar,intmp; for(int i0;imagazine.length();i){ mp[magazine[i]]; } for(int j0;jransomNote.length();j){ if(mp[ransomNote[j]]0){ mp[ransomNote[j]]--; } else{ return false;//如果不够用即刻处死 } } return true;//bingo^^ } };没啥说的magazine就是字符仓库unordered_map统计仓库里面字符类型和数量最后逐个减少看看是否能够满足消耗需要。2.分类统计有些时候我们可以自己设定一个哈希函数把一类数据哈希成同一个key从而直接统计一类数据的出现次数。49.字母异位词分组//给你一个字符串数组请你将 字母异位词 组合在一起。 //可以按任意顺序返回结果列表。 class Solution { public: vectorvectorstring groupAnagrams(vectorstring strs) { vectorvectorstringans; unordered_mapstring,vectorstringmp;//string映射到vectorstring类型 for( string s:strs){ string s_anss;//先记录原始字符串 sort(s.begin(),s.end());//排序如果排序后相等说明是字母异位词 mp[s].push_back(s_ans);//以排序后的字符串为键记录排序前的字符串 } //在这里我们就用sort把“字母异位词”哈希成同一个key //再将同一个key映射的value储存到vectorstring内部 for(const autopair:mp){ ans.push_back(pair.second); } return ans; } };尾声感谢你看到这里。我为这篇文章构思了很久做了很多准备写到这里我很开心希望你也是^^。