并查集,岛问题,前缀树

程序１：并查集

#include<iostream> //并查集
using namespace std;
#include<string>
#include<limits.h>
#include<vector>
#include<unordered_map>


class UnionFindSet
{
public:
    UnionFindSet(vector<char> nodes)
    {
        makeSets(nodes);
    }

    void makeSets(vector<char> nodes)
    {
        fatherMap.clear();
        sizeMap.clear();
        for(char var:nodes)
        {
            fatherMap.insert({var,var});
            sizeMap.insert({var,1});
        }
    }

    char findHead(char node)
    {
        char father = fatherMap[node];
        if(node != father)
        {
            father = findHead(father);
        }
        fatherMap[node]=father;//将所有结点的父节点都设为代表结点
        return father;
    }

    bool isSameSet(char a,char b)
    {
        return findHead(a)==findHead(b);
    }

    void Union(char a,char b)
    {
        char aHead = findHead(a);
        char bHead = findHead(b);
        if(aHead!=bHead)
        {
            int aSetSize = sizeMap[aHead];
            int bSetSize = sizeMap[bHead];
            if(aSetSize<=bSetSize)
            {
                fatherMap[aHead]=bHead;
                sizeMap[bHead]=aSetSize+bSetSize;
            }
            else
            {
                fatherMap[bHead]=aHead;
                sizeMap[aHead]=aSetSize+bSetSize;
            }
        }  
    }

    unordered_map<char,char> fatherMap;
    unordered_map<char,int> sizeMap;
};

int main()
{
    vector<char> temp = { 'A', 'B', 'C', 'D', 'E', 'H', 'G' };
    UnionFindSet s(temp);
    s.Union('A', 'B');
    cout << s.isSameSet('A', 'B');

    return 0;
}

程序２：岛问题

#include<iostream> //岛问题
using namespace std;
#include<string>
#include<limits.h>
#include<vector>
#include<unordered_map>


/* 单cpu,单内存解决岛问题*/
void infect(int m[][3],int i,int j,int N,int M)
{
    if(i<0 || i>=N || j<0 || j>=M || m[i][j]!=1)
    {
        return;
    }
    m[i][j]=2;
    infect(m,i-1,j,N,M);
    infect(m,i+1,j,N,M);
    infect(m,i,j-1,N,M);
    infect(m,i,j+1,N,M);
}

int countIslands(int m[][3],int N,int M)
{
    if(m==0||m[0]==0)
    {
        return 0;
    }
    int res = 0;
    for(int i = 0;i<N;i++)
    {
        for(int j = 0;j<M;j++)
        {
            if(m[i][j] == 1)
            {
                res++;
                infect(m,i,j,N,M);
            }
        }
    }
    return res;
}

int main()
{
    int m[][3] = {0,1,0,0,1,0,1,0,1};
    int N = sizeof(m) / sizeof(m[0]);  //行
    int M = sizeof(m[0]) / sizeof(int);  //列
    cout<<countIslands(m,N,M);
    return 0;
}

程序3:前缀树

#include<iostream> //前缀树　
using namespace std;
#include<string>

class TrieNode
{
public:
    int path;  //有多少个到达过
    int end;   //有多少个以其为结尾
    TrieNode* nexts[26];
    TrieNode()
    {
        path = 0;
        end = 0;
    }
};


class Trie
{
public:
    Trie()
    {
        root = new TrieNode();
    }

    void insert(string world)
    {
        if(world.empty())
        {
            return;
        }
        TrieNode* node = root;
        int index = 0;
        for(int i = 0;i<world.length();i++)
        {
            index = world[i] - 'a';
            if(node->nexts[index] == nullptr)
            {
                node->nexts[index] = new TrieNode();
            }
            node = node->nexts[index];
            node->path++;
        }
        node->end++;
    }

    int search(string world)
    {
        if(world.empty())
        {
            return 0;
        }
        TrieNode* node = root;
        int index = 0;
        for(int i=0;i<world.length();i++)
        {
            index = world[i] - 'a';
            if(node->nexts[index]==nullptr)
            {
                return 0;
            }
            node = node->nexts[index];
        }
        return node->end;
    }

    void deleteString (string world)
    {
        if(search(world)!=0)
        {
            TrieNode* node = root;
            int index =0;
            for(int i =0;i<world.length();i++)
            {
                index = world[i] - 'a';
                if(--node->nexts[index]->path ==0)
                {
                    node->nexts[index] = nullptr;
                    return;
                }
                node = node->nexts[index];
            }
            node->end--;
        }
    }

    int prefixNumber(string pre)
    {
        if(pre.empty())
        {
            return 0;
        }
        TrieNode* node = root;
        int index = 0;
        for(int i=0;i<pre.length();i++)
        {
            index = pre[i] - 'a';
            if(node->nexts[index] == nullptr)
            {
                return 0;
            }
            node = node->nexts[index];
        }
        return node->path;
    }
private:
    TrieNode* root;
};

int main()
{
    Trie p;
    p.insert("kjfvhb");
    p.insert("kjkjhu");
    p.insert("kiyghj");
    cout<<p.search("kiyghj");

    return 0;
}