標籤: review

C++資料結構：Binary Search Tree

mtmatt, C++學習心得Leave a Comment on C++資料結構：Binary Search Tree

Binary Search Tree (二元搜尋樹)，是用來存放多筆資料，並快速搜尋的資料結構。大概的原則就是，大的放右邊，小的放左邊。

新增，刪除一個值都只要O(log(N))

以下為實作範例

#include<bits/stdc++.h>
using namespace std;

template<class T>
class bst{
    private:
        struct node{
            T val;
            node* l,r;

            node(){
                l=r=nullptr;
            }
            node(T v){
                l=r=nullptr;
                val=v;
            }
        };

        bool find(node *n,T v){
            if(n->val==v){
                return true;
            }else if(n->val > v && n->r!=nullptr){
                find(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                find(n->l,v);
            }else{
                return false;
            }
        }

        void insert(node *&n,T v){
            if(n==nullptr){
                node nd=new node(v);
                n=&nd;
            }else if(n->val > v && n->r!=nullptr){
                insert(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                insert(n->l,v);
            }
        }

        void DeleteNode(node *&n){
            if(n->l==nullptr && n->r==nullptr){
                delete n;
                n=nullptr;
            }else{
                node *left,*right;
                if(n->l==nullptr){
                    right=n->r;
                    n->val=right->val;
                    n->l=right->l;
                    n->r=right->r;
                    delete right;
                }else if(n->r==nullptr){
                    left=n->l;
                    n->val=left->val;
                    n->l=left->l;
                    n->r=left->r;
                    delete left;
                }else{
                    right=n;
                    left=n->l;
                    while(left->r!=nullptr){
                        right=left;
                        left=left->l;
                    }
                    n->val=left->val;
                    if(right!=n)
                        right->r=left->l;
                    else
                        right->l=left->l;
                    delete left;
                }
            } 
        }

        void erase(node *n,T v){
            if(n->val==v){
                DeleteNode(n);
            }else if(n->val > v && n->r!=nullptr){
                erase(n->r,v);
            }else if(n->val < v && n->l!=nullptr){
                erase(n->l,v);
            }
        }

        void DeleteTree(node *n){
            if(n->l!=nullptr)
                DeleteTree(n->l);
            if(n->r!=nullptr)
                DeleteTree(n->r);
            delete n;
        }
    public:
        bst(){
            root=nullptr;
            sz=0;
        }

        ~bst(){
            if(root!=nullptr)
                DeleteTree(root);
        }

        bool find(T v){
            if(root!=nullptr)
                return find(root,v);
        }

        void insert(T v){
            if(root==nullptr){
                node n=new node(v);
                root=&n;
            }else{
                insert(root,v);
            }
            sz++;
        }

        void erase(T v){
            if(root==nullptr) return;
            erase(root,v);
            sz--;
        }

        int size(){
            return sz;
        }
    private:
        node *root;
        int sz;
};



相同的，C++都幫你做好了，就是所謂的Set & Map。

以下為使用範例

#include<bits/stdc++.h>
using namespace std;

int main(){
    vector<int> v(100);
    for(int i=0;i<100;++i){
        v[i]=i;
    }
    random_shuffle(v.begin(),v.end());

    set<int> s;
    for(auto a:v){
        s.insert(a);
    }

    random_shuffle(v.begin(),v.end());

    for(auto a:v){
        cout<<*s.lower_bound(a)<<" ";
        cout<<*s.upper_bound(a)<<"\n";
    }
    s.erase(10);
    cout<<*s.lower_bound(10);
}



我相信許多人跟我一樣，一開始不知道這些東西要用在哪？

以下我找了幾個範例

1. 在O(Nlog(26))以內找出是否有一個字母在兩個字串中均能被找到(出處：HackerRank)

string twoStrings(string s1, string s2) {
    set<char> s;
    for(auto a:s1){
        s.insert(a);
    }
    for(auto a:s2){
        if(s.count(a)){
            return "YES";
        }
    }
    return "NO";
}

2. 以O(N3log(N))找出一個字串中無序變形子串對的數目(出處：HackerRank) 最重要的，就是其刪除快速的特性

int sherlockAndAnagrams(string s) {
    int ct=0,len=s.size();
    for(int i=0;i<len;i++){
        for(int j=i;j<len;j++){
            multiset<char> st,tt;
            for(int k=i;k<=j;k++){
                st.insert(s[k]);
                tt.insert(s[k]);
            }

            for(int k=i+1;k<len-(j-i);k++){
                tt.insert(s[k+(j-i)]);
                auto it=tt.find(s[k-1]);
                if(it!=tt.end()) tt.erase(it);
                if(tt==st) ct++;
            }
        }
    }
    return ct;
}

3. 最後一個是Map的應用範例，Map是以first做排序依據，second存放對應資料。最常見的就是數字與出現頻率，以下甚至還有用來存頻率的頻率的用法。(出處：HackerRank) m 放<數字 , 頻率>，ct 放<頻率 , 頻率的頻率>

vector<int> freqQuery(vector<vector<int>> q) {
    vector<int> ans;
    map<int,int> m,ct;
    for(auto a:q){
        if(a[0]==1){
            ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
            m[a[1]]++;
            ct[m[a[1]]]++;
        }else if(a[0]==2){
            ct[m[a[1]]]=max(ct[m[a[1]]]-1,0);
            m[a[1]]=max(m[a[1]]-1,0);
            ct[m[a[1]]]++;
        }else{
            ans.push_back(bool(ct[a[1]]));
        }
    }
    return ans;
}

下一篇心得會補 pointer (指標) 的部分，在此之前可以先Google搜尋(C++指標)。

C++資料結構：Stack & Queue

mtmatt, C++學習心得Leave a Comment on C++資料結構：Stack & Queue

Stack，又稱作堆疊，顧名思義就是從上面(也可以說前面)放入與取出的資料結構。 Queue，稱為佇列，是從前面放後面取出的資料結構。

實作程式碼如下

#include<bits/stdc++.h>
using namespace std;

template<class T>
class Stack{
    private:
        int t=-1;
        vector<T> dt;
    public:
        T top(){
            if(t!=-1){
                return dt[t];
            }else{
                cout<<"Stack is empty.\n";
            }
        }

        void pop(){
            if(t!=-1){
                t--;
                dt.pop_back();
            }else{
                cout<<"Stack is empty.\n";
            }
        }

        void push(T p){
            t++;
            dt.push_back(p);
        }
};

template<class T>
class Queue{
    private:
        deque<T> dt;
    public:
        T front(){
            if(!dt.empty()){
                return dt.front();
            }else{
                cout<<"Queue is empty.\n";
            }
        }

        void pop(){
            if(!dt.empty()){
                dt.pop_front();
            }else{
                cout<<"Queue is empty.\n";
            }
        }

        void push(T p){
            dt.push_back(p);
        }
};

C++已經幫你將這兩個資料結構實做好了，以下示範例程式碼

#include<iostream>
#include<stack>
#include<queue>
#include<deque>

using namespace std;

int main(){
    stack<int> st;
    for(int i=0;i<10;++i){
        st.push(i);
    }
    cout<<st.size()<<"\n";
    while(!st.empty()){
        cout<<st.top()<<" ";
        st.pop();
    }
    cout<<"\n\n";

    queue<int> q;
    for(int i=0;i<10;++i){
        q.push(i);
    }
    cout<<q.size()<<"\n";
    while(!q.empty()){
        cout<<q.front()<<" "<<q.back()<<"\n";
        q.pop();
    }
    cout<<"\n";
}

光聽這兩個介紹以及大部分的分享，相信你還是不知道這兩個東西要用在哪裡。以下會有幾個應用的範例，都是用 STL 。

1.在 O(N) 的複雜度下做單調對列 Ex : 洛谷

題目敘述：
對於每個元素，從後面找出第一個比他大的元素的位置

這題就是要透過 stack 保持裡面所存位置對應的元素的單調遞減性。實際做法就是，遇到比他大的就丟掉，反正已經確認現在這個元素已經比他大了，後面也不會用到。否則他就還沒遇到還沒遇到比他大的。

以下為程式碼

#include<bits/stdc++.h>
using namespace std;

int main(){
    ios::sync_with_stdio(0);cin.tie(0);

    int n;
    cin>>n;
    vector<int> v(n);
    for(int i=0;i<n;++i) cin>>v[i];

    vector<int> ans(n,0);
    stack<int,vector<int>> st;
    for(int i=0;i<n;++i){
        while(!st.empty() && v[st.top()]<v[i]){
            ans[st.top()]=i+1;
            st.pop();
        }
        st.push(i);
    }

    for(int a:ans)
        cout<<a<<" ";
}

2.以 O(N) 在滑動窗口中找最大以及最小值 Ex : 洛谷

題目敘述：
在所有長度為k的窗口中找到最大以及最小值

這題要用deque(double-ended-queue)，也就是雙向佇列，是一個從前後方都可以加入以及刪除值的queue。用以維持內部元素既在範圍以內，又保持單調遞增或遞減。

以下為程式碼

#include<bits/stdc++.h>
using namespace std;
#define ll long long

int nm[1000010]={0},rmax[1000010],rmin[1000010];

int main(){
    int n,k;
    cin>>n>>k;

    for(int i=0;i<n;i++) cin>>nm[i];

    deque<int> mx,mn;

    for(int i=0;i<k;i++){
        while(!mx.empty() && nm[mx.front()]<nm[i])
            mx.pop_front();
        mx.push_front(i);

        while(!mn.empty() && nm[mn.front()]>nm[i])
            mn.pop_front();
        mn.push_front(i);
    }

    rmax[0]=mx.back();
    rmin[0]=mn.back();

    for(int i=1,j=k;j<n;i++){

        while(!mx.empty() && mx.back()<i)
            mx.pop_back();
        while(!mn.empty() && mn.back()<i)
            mn.pop_back();

        while(!mx.empty() && nm[mx.front()]<nm[j])
            mx.pop_front();
        mx.push_front(j);
        while(!mn.empty() && nm[mn.front()]>nm[j])
            mn.pop_front();
        mn.push_front(j);

        rmax[i]=mx.back();
        rmin[i]=mn.back();

        j++;
    }

    for(int i=0;i<n-k+1;i++)
        cout<<nm[rmin[i]]<<" ";
    cout<<"\n";
    for(int i=0;i<n-k+1;i++)
        cout<<nm[rmax[i]]<<" ";
    return 0;
}

未完待續~~

C++ 並查集實作

mtmatt, C++學習心得Leave a Comment on C++ 並查集實作

並查集，適用於高速判斷AB是否再同一組，以及合併兩組。

#include<bits/stdc++.h>
using namespace std;

class dsu{
    private:
        vector<int> p;
        vector<long long> rank;
    public:
        void init(int n){
            for(int i=0;i<=n;i++){
                p.push_back(i);
                rank.push_back(1);
            }
        }
        
        int find(int a){
            if(a==p[a]) return a;
            return p[a]=find(p[a]);
        }
        
        bool same(int a,int b){
            return find(a)==find(b);
        }
        
        bool uni(int a,int b){
            if(!same(a,b)){
                int rA=rank[find(a)],rB=rank[find(b)];
                if(rA>rB){
                    p[find(b)]=p[find(a)];
                }else if(rA==rB){
                    p[find(b)]=p[find(a)];
                    rank[p[find(a)]]++;
                }else{
                    p[find(a)]=p[find(b)];
                }
            }
        }
};

包含路徑壓縮與啟發式合併。