<style> h2{ color:#8B4746; } .blue{ color:#4A919E } </style> <font color="#4A919E">DSA 第八週講義</font> === >[name= 沈奕呈、林德恩][time=Mar 11,2022 ] ###### tags:`DSA` `Data Structure and Algorithm` `資料結構` `演算法` `Data Structure` `Algorithm` `tcirc39th` `社課` `臺中一中電研社` [TOC] --- ## <div class="blue">電研社</div> 社網:[tcirc.tw](https://tcirc.tw) online judge:[judge.tcirc.tw](https://judge.tcirc.tw) IG:[TCIRC_39th](https://www.instagram.com/tcirc_39th) --- ## 資料結構 (Data Structure) <!-- https://www.csie.ntu.edu.tw/~r95116/CA200/slide/C6_DataStructure.pdf --> ### 介紹 資料結構是在電腦中用於儲存、組織資料的方式 ---- ### 常見資料結構種類 堆疊（Stack） 佇列（Queue） 陣列（Array） 連結串列（Linked List） 樹（Tree） 堆積（Heap） 圖（Graph） 雜湊表（Hash table） <!--維基百科--> --- ## 樹 (tree) <!-- https://www.csie.ntu.edu.tw/~r95116/CA200/slide/C10_Tree.pdf --> 樹是一種電腦的資料結構，如同容器一樣可儲存資料，並有效地插入，搜尋資料  [image link](https://www.google.com/url?sa=i&url=https%3A%2F%2Ftowardsdatascience.com%2F8-useful-tree-data-structures-worth-knowing-8532c7231e8c&psig=AOvVaw17gUi1A3LzTZQL70FFlEaX&ust=1636726156512000&source=images&cd=vfe&ved=0CAsQjRxqFwoTCPCQpKK-kPQCFQAAAAAdAAAAABAD) ---- ### 名詞介紹 **Root**:根節點，最上面的一個點 **Node**:節點，相連的點 **Parent**:父節點 **Child**:子節點 **Grandchild**:子節點的子節點 **Ancestor**:祖先節點，在往上跨一代的節點都是該點的Ancestor(不含父節點) **Descendant**:在往下跨一代的節點都是該點的Descendant(不含子節點) ---- **Subtree**:子樹，下面有child的child **Leaves**:葉節點，沒有child的子節點 **Non-terminal Nodes**：非終端節點，除了葉節點之 外的其它節點稱為非終端節點 **Key**:裡面的值 **Edge**:節點之間的連接 **Sibling**:兄弟節點 **Level**:階層，由上往下算(ex.Level 1,Level 2,Level 3...) **Hight**:樹高/樹深，由下往上算有幾層 **Degree**:分支度，子節點數 ***n*元樹**：該樹的一個節點最多擁有*n*個子節點 ---- ### 二元樹(binary tree) 二元樹是樹的其中一種結構，它只有每一層只有兩個分支 習慣上認為兩個子樹是不同的tree(只有在二元樹) ---- 完滿二元樹（Full Binary Tree）:每一層都是最大節點數 完整二元樹（Complete Binary Tree）:是完美二元樹或除了最後一層以外是滿的，如果有缺少，一定從右邊開始缺，並且是連續。 Binary Max Tree:根節點$\ge$其子節點，並且其子樹也符合此兩個條件 Binary Mini Tree:根節點$\le$其子節點，並且其子樹也符合此兩個條件 ---- Complete Binary Tree  ---- ### 二元搜尋樹(BST ,Binary Search Tree)  [image link](https://www.google.com/url?sa=i&url=https%3A%2F%2Fithelp.ithome.com.tw%2Farticles%2F10205875&psig=AOvVaw1vT_qOt_Jj5MerGNK2x9ma&ust=1636726227746000&source=images&cd=vfe&ved=0CAsQjRxqFwoTCPj3_8K-kPQCFQAAAAAdAAAAABAD) ---- 二元搜尋樹一定是排序過後的樹 排序後右邊的樹一定比左邊大，右子樹比左子樹大 時間複雜度是$O(h)$ 如果又同時是complete tree，其時間複雜度是$O(log_2n)$ ---- #### BST的插入和刪除   ---- 實作 ---- ### 二元樹的走訪 #### 中序(in-order) 先從左邊，接著自己，再接右邊  [來源](https://commons.wikimedia.org/wiki/File:Binary_search_tree.svg) 中序遍歷排成 `1、3、4、6、7、8、10、13、14` 中序遍歷後的BST一定是按照大小 ---- #### 前序(pre-order) 先從自己，接著左邊，再接右邊  [來源](https://commons.wikimedia.org/wiki/File:Binary_search_tree.svg) 前序遍歷排成 `8、3、1、6、4、7、10、14、13` ---- #### 後序 先從左邊，接著右邊，再接自己  [來源](https://commons.wikimedia.org/wiki/File:Binary_search_tree.svg) 後序遍歷排成 `1、4、7、6、3、13、14、10、8` 二元樹只要有**前序或後序**及**中序**就能還原 ---- ### 儲存 #### 陣列儲存 根節點是0 左子樹是父節點編號乘以2 右子樹是父節點編號乘以2加1 如果該編號位置是空的，陣列也要空下來 優點:操作容易，要找每個節點都很容易 缺點:在非完滿二元樹的儲存效率較低 ---- #### 鏈結儲存 <!-- --> 在每個節點儲存自己的資料、左節點和右節點的指標 優點:在儲存歪斜樹之類的樹用的空間比陣列小 缺點:在儲存葉節點會浪費未用到的兩個指標的空間(值為NULL) <!-- ``` struct binary_tree_node { 資料型態 變數名稱; struct binary_tree_node *left; struct binary_tree_node *right; }; typedef struct binary_tree_node node; node *root; root = (node *)malloc(sizeof(node)); root ->left= NULL; root ->right= NULL; ```--> <!-- https://youtu.be/QzO0rag6geA?list=PLil-R4o6jmGiDc1CC8PyBbasl8kR9r8Wr&t=3400 --> --- ## heap ---- ### 舉例 #### max-heap 具有max tree和complete binary tree #### mini-heap 具有mini tree和complete binary tree #### binomial heap ---- ### max-heap和mini-heap的刪除 刪除後將最後一項補到刪除的位置，再移動到符合max或mini的位置 時間複雜度是$O(log_2n)$ ---- ### max-heap和mini-heap的插入 將插入的值放到最後，再移動到符合max或mini的位置 時間複雜度是$O(log_2n)$ <!--https://youtu.be/RjvhXL0WTrY?t=8389 --> <!-- --- ## Hash Table 可以將資料量減少 先將資料進行運算再壓縮，因為進行壓縮，所以有機會有一些會重複，稱之為碰撞，hash function越複雜，越難看出原本的值，也可以用於使資料難以知道原值，如: 比如說hash table --> <!-- https://youtu.be/SBQLkYIDAZI?t=7364 --> <!-- https://www.youtube.com/watch?v=WX-z52QweUs --> --- ## 列舉 列舉就是**跑過所有可能的情況**的方法，面對**資料量很小**的演算法問題，可以用列舉簡單暴力的解決 適時使用列舉，能幫你在比賽中**省下不少思考時間**； 不過這個方法遇到資料量大的題目就沒轍了。 ---- ### 優化/剪枝 根據列舉的方式不同，程式所需的時間複雜度可能會大大的不同 如果能善用優化和剪枝的技巧，將能增加通過題目的機會 - **優化**：減少時間複雜度的級別 ex.拆掉一層或一個迴圈 - **剪枝**:減少不必要的細節 ex.符合題目要求後跳出迴圈，而不是等迴圈跑完 --- ### 列舉全排列 O(n!) 題目：[c028: 最短貨物運送距離](https://judge.tcirc.tw/ShowProblem?problemid=c028) 題目說明：在二維座標中，從原點出發經過四個站點，求最短總距離及走訪順序 輸入量：4 ---- 首先，四個站點兩兩之間的距離有的長有的短，所以「**走訪的順序**」會影響到行走的總距離 如果我們從四個點中挑一個當作第一站，再從剩下三個點中挑一個當作第二站...走訪順序就會有4!種方式 才四個站點，別多想了，就把所有可能列舉一遍吧 ---- #### 時間複雜度 列舉全排列的時間複雜度為 $O(n!)$， 因為輸入的資料量 n <=10 ，使用這個方法不會TLE ----  ---- #### 列舉方法 如何列舉出所有走訪順序? >分別列舉出a.b.c.d站當第一站的走訪順序 如何列舉出a站當第一站的走訪順序? >分別列舉出b.c.d站當第第二站的走訪順序 --- 「<font color="ff0000">在我們解決問題之前，得要先處理另一個子問題 在解決子問題之前，得要先處理另一個子子問題</font>」 -- 這就是遞迴的核心概念 而因為總共只有四個站點，這個遞迴的停止條件便是「列舉第五個站點」 ---- #### 函式設計 1.預期作用:列舉第i個站點 2.設定終止條件:i==5 3.計算、比較最短距離及選點順序 4.用「迴圈」列舉a.b.c.d當第i個站點的情況 5.用陣列紀錄目前選點順序 6.迴圈裡面呼叫「函式本身」，先去列舉a.b.c.d當第i+1個站點的情況 ---- 宣告後面會用到的變數和函式(等後面用到再回來看) ```cpp= #include <bits/stdc++.h>//萬用標頭檔 using namespace std; const int max_n=4; const int max_v=1e6;//1.4*2*1e6 < 2e9 const int inf=1e7; struct pos{int x,y;}; pos item[5];//以struct紀錄四個點的x.y座標 double ans_dis,t_dis;//目前最短總距離；目前總距離 int ord[2][5];//ord[0][i]為目前最短順序，ord[1][i]為當前順序 bool vis[5]={};//紀錄點有沒有被走過 double dis(pos a,pos b){//計算距離 return sqrt( pow(a.x-b.x,2)+pow(a.y-b.y,2) ); } ``` ---- 遞迴函式 ```cpp= void recursion(int t){ //終止條件 if(t==5){ t_dis=0; for(int i=1;i<=4;i+=1){ t_dis+=dis( item[ ord[1][i] ] , item[ ord[1][i-1] ] ); } if(t_dis<ans_dis){//字典序較大者，總距離一定得更小 ans_dis=t_dis;//更新距離、順序 for(int i=1;i<=4;i+=1){ ord[0][i]=ord[1][i]; } } return; } //recursion for(int i=1;i<=4;i+=1){ if(vis[i]==1) continue; vis[i]=1;//挑第幾個點 ord[1][t]=i;//第幾次挑的點 recursion(t+1); vis[i]=0;//取消挑這個點，換下個點 } } ``` ---- 主程式 ```cpp= int main() { //init item[0]={0,0};//原點 ord[0][0]=0; ord[1][0]=0; //預設值要比可能的答案都還要大，才能找到越來越小的答案 ans_dis=inf; //cin for(int i=1;i<=4;i+=1){ cin>>item[i].x>>item[i].y; } //列舉 recursion(1); //cout //加上「<<fixed<< setprecision(2)」取兩位小數 cout<<fixed<< setprecision(2)<<ans_dis<<'\n'; for(int i=0;i<=4;i+=1) cout<<ord[0][i]; return 0; } ``` --- ### 子集合列舉 $O(2^n)$ 題目：[d007: 習題 Q-1-8. 子集合的和](https://judge.tcirc.tw/ShowProblem?problemid=d007) 題目說明：在一個數字集合內挑一些數字，使選出的數字集合最接近P且不超過P 輸入量：25 ---- 每個數字有**選與不選**兩種可能，只要列舉出所有情況的數字總和，就能找到最接近P且不超過P的數字總和 總共有 $2^{25}$ 種情況呢! 還算可以，先試試看吧 ---- #### 時間複雜度 列舉全排列的時間複雜度為 $O(2^n)$， 因為輸入的資料量 n <=25 ，使用這個方法還不會TLE，n到30大概就TLE惹 ---- #### 列舉方法 如何列舉出所有情況? >分別列舉出第一個數字選與不選的情況 如何列舉出第一個數字選與不選的情況? >分別列舉出第二個數字選與不選的情況 你很聰明😏，又是遞迴 ---- #### 函式設計 1.預期作用:列舉第x個數字選與不選兩種情況 2.設定其一終止條件:x>=n 3.不選數字，呼叫「函式本身」，先去列舉第x+1個數字選與不選兩種情況 4.設定其二終止條件:數字總和超過P 5.選數字，與目前最大數字和比較 6.呼叫「函式本身」，先去列舉第x+1個數字選與不選兩種情況 ---- ```cpp= #include <bits/stdc++.h> using namespace std; const int max_n=25; const int max_p=1e9+9;//p、num、ans可用int long long a[25];//數字大小沒限制 int n,p,num,ans; void recursion(int x){ if(x>=n) return;//終止條件1 recursion(x+1);//不選第x個數字 if(num+a[x]>p) return;//終止條件2 num+=a[x];//選第x個數字 ans=max(ans,num);//因數字總和變大，與目前最大數字和比較 recursion(x+1); num-=a[x];//復原沒有選過的狀態 } int main(){ cin>>n>>p; for(int i=0;i<n;i+=1) cin>>a[i]; ans=0; num=0; recursion(0); cout<<ans<<'\n'; return 0; } ``` --- ### 二維陣列列舉 $O(n^2)$ 題目：[atcoder:abc241_c](https://atcoder.jp/contests/abc241/tasks/abc241_c) 題目說明：在一個二維陣列裡面有 ``＃`` 和 `．`兩種字元，如果將其中至多兩個 `．` 改成 `＃` ，能將六個 `＃`連成一線(直橫斜都可)，輸出"Yes"，否則輸出"No" 輸入量：1000 ---- 如果在二維陣列所有長度為6的直橫斜線中，有一條含有至少四個 '#'， 就可以透過將剩下的 '．' 改成 '＃' ，讓六個 '＃'連成一線 而列舉二維陣列的每一點，往八個方向延伸，就等於是列舉出每一條長度為6的直橫斜線惹~ ---- 「在二維陣列裡藉由各種方式延伸，查看有無符合題目要求」，這種題目蠻常見的，資料量小的可以用雙層迴圈列舉( $O(n^2)$ )，資料量大的則需使用特定演算法 ---- #### 列舉方法: 用雙層迴圈列舉二維陣列裡的每一個點當起點，往八個方向向外延伸五格，如果某個方向的六格皆在二維陣列內，且其中有至少四個 '#'，就能符合題目要求了 ---- #### 時間複雜度 二維陣列列舉的時間複雜度為 $O(n^2)$， 因為輸入的資料量遠小於5000，放心的列舉二維陣列的每一格吧 ---- ```cpp= #include <bits/stdc++.h> using namespace std; const int max_n=1e3; int n,flag; //上、下、左、右、左上、右上、左下、右下 int dr[8]{-1,1, 0,0,-1,-1, 1,1};//上下 int dc[8]{ 0,0,-1,1,-1, 1,-1,1};//左右 string block[max_n]; void line(int r, int c,int k){ int temp=0; for(int l=0;l<6;l+=1){ if(r>=n || c>=n || r<0 || c<0) break; if(block[r][c]=='#') temp+=1; if(l==5 and temp>=4) flag=1; r+=dr[k]; c+=dc[k]; } return; } int main() { cin>>n; for(int i=0;i<n;i+=1) cin>>block[i]; flag=0; for(int r=0;r<n;r+=1){ for(int c=0;c<n;c+=1){ for(int k=0;k<8;k+=1) line(r,c,k); } } (flag)? cout<<"Yes" : cout<<"No"; return 0; } ``` ---- #### 剪枝方向: 1. 函式跑完後如果flag=1後跳出迴圈 2. 因為是由左上往右下列舉，只需往「右、右下、下、左下」四個方向沿伸 因為時間很夠所以就不示範剪枝版本了 --- ### 折半列舉 題目：[d019: 例題 Q-2-10. 子集合的和(折半枚舉)](https://judge.tcirc.tw/ShowProblem?problemid=d019) 題目說明：在一個數字集合內挑一些數字，使選出的數字集合最接近P且不超過P 輸入量：38 ---- 好欸，一樣的題目!! 等等...剛才的方法ｎ到25不是極限了嗎，這題的ｎ居然是38！? 如果把38個數分成兩半，分別列舉兩邊所有情況的數字總和後(n=19)，再從兩邊(或一邊)各取一數相加是不是就可以了? ---- 1. 分別列舉兩邊「所有情況」的「數字總和」S(A)、S(B) 並記錄 $O(2^{n/2})$+$O(2^{n/2})$ 2. 分別列舉S(A)、S(B)裡的元素相加 $2^{n/2}$個*$2^{n/2}$個=$O(2^n)$ 時間複雜度=$O(2^{n/2})$+$O(2^{n/2})$+<font color="ff0000">$O(2^n)$</font> ---- 這樣沒有比較好啊!! 冷靜一下，第二點是可以優化的 ---- A集合取一個數，B集合取一個數，兩者相加找最接近的值 其實有比列舉更快的方法，而且我們用過很多次 EX. x、y是整數，3x+2y<=30，求3x+2y最接近30的數字 遇到題目，我們通常會列舉 3x=3、6、9...的情況 再找出 2y 的情況中找出 <= 30-3x 的最大值 ---- 前述的3x、2y等同於**題目裡集合S(A)、S(B)** S(3X)={3,6,9,...,30} ； S(2Y)={2,4,6,...,30} 而前述「找出 2y 中 <= 30-3x 的最大值」 **等同於在S(B)中找出符合( S(B)<=P-S(A) )的最大元素** 這個部分可以用set的upper_bound()實現 ---- #### 時間複雜度 1. 分別列舉兩邊「所有情況」的「數字總和」S(A)、S(B) 並記錄 $O(2^{n/2})$+$O(2^{n/2})$ 2. 列舉S(A)，S(B)用upper_bound()找出S(B)中符合條件的最大值 $O(2^{n/2})$*$O( log2^{n/2} )$ 時間複雜度=$O(2^{n/2})$+$O(2^{n/2})$+<font color="ff0000">$O(n)$ * $O(2^{n/2})$</font>=$O(2^{n/2})$ ---- #### lower_bound() / upper_bound() set中有一組方便的函式 `lower_bound() / upper_bound()` - `.upper_bound(x)` :回傳第一個大於指定的值的元素 iteritor(沒有就回傳.end()) **-> `.*upper_bound(x)` 找大於x的最小元素的值** - `.lower_bound()` :回傳第一個大於等於指定的值的元素 iteritor(沒有就回傳.end()) **-> `.*lower_bound(x)` 找大於等於x的最小元素的值** ---- 如果我們要找出符合( S(B)<=P-S(A) )的最大元素 就把S(B)丟進去multiset，使用`.*(upper_bound(x)-1)` 找小於等於x的最大元素的值 <font color="ff0000">注意1:數字會重複所以要用multiset</font> <font color="ff0000">注意2:記得要加星號取該元素iterator的值</font> ----  ---- ```cpp= #include <bits/stdc++.h> using namespace std; const int max_n=38; const long long max_v=1<<60; long long a[38]; int n; long long p,num,ans; vector<long long> sum_a; multiset<long long> sum_b; ``` ---- 函式 ```cpp= void SA(int x){ if(x>=n/2) return; SA(x+1); if(num+a[x]>p) return; num+=a[x]; sum_a.push_back(num); SA(x+1); num-=a[x]; } void SB(int x){ if(x>=n) return; SB(x+1); if(num+a[x]>p) return; num+=a[x]; sum_b.insert(num); SB(x+1); num-=a[x]; } ``` ---- 主程式 ```cpp= int main(){ cin>>n>>p; for(int i=0;i<n;i+=1) cin>>a[i]; ans=0; num=0; SA(0);//S(A) SB(n/2);//S(B) //折半枚舉 multiset<long long>::iterator it; if(sum_b.empty()==0){ it=sum_b.end(); it--; ans=max(ans,*(it));//只選S(B) } vector<long long>::iterator begin=sum_a.begin(); vector<long long>::iterator end=sum_a.end(); for(auto sa=begin;sa!=end;sa++){ it=sum_b.upper_bound(p-*(sa) ); //S(B)中所有元素均超過p-S(A) if(it==sum_b.begin() ){//只選S(A) ans=max( ans,*(sa) ); continue; } it--; //比較S(A)+S(B)與目前最大數字總和 ans=max( ans,*(it)+*(sa) ); } // cout<<ans<<'\n'; return 0; } ```