Celery's Blog

0%

LeetCode-Day56

发表于 Valine：

Trie

tire数是用一棵树来表示一个字符串，从跟节点，到某个字符串结束的节点，经过的路径，就是这个字符串，这样子我们可以比较高效的查找，在tire数内是否有一个字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int tire[1000005][30];
int sum[1000005];
int tot = 1;    //此处可以理解为层次，就是想当于，每一层数组表示一个指针

void insert(string str) {
    int root = 1;
    int len = str.size();
    for(int i = 0; i < len; i++) {
        int idx = str[i] - 'a';
        if(tire[root][idx] == 0) {
            tire[root][idx] = ++tot;
        }
        root = tire[root][idx];
        sum[root]++;
     }
}

int query(string str) {
    int len = str.size();
    int root = 1;
    for(int i = 0; i < len; i++) {
        int idx = str[i] - 'a';
        if(tire[root][idx] == 0) {
            return 0;
        }
        root = tire[root][idx];
    }
    // 返回有多少字符串符合该前缀str
    return sum[root];
}

洛谷P2922 Secret Message

题目大意：给定 N 个字符串组成的字典，有 M 个询问，每次给定一个字符串，求字典中有多少个单词为给定字符串的前缀或前缀是给定的字符串。

这个前缀长度必须等于暗号和那条信息长度的较小者．

思路：

对于这道题不仅需要记录每个字符串的终止信息，还需要记录每一个节点被途径的次数。

在遍历一条输入暗号的时候，若还没有到结尾，则应该加上当前长度暗号串的个数，如果到结尾，则应该加上经过该末尾的字符串的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 500005;
const int MAXN = 500005;
int trie[MAXM][3];
int num[MAXN];
int book[MAXN];
int sum[MAXN];
int m, n;
int tot = 1;

void insert(int cnt) {
    int root = 1;
    for(int i = 0; i < cnt; i++) {
        int idx = num[i];
        if(trie[root][idx] == 0) {
            trie[root][idx] = ++tot;
        }
        root = trie[root][idx];
        sum[root]++;
    }
    book[root]++;
}

int query(int cnt) {
    int root = 1, ret = 0;
    for(int i = 0; i < cnt; i++) {
        int idx = num[i];
        if(trie[root][idx] == 0) {
            return ret;
        }
        root = trie[root][idx];
        ret += book[root];
    }
    return ret + sum[root] - book[root];
}

int main() {
    memset(book, 0, sizeof(book));
    memset(sum, 0, sizeof(sum));
    scanf("%d%d", &m, &n);
    for(int i = 0; i < m; i++) {
        int cnt;
        scanf("%d", &cnt);
        for(int j = 0; j < cnt; j++) {
            scanf("%d", &num[j]);
        }
        insert(cnt);
    }
    for(int i = 0; i < n; i++) {
        int cnt;
        scanf("%d", &cnt);
        for(int j = 0; j < cnt; j++) {
            scanf("%d", &num[j]);
        }
        printf("%d\n", query(cnt));
    }
}

hdu 1671 phone list

题目大意：给出多组数据，每组多个电话号码（数字串）。判断是否造成打错电话：2个号码123 123456 前3个数字相同，并且构成了一个完整的号码串即可打出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
int trie[MAXN][12];
bool book[MAXN];
int tot = 1;

bool insert(string str) {
    int len = str.size();
    int root = 1;
    for(int i = 0; i < len; i++) {
        int idx = str[i] - '0';
        if(trie[root][idx] == 0) {
            trie[root][idx] = ++tot;
        }
        root = trie[root][idx];
        if(book[root]) {
            return false;
        }
    }
    book[root] = true;
    // 需要遍历一遍，因为有些情况可能是91111 911这种情况下，911是不能被察觉到的，因为，中间第二个1没有被标注为true，因此，需要遍历一遍
    for(int i = 0; i < 10; i++) {
        if(trie[root][i] != 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int num;
        string str;
        bool flag = true;
        memset(book, 0, sizeof(book));
        memset(trie, 0, sizeof(trie));
        tot = 1;
        scanf("%d", &num);
        for(int j = 0; j < num; j++) {
            cin >> str;
            if(flag && !insert(str)) {
                flag = false;
            }
        }
        if(flag) {
            printf("YES\n");
        } else {
            printf("NO\n");
        }
    }
}

hdu 3460 Ancient Printer

题意：
我有一台古老的打印机，这个打印机只能支持三个操作
1.在缓存区最后面加入一个小写字母
2.将缓存区的字符全部打印到一张卡片上
3.将缓存区最后面字符删除
现在我想打印一些单词，问最少要操作几次才能将打印出所有的单词卡片

思路：

画个图就能理解是 节点数 * 2（键入的加删除的） + 单词个数（print次数） - maxLen（最长的单词不需要删除）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 500000;
int trie[MAXN][30];
bool book[MAXN];
int tot = 1;
int maxLen = 0;
int dup = 0;

void Insert(string str) {
    int len = str.size();
    maxLen = max(maxLen, len);
    int root = 1;
    for(int i = 0; i < len; i++) {
        int idx = str[i] - 'a';
        if(trie[root][idx] == 0) {
            trie[root][idx] = ++tot;
        }
        root = trie[root][idx];
    }
    return ;
}

int main() {
    int n;
    while(scanf("%d", &n) != EOF) {
        memset(trie, 0, sizeof(trie));
        tot = 1;
        maxLen = 0, dup = 0;
        string str;
        for(int i = 0; i < n; i++) {
            cin >> str;
            Insert(str);
        }
        printf("%d\n", n + 2 * (tot - 1) - maxLen);    
    }
    
}