一.map函数1.map可以提供高效的查找、插入、删除2.基本特性唯一键值每个key只能出现一次自动排序元素总是按key排序高效查找基于key的查找时间复杂度为O(log2n)键不可修改key是const的value可以修改二.相关题目力扣205 1309计蒜客T1271 T3603三.题目分析1力扣205. 同构字符串解题思路先判断两字符串长度长度不一样直接返回false创建两个映射数组维护双向映射 数组a记录 s字符 → t字符 数组b记录 t字符 → s字符依次遍历每一对对应字符 如果两边字符都还没建立映射互相绑定 如果已经存在映射检查是否和当前字符匹配匹配冲突 → 直接返回false。class Solution { public: bool isIsomorphic(string s, string t) { int l1s.size(); int l2t.size(); if(l1!l2)return false;//长度不同必不可能是同构字符串 //a数组映射s字符-t字符 //b数组映射t字符-s字符 char a[150]{0},b[150]{0}; for(int i0;il1;i){ // 当前s[i]、t[i]都还没有建立映射关系 if(a[s[i]]0b[t[i]]0){ a[s[i]]t[i]; b[t[i]]s[i]; } else{ // 已经存在映射校验双向映射是否匹配 if( a[s[i]]!t[i]||b[t[i]]!s[i])return false; } } return true; } };2力扣1309. 解码字母到整数映射解题思路从左向右遍历字符串不使用for自带i手动控制下标移动优先判断当前位置往后第2位有没有 # 有 # 说明是两位数编码读取两位数字转换成字母下标 i 3 没有 # 单个数字编码直接转换下标 i 1 class Solution { public: string freqAlphabets(string s) { string ans; // 从头遍历字符串 for(int i0;is.size();) { // 判断后面第2位存在并且是#代表是两位数编码(10#~26#) if(i2s.size()s[i2]#){ // 算出两位数字数值 int num(s[i]-0)*10s[i1]-0; // 数字转字母 1-a ansanum-1; // 两位数占3个字符 i i1 #直接跳3格 i3; } else{ // 单个数字编码1~9 ansa(s[i]-0)-1; // 只走1位 i; } } return ans; } };3计蒜客T1271分析题目可得能长度≥3的完美子数组只有两类所有元素余数 r 0 - K为偶数所有元素余数 r K/2其余合法组合只能最多两个元素一对 r 和 K-r。解题思路1.求所有数字模K的余数统计每个余数出现次数优先计算可以形成长数组的两种情况余数0、余数K/2(K偶数)如果这两组任意一组元素数量≥2直接输出这个数量最优解若上面两组最多只有1个数说明不可能构造长度≥3的子数组遍历余数查找是否存在一对 (r , K-r) - 存在答案2 - 不存在输出-1#includebits/stdc.h using namespace std; int main(){ int n,k; cinnk; mapint,intcnt; for(int i0;in;i){ long long x; cinx; int rx%k;//计算数字%k的余数 cnt[r]; } int anscnt[0];// 余数0的集合内部任意两数满足条件 // k偶数时余数k/2的集合 if(k%20){ ansmax(ans,cnt[k/2]); } if(ans2){ coutansendl; return 0; } // 走到这里最长集合最多1个元素只能尝试寻找一对(r, k-r)组成长度2 int m0; for(auto p:cnt){ int rp.first; int tk-r; if(rt)continue;//0和k/2已经讨论过跳过 if(cnt.count(t)){ //同时存在r和k-r能凑出一对 m1; break; } } if(m1)cout2endl; else cout-1endl; return 0; }4计蒜客T3603这道题意思比较清楚步骤比较多一步一步跟着题意走即可#includebits/stdc.h using namespace std; mapint ,intidurg; mapint,inturgid; setinturgset; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cinn; while(n--){ int op; cinop; if(op1){ int id,urg; cinidurg; idurg[id]urg; urgid[urg]id; urgset.insert(urg); } else if(op2){ if(urgset.empty()){ couterror\n; continue; } int minurg*urgset.begin(); int pidurgid[minurg]; coutpidendl; urgset.erase(minurg); idurg.erase(pid); urgid.erase(minurg); } else if(op3){ if(urgset.empty()){ couterror\n; continue; } int maxurg*urgset.rbegin(); int pidurgid[maxurg]; coutpidendl; urgset.erase(maxurg); idurg.erase(pid); urgid.erase(maxurg); } else if(op4){ int id,newurg; cinidnewurg; int oldurgidurg[id]; urgset.erase(oldurg); urgid.erase(oldurg); idurg[id]newurg; urgid[newurg]id; urgset.insert(newurg); } else if(op5){ int newid,urg; cinnewidurg; int oldidurgid[urg]; idurg.erase(oldid); idurg[newid]urg; urgid[urg]newid; } else if(op6){ int id; cinid; if(!idurg.count(id))couterror\n; else coutidurg[id]endl; } else if(op7){ int urg; cinurg; if(!urgid.count(urg))couterror\n; else couturgid[urg]endl; } } return 0; }
)
