Map容器用map优化程序
目录
基础知识及操作
基础知识
增删改查
map元素的访问
map的遍历
题目练习
1.同构字符串
2.解码字母到整数映射
3.完美K倍子数组-计蒜客
4.和为K的子数组
5.叫号系统-计蒜客
小结
基础知识及操作
今天学习了map的用法，在之前的寒假训练时就接触到过，现在系统的来复习一遍加深记忆。
基础知识
映射：map：
map<string,int> mp; 将string映射到int中 初值为0
对于map来说，一个键只能映射一次，并且具有互异性
map具有中括号运算符可以像数组一样进行运算 如mp[键]
增删改查
查找元素：
if(mp.find(要查找的元素)!=mp.end())如果找到返回此迭代器没有找到就返回尾迭代器，也可以用mp.count(键名)来查找因为map中键具有互异性所以有的话就只会返回1。
删除元素：map.erase(键---类似于数组下标)查大小---清空----判空
mp.size(); map.clear(); mp.empty();
map会自动进行排序（而且是按照键的从小到大进行排序），所以如果对顺序没有要求的话尽量使用unordered_map，因为使用map在每次增加元素或删除元素时都会排序，导致浪费很多时间，用unordered_map可以省去很多时间！
map元素的访问
如果是通过对象本身进行访问的话就需要用到 . 来访问元素。
如果是通过迭代器进行访问的话就需要用到 -> 来访问元素。
map的遍历
如果使用迭代器进行遍历的话，同样有两种方法：
map<int,int> mp;mp[1] = 1;mp[3] = 3;mp[5] = 5;for(auto i = mp.begin();i!=mp.end(); i++){cout<<i->first<<' '<<i->second<<endl;}
这样就需要用 -> 因为当前的i是一个迭代器，通过迭代器访问元素的话就需要用->来访问
而你也可以用快速遍历（对编译器有要求）：
for(auto &随便命名 : 容器名){cout<<命的名<<endl;-----由于映射map输出时有两个所以应该写为cout<<名字.first<<' '<<名字.second<<endl;}
下面就是今天练习的题目了：
题目练习
1.同构字符串
本来这道题就是一个简单的模拟题，但是好久没写代码的我竟然错了好几发找不到正确的思路，还是记下来熟悉一下count的用法吧，当然也可以用find != end() 来代替。
核心代码：
class Solution {
public:bool isIsomorphic(string s, string t) {//由于字符串S和T的长度相同 所以无序再进行判断unordered_map<char,char> mps,mpt;for(int i=0;i<s.length();i++){if(mps.count(s[i]) && mps[s[i]] != t[i]) return false;if(mpt.count(t[i]) && mpt[t[i]] != s[i]) return false;mps[s[i]] = t[i];mpt[t[i]] = s[i];}return true;}
};2.解码字母到整数映射
其实没必要用大量的函数（像一些stoi()，先转成字符串再拼接之类的 有点浪费时间 可以直接通过字符的ASCII码来计算数值）
class Solution {
public:string freqAlphabets(string s) {string ans;for(int i=s.length()-1;i>=0;i--){if(s[i]>='1' && s[i]<='9') ans += 'a'+(s[i]-'0'-1);else if(s[i] == '#'){int num = (s[i-2]-'0');num*=10;num += (s[i-1]-'0');i-=2;ans += 'a'+num-1;}}reverse(ans.begin(),ans.end());return ans;}
};当然也可以正向遍历，用i+2来查询字符 '#' 。
还有就是巩固reverse函数的使用。
string ans;
reverse(ans.begin(),ans.end());
3.完美K倍子数组-计蒜客
当我看到题目中的子数组时，我以为是必须是原数组中连续的一段，我还以为要用滑动窗口作，可是想了半天不知道用滑动窗口怎么实现，跟数值的大小没有关系，好像滑动窗口不能用。
滑动窗口通常适用于连续子数组的和、最值或特定范围问题，但无法直接处理“模运算”条件（即和为K的倍数）
后来看样例发现可以不连续，呢么就可以换一种思路来求解了：
要想数组中的元素两两相加的和都是K的倍数，那么我们可以讨论有几种情况能实现。
在这之前，我们可以讨论有几种情况使得两个数相加等于K，然后再进行取模分析。
不难发现，我们可以通过{k,0}，{k/2,k/2}，{x,k-x}三种情况，推广到取模时：
1-数组中所有元素都是K的倍数，这样不管是哪两个加起来都会是K的倍数，这种情况适用于不管K是奇数还是偶数的所有情况。
2-如果所有元素都对K取模等于K/2，那么 相加起来还是K的倍数（只适用于K为偶数的情况，因为只有K为偶数时，K/2才一样，如果不一样的话，比如K=5，分成2+3，这样就只能是两个元素作为一个数组，因为不管加进来哪个数，都会最多和其中一个数匹配而与另一个数无法匹配，也就是第三种情况）。
3-只有两个数为一组的如{2,3}。
如果子数组可以不连续的话，直接跑一遍统计一下即可，最终结果取得三种情况的最大值。
详解看代码：
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
const int N = 1e5+10;
int a[N];
int n,k;void solve()
{cin>>n>>k;for(int i=1;i<=n;i++){cin>>a[i];}bool ff=0;//作为标记，表示是否能找到最少两个为一组的合法数组作为答案unordered_map<int,bool> mp;int ans1=0,ans2=0;for(int i=1;i<=n;i++){if(a[i] % k == 0)//将所有K的倍数都统计起来{ans1++;}if(k%2==0 && a[i] % k * 2==k)//只有K为偶数时才需要考虑统计{ans2++;}if(!ff)//目前还没有找到两个为一组的合法答案{int t = a[i] % k;//取模便于操作if(mp[k - t]) ff = 1;//如果有需要的另一个数，就找到了mp[t] = 1;//不断统计之前的数}}int res = max(ans1,ans2);//取最大值if(res >= 2) cout<<res<<endl;//有大于两个的最优解，不管是否找到那个“二元组”，已经有了最优解 等于可加可不加 反正答案是2 具体是哪个二元组无需考虑else{if(ff) cout<<2<<endl;else cout<<-1<<endl;}
}signed main()
{IOSint T=1;
// cin>>T;while(T--) solve(); return 0;
}
类似题：
4.和为K的子数组
注意这道题中的子数组是指原数组中连续且非空的一段
而这个虽然连续但是也不用滑动窗口，原因是：
正解：
前缀和 + 哈希表：
不断的更新前缀和，因为要求一段连续的区间和为K，那么就是sum[r] - sum[l-1] = K,也就是sum[r] - K = sum[l-1]，即找有几个sum[l-1]。所以遍历一遍，不断统计前缀和并用map存起来，表示到目前为止有的sum[l-1]的数量即类型信息，如果在遍历过程中出现了有需要的sum[l-1]，那么只需要累加起来即可，有几个sum[l-1]就说明L到R的这段区间内有几个和为K且以R为右端点的新区间，所以要累加。
class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> mp;mp[0] = 1;//初始化！！！为了找到第一个解int count = 0, pre = 0;for (auto& x:nums) {pre += x;if (mp.find(pre - k) != mp.end()) {//看他前面有几个能满足前缀和为pre-k的count += mp[pre - k];}mp[pre]++;//不要忘记也将前缀和累加起来}return count;}
};map的综合应用：
5.叫号系统-计蒜客
这道题有点长，其实也就是一些相关的map的操作，需要注意的坑是要根据实际情况进行删除，不要漏删！
很明显是要用双向的map来存id对urg的映射以及urg对id的映射（由于操作中需要访问最值，所以不用unordered_map，直接用可以自动排序的map方便）。
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define PII pair<int,int>
#define fi first
#define se second
map<int,int> id,urg; //map可以自动排序void solve()
{int n; cin>>n;while(n--){int op;cin>>op;if(op==1){int x,y;cin>>x>>y;id[x] = y;urg[y] = x;}if(op==2){if(urg.empty()) cout<<"error"<<endl;else{cout<<urg.begin()->se<<endl;//通过迭代器访问用箭头id.erase(urg.begin()->se);//从系统中删除这个人的信息就要将两个map中都删除 千万不能忘记urg.erase(urg.begin());}}if(op==3){if(urg.empty()) cout<<"error"<<endl;else{cout<<(--urg.end())->se<<endl;id.erase((--urg.end())->se);urg.erase(--urg.end());}}if(op==4){int x,y;cin>>x>>y;//输入顺序别搞混urg.erase(id[x]);//因为要对id为x的人修改其urg为y，所以要进行3个操作：id[x] = y;//1.将id对应的值改为y 2.在urg中增加对应的urg和id信息urg[y] = x;//3.千万不要忘记把之前的urg删除 防止对后来的信息产生影响即冲突}if(op==5){int x,y;cin>>x>>y;//与操作4一样id.erase(urg[y]);urg[y] = x;id[x] = y;}if(op==6){int x;cin>>x;if(id.find(x) == id.end()) cout<<"error"<<endl;else cout<<id[x]<<endl;}if(op==7){int y;cin>>y;if(urg.find(y) == urg.end()) cout<<"error"<<endl;else cout<<urg[y]<<endl;}}
}signed main()
{IOSint T=1;
// cin>>T;while(T--) solve(); return 0;
}
小结
分清用 -> 还是用 .
map的end()返回的是最后一个元素后面的一个迭代器
所以使用find时，直接mp.find() != mp.end()即可。
访问最后一个元素是要用(--mp.end())->fi/se「迭代器类型用箭头！」
今天是第四天，感觉比前两天轻松了，起码没有学习什么新的东西，趁有时间再去复习复习！