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

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++ 彰雲嘉區複賽106-5 回文日期問題

窮舉法

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
using namespace std;

int dom[15]={0,31,28,31,30,31,30,31,31,30,31,30,31,0,0};
int pro[700],nt,ct=0;

void check(int y){
    if(y%400==0 || (y%4==0 && y%100!=0)){
        dom[2]=29;
    }else dom[2]=28;
}

void isv(int a){
    string s;
    int b=a;
    while(a>0){
        s+=char(a%10+'0');
        a/=10;
    }
    for(int i=0;i<=s.size()/2;i++){
        if(s[i]!=s[s.size()-1-i]){
            return;
        }
    }
    pro[nt++]=b;
    return;
}

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

    int n;
    cin>>n;
    while(n--){
        int y;
        nt=ct=0;
        cin>>y;
        check(y);
        for(int i=1;i<=12;i++){
            int tmp=i;
            for(int j=1;j<=dom[i];j++){
                if(i<10){
                    if(j<10){
                        isv(y*100+i*10+j);
                        isv(y*1000+i*10+j);
                        isv(y*1000+i*100+j);
                        isv(y*10000+i*100+j);
                    }else{
                        isv(y*1000+i*100+j);
                        isv(y*10000+i*100+j);
                    }
                }else{
                    if(j<10){
                        isv(y*1000+i*10+j);
                        isv(y*10000+i*100+j);
                    }else{
                        isv(y*10000+i*100+j);
                    }
                }
            }
            i=tmp;
        }
        cout<<nt<<" ";
        sort(pro,pro+nt);
        for(int i=0;i<nt;i++){
            cout<<pro[i]<<" ";
        }
        cout<<"\n";
    }
    return 0;
} 

出處:GreenJudge