目錄
map的若干操作
1、emplace()
2、find(key)
3、count(key)
4、lower_bound 和 upper_bound
5、erase()
6、empty()
7、降序的map
計蒜客T3603 叫號系統
題意：
解題思路：
Code:
Leetcode1309 解碼字母到整數映射
題意：
解題思路：
Code：
Leetcode205 同構字符串
題意：
解題思路：
Code：
計蒜客T1271 完美K倍子數組
題意：
解題思路：
Code：
????????今天主要是map專題，一般map只是一個映射，在程序中大多是一個輔助的存在。不像前面的隊列和棧，它們特殊的結構有一些衍生的算法思想。而map主要是熟悉它的操作，可以更方便的查找。其實原本今天的題目和map關系不是特別大，但是寫到最后一題有很多相關的操作我都很少有用過，查了很多又改了好久才模擬出來。所以在最開始先盤點一下map常用的操作~
map的若干操作
map 鍵值對(key - value)
1、emplace()
功能：原地構造鍵值對，效率更高。
示例：
myMap.emplace(2, "banana"); // 直接構造，無需創建臨時對象2、find(key)
功能：通過鍵查找目標，找到了就返回相應迭代器，如果沒找到返回end()。
示例：
auto it = myMap.find(2);
if (it != myMap.end())cout << "找到鍵 " << it->first << ": " << it->second;
else cout << "未找到";3、count(key)
功能：查找此鍵的個數，由于每個鍵在map中只能出現一次，所以只會返回1或0，可用于判斷某個鍵是否存在。
示例：
if (myMap.count(3) > 0)cout << "鍵3存在";4、lower_bound 和 upper_bound
功能：
- lower_bound：返回第一個大于等于?
key?的迭代器。 upper_bound(key)：返回第一個大于?key?的迭代器。
示例：
map<int, string> myMap = {{1, "a"}, {3, "c"}, {5, "e"}};
auto low = myMap.lower_bound(3); // 指向鍵3
auto up = myMap.upper_bound(3); // 指向鍵55、erase()
功能：???????刪除指定元素。
示例：
myMap.erase(key); // 按鍵刪除
myMap.erase(2); // 刪除鍵2
myMap.erase(myMap.begin()); // 刪除第一個元素
myMap.erase(it); // 按迭代器刪除
myMap.erase(first, last); // 刪除區間 [first, last)6、empty()
功能：判斷此時是否為空，返回值為bool類型。
示例：
if (myMap.empty()) cout << "容器為空";7、降序的map
功能：由于map會自動進行排序，系統默認是升序排序，其實還可以降序
示例：
map<int, int, greater<int>> myMap;myMap[3] = 30;
myMap[1] = 10;
myMap[4] = 40;
myMap[2] = 20;// 輸出結果會是 4,3,2,1
for (auto i : myMap)cout << i.first << ":" << i.second << endl;常用的函數基本就這些了，其實map的主要功能是映射，這些函數是錦上添花。下面看幾道題吧~
計蒜客T3603 叫號系統
鏈接：叫號系統 - 計蒜客
本題很好的考察了map的基本性質，比如排序，鍵、值的查找等。
題意：
????給定1~7七種操作，根據操作執行。
- op=1：將id和u錄入系統；
- op=2：找緊急程度最小的患者,輸出id并刪除.如果沒有輸出error；
- op=3：找緊急程度最大的患者,輸出id并刪除.如果沒有輸出error；
- op=4：將編號為id的病人緊急程度改為urg；
- op=5：將緊急程度為urg的病人編號改為id；
- op=6：查找標號為id的病人的urg并輸出,如果沒有輸出error；
- op=7：查找緊急程度為urg的病人的id并輸出,如果沒有輸出error；
解題思路：
? ? ? ?本題是個大模擬，要對鍵、值的查找比較熟悉，操作比較多需要認真一點。
接下來直接看代碼吧。
Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second
#define endl '\n'
const int N = 1e6+5;
map<int, int> mp;
int id,u;//Id和緊急程度
int op;
void solve()
{cin >> op;if(op==1)//將id和u錄入系統{cin >> id >> u;mp[u]=id;//由于后面要找緊急程度的大小,所以按urg排序}if(op==2)//找緊急程度最小的患者,輸出id并刪除.如果沒有輸出error{if(mp.empty()){cout << "error" << endl;return ;}auto it = mp.begin();//迭代器類型索引用->cout << it->se << endl;mp.erase(it);}if(op==3)//找緊急程度最大的患者,輸出id并刪除.如果沒有輸出error{if(mp.empty()){cout << "error" << endl;return ;}auto it = --mp.end();//索引最后一個的時候用--end,end是最后一個的下一個cout << it->se << endl;mp.erase(it);}if(op==4)//將編號為id的病人緊急程度改為urg{cin >> id >> u;for(auto i:mp){if(i.se==id){auto it=mp.find(i.fi);mp.erase(it);mp[u]=id;break;}}}if(op==5)//將緊急程度為urg的病人編號改為id{cin >> id >> u;for(auto i:mp){if(i.fi==u){mp[u]=id;break;}}}if(op==6)//查找標號為id的病人的urg并輸出,如果沒有輸出error {cin >> id;int f=0;for(auto i:mp){if(i.se==id){f=1;cout << i.fi << endl;return ;}}if(!f) cout << "error" << endl;}if(op==7)//查找緊急程度為urg的病人的id并輸出,如果沒有輸出error {cin >> u;if(mp.find(u)==mp.end()){cout << "error" << endl;return ;}else{auto it=mp.find(u);cout << it->se << endl;}}
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int t=1;cin >> t;while(t--) solve();return 0;
}Leetcode1309 解碼字母到整數映射
鏈接：1309. 解碼字母到整數映射 - 力扣（LeetCode）
本題我直接用ASCII進行存值，但此題有點麻煩導致寫的時候感覺有點亂
題意：
????????根據題中給的解碼規則進行解碼。
解題思路：
? ? ? ? 1~9的解碼比較容易，10之后的有點麻煩，我是將數字和#分開判斷，注意的是10之后一次是占據三個位置，注意下標不要超。
Code：
class Solution {
public:string freqAlphabets(string s) {map<int, int> m;string s1="";for(int i=1; i<=26; i++) m[i]='a'+i-1;//創建鍵值對int i;for(i=0; i<s.size()-2; i++)//如果i在后兩個i+2會超{if(s[i+2]!='#') s1+=m[s[i]-'0'];else{int num=(s[i]-'0')*10+s[i+1]-'0';s1+=m[num];i+=2;}}if(i>s.size()-3)//單獨處理在后兩位的情況for(auto j=i; i<s.size(); i++) s1+=m[s[i]-'0'];return s1;}
};Leetcode205 同構字符串
鏈接：205. 同構字符串 - 力扣（LeetCode）
題目其實還是比較簡單，需要注意的點就是所有的鍵和值都是唯一的。
題意：
? ? ? ? 給定兩個字符串看它們是否完全符合一定的映射規則。
解題思路：
? ? ? ? 按照所給字符串進行映射關系的建立和判斷，如果前后沖突則為否。
Code：
class Solution {
public:bool isIsomorphic(string a, string b) {map<int, int> m;//這里用字符的ASCII碼進行映射map<int, int> m1;for(int i=0; i<a.size(); i++){if(m[a[i]])//有值的話判斷值{if(m[a[i]]!=b[i])return 0;}else//沒值先判斷當前值是否被映射過{if(m1[b[i]]) return 0;m[a[i]]=b[i],m1[i]=1;//沒有就賦值，再標記一下表示被映射過}}return 1;}
};計蒜客T1271 完美K倍子數組
鏈接：完美K倍子數組 - 計蒜客
這題大思路是對的，就是情況沒考慮周全。
題意：
? ? ? ? 給定一個長度為n的序列，找到一個子數組使得數組中的每個元素兩兩之和都是k的倍數。
解題思路：
? ? ? ? 由于數組中所有的數之和都是k的倍數，那首先很容易想到如果所有數都是它的倍數那么就都可以了。由于是兩兩之和，所以如果K為偶數的話，如果余數為k/2的數兩兩相加那么也一定是k的倍數。如果前面的情況都不是，那么當兩個數相加剛好等于k的倍數的時候那也可以，有點像昨天的某一道題。
Code：
unordered_map<int, int> m;//余數->出現次數
void solve()
{cin >> n >> k;for(int i=1; i<=n; i++)cin >> a[i],m[a[i]%k]++;if(k%2==0){//余數剛好是k/2/*例: 5 105 5 15 25 95*/for(int i=1; i<=n; i++) if(a[i]%k==k/2) num++;ans=max(ans,num);num=0;}for(int i=1; i<=n; i++) if(a[i]%k==0) num++;ans=max(ans,num),num=0;if(ans<2){for(int i=1; i<=n; i++) {int r = a[i]%k;//余數int c = (k-r)%k;//剛好和余數互補if(m[c]&&(m[c]>=2||(m[c]>= 1&&c!=r))){ans=2;break;}}}if(ans<2)cout << -1;else cout << ans;
}總體來說題目依舊比較高質量，雖然沒什么算法，但也暴露出基本功的問題，不涉及算法的題還要修改好久，思路不夠靈敏，繼續加油吧！
