###### tags: `MDCPP講義` # 基礎資料結構(2) **Author : 謝侑哲** --- ## 上周題目講解 --- [Parentheses Balance](http://mdcpp.mingdao.edu.tw/problem/B005) ---- 分析 : - 當兩個括號互補時，就保證其可以一定合法，不會受其他因素影響 - 他是一個層層相疊的結構，外面的括號會被裡面的括號影響 ---- 思路: - 既然只要括號互補就必定合法，且不受影響，那當其合法，就可以不繼續處理 - 外面的括號會被裡面的括號影響，那能不能把裡面的括號去掉 - 當我們從左看到右來做，最先合法的括號就會是最內層的括號 ---- 解法: 利用stack的特性，從左往右掃，當她出現第一組合法括號時，將其丟掉，一路做到底，如果有剩下的東西，及代表他不合法 ---- 對應思路: - 互補必定合法，不被影響 $\rightarrow$ 可以直接丟掉 - 目標去掉裡面的括號 $\rightarrow$ 利用pop的特性，將其排除 - 最先合法的就是最內層 $\rightarrow$ stack的特性，可以將最後近來的東西丟掉，也就是遇到的最先合法的括號 ---- 圖解:  ----  ----  ----  ----  ----  ----  ----  ---- 為了不讓你們抄，我已經竄改過程式碼了 ```cpp= #include <bits/stdc++.h> using namespace std; int main () { int n; cin >> n; string c; getline(cin,c); //吃掉多的\n for(int j = 0;j < n;j++){ int o = 0; //判斷後面是否輸出 stack<cr> st; string s; getline(cin , s); // 讀入字串 for(int i = 0;i < s.size();i++){ if(s[j] == '(' || s[i] == '['){ st.push(s[i]); // 如果他是左括號就丟進stack }else if(st.empty()){ if(o == 0) // 當她是右括號且stack空時，必定找不到對應的左括號，所以錯 cout << "No\n"; o = 1; //避免多輸出一次 }else if(st.top() == '(' && s[i] == ')'){ st.pop(); //當他符合()的形式，pop掉，注意這裡只丟掉一個是因為另一個根本沒被丟進來 }else if(st.top() == '[' && s[i] == ']'){ st.pop(); //符合[]形式，pop掉 }else if(o == 0){ cout << "No\n"; // 當字串出現奇怪東西或(]、[)的時候，判斷為錯 o = 1; } } if(o == 0){ //最後判斷stack是不是空的，空的就合法 if(st.empty()) cout << "Yes\n"; else{ cout <<< "No\n"; } } } } ``` --- [智乃還債計畫](http://mdcpp.mingdao.edu.tw/problem/T006) ---- 分析: - 要求在"連續"城鎮中打工 - 要求打工的城鎮數最少，但不限制總數 - 有一個最低的賺錢底線 ---- 思路: - 要求在連續城鎮中打工，所以可以利用先進先出的資料結構，因為這樣裡面可以保持連續 - 求打工的城鎮可以利用資料結構的長度來計算 - 有一個最低的賺錢底線，所以當底線符合時，可以做一些處理 ---- 解法: 利用queue的特性，將資料結構裡的城鎮保持連續。 接者一個一個丟進來，當資料結構裡的城鎮能賺到的錢大於底線時，用size()函式判斷他的長度是否小於目前找到的最短長度，如果是，就更新他。 接者把城鎮從前面丟出去，如果仍符合，代表比剛剛找到的長度短，再判斷是否更新 直到賺的錢再次比底線少時，繼續丟城鎮進來 ---- 對應思路: - 用先進先出的結構維護 $\rightarrow$ 用queue - 用資料結構長度來算城鎮樹 $\rightarrow$ 用size()函式 - 當超過底線做處理 $\rightarrow$ 在長度大於底線時，進行更新，並開始丟東西到小於底線 ---- 圖解  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ----  ---- ```cpp= #include<bits/stdc++.h> using namespace std; const int maxn = 50; int x[maxn]; queue<int> q; int main(){ int n, k; cin >> n >> k; // 城鎮數&底線錢 for(int i = 0; i < n; i --) cin >> x[i]; int sum = 0, ans = 1e9; //把 ans 開超大，以找最小 for(int i = 0; i < n; i --){ sum += x[i]; // 紀錄城鎮加起來的錢數 q.push(x[i]); // 將城鎮放入queue if(sum >= k) ans = min(ans, (int)q.size()); // 如果超過底線錢，判斷長度是否比上個長度短 sum -= q.front(); q.pop(); while(sum>= k){ //當出去之後還比底線大 ans = min(ans, (int)q.size()); //再判斷 sum -= q.front(); //重複繼續丟 q.pop(); } } cout << ans; } ``` --- 更多STL容器 --- ## set ---- 他是一個可以自動排序的資料結構 如果你丟給她67428 它會讓他變成24678 但他有一個特性是，只能儲存不同的數字 像是給他695655 他會存成569，多的數字就被排掉了 ---- 關於它的原理 因為有些東西還沒教到了，所以我暫時不打算講 不過可以提幾個關於他原理的詞 ---- - 圖的遍歷 - 中序走訪 - 二元搜尋樹 - 紅黑樹 ...... 聽起來超複雜的對吧，那就有機會再講，或是有興趣的可以再來問講師 ---- 所以先學會怎麼用就好 ---- 宣告: ```cpp= #include<set> using namespace std; set<int> s; ``` 就跟之前一樣 ---- - begin() 回傳遞第一個值的迭代器 - rbegin() 回傳最後一個值的迭代器 - *begin() 回傳遞第一個值 - *rbegin() 回傳最後一個值 如果不知道迭代器是甚麼，可以先把他想成是一個資料的地址，後面我再講 後面兩個\*號就是間接尋址運算子，簡單來說就是可以取得某個地址的值 ```cpp= #include<set> using namespace std; set<int> s; s.begin(); // pointer s.rbegin(); // pointer *s.begin(); *s.rbegin(); ``` ---- find(DT value) 找出某個值在set中的迭代器 基本上跟begin()和end()差不多 值得注意的是，如果find不在set裡面的東西，他會回傳end()的值 ```cpp= #include<set> using namespace std; set<int> s; s.find(10); ``` ---- insert(DT value) 插入東西(因為它會自動排序，就沒有從哪裡插的差別了) 時間複雜度 O(logN) 至於為甚麼，你們之後學到二分搜就會懂了 前面說過，他不能存同樣值，所以如果你插了5，再插一個5就不會發生任何事 ```cpp= #include<set> using namespace std; set<int> s; s.insert(5); ``` ---- erase(DT value) 把東西刪掉 複雜度O(logN) 用這要注意，如果你刪掉不屬於set的東西，他可能會爆掉 在judge上會顯示RE ```cpp= #include<set> using namespace std; set<int> s; s.erase(5); ``` ---- 那要怎麼處理刪到不存在的東西呢? ---- 可以利用find的特性，當find找不到東西就會回傳end()的值 所以當s.find()==s.end()，就代表東西不存在 這時候就不要做erase()操作 ```cpp= if(s.find(5) != s.end()) s.erase(5); ``` ---- 剩下的一些東西 size() 就找大小 set<DT, greater<DT\> > 可以讓set從小到大變大到小 ```cpp= s.size() set<int,greater<int>> s; ``` ---- 補充: 前面提到set不能存重複元素 但C++有個multiset可以做到，用法就跟set幾乎一樣 ---- 練習題: [先到先服務](http://mdcpp.mingdao.edu.tw/problem/AP013) --- 迭代器 ---- 就像前面set說的，他是一個存地址的東西 我們稱它為指標 然後他是用來遍歷容器的工具 ---- 另外他也是一種資料型別 宣告方法如下 ```cpp= vector<int> :: iterator vit; //宣告一個 vector<int>的迭代器 set<int> :: iterator sit; //宣告一個 set<int>的迭代器 // 用v、s + it 當名字是因為我們通常稱取迭代器前兩個字it ``` ---- 剛剛那個超長的宣告很難記住吧 所以我們都用C++11以上提供的auto 他可以自動幫你判斷資料的型別是甚麼 如果你用過python或javascript的var 他的功能就類似 ```cpp= auto sit = s.begin(); // sit 會被判斷為 set<int> :: iterator ``` --- map ---- map就是一個讓你可以給一個值索引，並查詢他的結構 然後它的原理也是紅黑樹，所以不講 ---- 直接進用法 ---- 宣告 ```cpp= #include<map> using namespace std; map<int,int > m; m[0] = 1; ``` 可以發現裡面有兩個值，前面的叫key，後面的叫value key就是他的索引 以範例中m[0]=1，0就是key，1就是value ---- 更多宣告 map裡面的資料型別常常會被放很多元的東西 像是字串、字元、pair等等 ```cpp= map<int,int> mii; map<string,int> msi; map<int,pair<int,int>> mp; ``` 基本上想的到都可以放 ---- 補充: 怕有人不知道pair，他是一個可以存兩個值的資料型別 ```cpp= pair<int ,int > pii; pii.first = 1; //第一個值 pii.second = 2; //第二個值 ``` map 存的東西就是pair ---- map基本操作 加入元素: 因為跟set一樣是紅黑樹，所以複雜度是O(logN) 有兩種做法 ---- 作法一 直接在對應的點宣告他的值 ```cpp= map<string,int> mp; mp["abc"] = 12; mp["bca"] = 16; mp["bca"]++; // mp["bca"] = 17 ``` ---- 作法二 利用insert函式 ```cpp= map<string,int> mp; mp.insert( pair<string,int>("aaa",1) ); mp.insert({"aaa",1}); mp.insert(make_pair("aaa",1)); //三的東西其實一樣，只是換了造出pair的方式 ``` 有時候作法一會莫名掛掉，掛掉的時候就可以換成作法二 ---- erase( DT value ) 把對應key的值刪掉 ```cpp= map<string,int> mp; mp["abc"] = 12; s.erase("abc"); ``` 複雜度也是O(logN); ---- 查找元素 find(DT　value) 找元素的迭代器 你們可能會想，直接中括號裡面放key不就好了 但這樣不是最好的做法 ---- ```cpp= mp["loli"] = 12; if(mp.find("loli") != mp.end()) cout << mp["loli"] << '\n'; //建議用法 優點 時間較快 不會增加多餘記憶體 if(mp["loli"]) cout << mp["loli"] << '\n'; //不建議用法 缺點如果查找元素不再map中 //會多開出記憶體並把值設為0且時間較慢 ``` ---- 清空 ```cpp= mp.clear(); ``` ---- 迴圈遍歷map ```cpp= for(auto i : mp) //這是遍歷STL容器中所有元素的做法，在vector之類的也可以用 cout << i.first << ' ' << i.second << '\n'; ``` ---- 練習題: [2-SET](http://mdcpp.mingdao.edu.tw/problem/B033)