Hihocode Trieツリーコード
3739 ワード
今日ACはHiHocodeの2番目の問題をつけて、hihocodeはテストのヒントを与えないため、難易度はleetcodeが少し高いと感じて、比較的に気持ち悪いです.
でもACが出てきたときは本当に嬉しかったです.くだらないことは言わないで、本題に入ります.
私は華やかな分割線です!
==============================================================
hihocodeは善意にヒントを提供し、3つに分かれていますが、ポイントは2つです.
1つは、ツリーをどのように構築するかです.
二つ目は、前置単語をどのように検索するかです.
Trieツリーはエッジで文字を保存していますが、ブロガーは最初はノードが保存していると勘違いしていて、少し頭がかかりました.
また,hihocodeは挿入しながら統計する必要があることを示唆し,我々の構造体はこのように現れた.
注意しなければならないのはhihocode定義の重複する単語を2つ計算して、ブロガーは最初に重複する単語を削除して、そこでWAは長い間です.
単語を挿入:
検索しながら集計しているので、実はtrieツリーに完全に合わなくてもいいし、単語のそのノードがマークしなくても結果に影響しない
単語/接頭辞の検索数:
次にすべてのコードを貼り付けます
すべてのコードには、重複する単語を減算する関数が含まれていますが、使用されません.
でもACが出てきたときは本当に嬉しかったです.くだらないことは言わないで、本題に入ります.
私は華やかな分割線です!
==============================================================
hihocodeは善意にヒントを提供し、3つに分かれていますが、ポイントは2つです.
1つは、ツリーをどのように構築するかです.
二つ目は、前置単語をどのように検索するかです.
Trieツリーはエッジで文字を保存していますが、ブロガーは最初はノードが保存していると勘違いしていて、少し頭がかかりました.
また,hihocodeは挿入しながら統計する必要があることを示唆し,我々の構造体はこのように現れた.
注意しなければならないのはhihocode定義の重複する単語を2つ計算して、ブロガーは最初に重複する単語を削除して、そこでWAは長い間です.
struct Node
{
bool isWord;
Node *child[Max];//save edge
int L[Max];//save count
Node()
{
isWord = false;
for (int i = 0; i < Max; i++)
{
child[i] = NULL;
}
for (int i = 0; i < Max; i++)
{
L[i] = 0;
}
}
~Node()
{
for (int i = 0; i < Max; i++)
{
delete child[i];
}
}
};
単語を挿入:
void Insert(string word)
{
Node *tempRoot = root;
for (int i = 0; i < word.length(); i++)
{
tempRoot->L[word[i]-'a']++;
if (tempRoot->child[word[i]-'a'] != NULL)
{
tempRoot = tempRoot->child[word[i]-'a'];
}
else
{
Node *newNode = new Node();
tempRoot->child[word[i]-'a'] = newNode;
tempRoot = tempRoot->child[word[i]-'a'];
}
if (i == word.length() - 1)
{
if (tempRoot->isWord == false)
{
tempRoot->isWord = true;
}
}
}
}
検索しながら集計しているので、実はtrieツリーに完全に合わなくてもいいし、単語のそのノードがマークしなくても結果に影響しない
単語/接頭辞の検索数:
int find(string word)
{
Node *tempRoot = root;
for (int i = 0; i < word.length(); i++)
{
if (tempRoot->child[word[i]-'a'] == NULL)return 0;
else
{
if (i == word.length() - 1) return tempRoot->L[word[i]-'a'];
tempRoot = tempRoot->child[word[i]-'a'];
}
}
}
次にすべてのコードを貼り付けます
すべてのコードには、重複する単語を減算する関数が含まれていますが、使用されません.
#include
#include
using namespace std;
const int Max = 26;
struct Node
{
bool isWord;
Node *child[Max];//save edge
int L[Max];//save count
Node()
{
isWord = false;
for (int i = 0; i < Max; i++)
{
child[i] = NULL;
}
for (int i = 0; i < Max; i++)
{
L[i] = 0;
}
}
~Node()
{
for (int i = 0; i < Max; i++)
{
delete child[i];
}
}
};
Node * root = new Node();
void minusDuplicate(string word)
{
Node *tempRoot = root;
for (int i = 0; i < word.length(); i++)
{
tempRoot->L[word[i]-'a']--;
tempRoot = tempRoot->child[word[i]-'a'];
}
}
void Insert(string word)
{
Node *tempRoot = root;
for (int i = 0; i < word.length(); i++)
{
tempRoot->L[word[i]-'a']++;
if (tempRoot->child[word[i]-'a'] != NULL)
{
tempRoot = tempRoot->child[word[i]-'a'];
}
else
{
Node *newNode = new Node();
tempRoot->child[word[i]-'a'] = newNode;
tempRoot = tempRoot->child[word[i]-'a'];
}
if (i == word.length() - 1)
{
if (tempRoot->isWord == false)
{
tempRoot->isWord = true;
}
}
}
}
int find(string word)
{
Node *tempRoot = root;
for (int i = 0; i < word.length(); i++)
{
if (tempRoot->child[word[i]-'a'] == NULL)return 0;
else
{
if (i == word.length() - 1) return tempRoot->L[word[i]-'a'];
tempRoot = tempRoot->child[word[i]-'a'];
}
}
}
int main()
{
int count = 0;
cin >> count;
string insertStr;
for (int i = count; i > 0; i--)
{
cin >> insertStr;
Insert(insertStr);
}
cin >> count;
for (int i = count; i > 0; i--)
{
cin >> insertStr;
cout<