Data Struct

Author Avatar
Xin Wei 4月 05, 2017
  • 在其它设备中阅读本文章

字典树(Trie)–String 搜索

字典搜索树
搜索的时间复杂度为O(L),L为树种最长单词长度

nclude <iostream>
#include <unordered_map>
#include <string>

using namespace std;

class TrieNode
{
    public:
        TrieNode()
        {
            isLeaf = false;
        }
        bool isLeaf;
        unordered_map<char, TrieNode*> children;
};

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

        void insert(string word)
        {
            TrieNode *r = root;
            for (char ch : word)
            {
                if (r->children.find(ch) == r->children.end())
                    r->children[ch] = new TrieNode();
                r = r->children[ch];
            }
            r->isLeaf = true;
        }

        bool search(string word)
        {
            TrieNode *r = root;
            for (char ch : word)
            {
                if (r->children.find(ch) == r->children.end())
                    return false;
                r = r->children[ch];
            }
            return r->isLeaf;
        }

    private:
        TrieNode *root;
};

int main()
{
    int n, i = 0;
    cin >> n;
    string word;
    Trie trie;
    while(i < n)
    {
        cin >> word;
        trie.insert(word);
        i++;
    }
    while(cin >> word)
        cout << (trie.search(word)? "Found" : "Not Found") << endl;
    return 0;

}

树状数组

树状数组
适用于获取数组前n项和,特别是数组元素经常改变的情况。

// 树状数组

#include <iostream>
#include <vector>

using namespace std;

class BIT
{
    public:
        BIT(const vector<int> &data)
        {
            init(data);
        }

        /*
        * 使用数组初始化树状数组,lowbit获取当前树状数组位置管辖的范围,然后这个范围内所有数累加到当前位置
        */
        void init(const vector<int> &data)
        {
            n  = data.size();
            tree = vector<int>(n+1, 0);
            for (int i = 1; i <= n; ++i)
                for (int j = i - lowbit(i) + 1; j <= i; ++j)
                    tree[i] += data[j];
        }

        /*
        * 使用lowbit获取开头到位置idx的和,比如`idx=7(111)`,则首先获取最低位管辖位置`i=7`的和,然后获取次低位`010`管辖位置`i=5,i=6`的和,最后获取`100`管辖位置`i=1,i=2,i=3,i=4`的和
        */
        int getSum(int idx)
        {
            int sum = 0;
            while(idx > 0)
            {
                sum += tree[idx];
                idx -= lowbit(idx);
            }
            return sum;
        }

        void update(int idx, int val)
        {
            while(idx <= n)
            {
                tree[idx] += val;
                idx += lowbit(idx);
            }
        }
    private:
            vector<int> tree;
            int n;
            int lowbit(int num)
            {
                return num & (-num);
            }

};

int main()
{
    vector<int> input;
    int num, n, i = 0;
    cin >> n;
    while (i++ < n)
    {
        cin >> num;
        input.push_back(num);
    }
    BIT b(input);
    cout << "getSum"<< endl;
    cin >> n;
    i = 0;
    while(i++ < n)
    {
        cin >> num;
        cout << b.getSum(num);
    }
    cout << "updataSum" << endl;
    int pos;
    cin >> pos >> num;
    b.update(pos, num);
    cout << "getSum"<< endl;
    cin >> n;
    i = 0;
    while(i++ < n)
    {
        cin >> num;
        cout << b.getSum(num);
    }
    return 0;
}