赞
踩
背景:为了方便九宫格手机用户发短信,希望在用户按键时,根据提供的字典(给出字符串和频数),给出各个阶段最有可能要打的单词。
题意: 首先给出的是字典,每个单词有一个出现频率。然后给出的是询问,每个询问有一个数字字符串,代表在手机上按了哪些键,以1结束。问按键的过程中最可能出现的单词分别是哪些。
思路:搞了很久.......一开始总想着以字母为各结点如何建树,询问......还是太年轻了。
以手机8个键作为字典树各节点,每个结点映射3-4对应的字母。每个结点存频率最高的串,询问的时候也可以方便的直接询问了。
还是太年轻了.........理解题意为具有相同前缀的串的频率是高的覆盖低的........其实是叠加...........一直没看出来。
题目是按照字典序升序给出字典的,所以可以把相同的前缀频率相加,这样只是插入一次了。
接下来就是基本字典树的写法了
- #include <cstdio>
- #include <cstring>
- #include <iostream>
- using namespace std;
-
- char book[] = {"22233344455566677778889999"}; //映射
- char str[1111][111];
- int cou[1111][111];
- struct trie {
- trie *next[12];
- char word[105];
- int num;
- trie() {
- num = 0;
- memset(next,0,sizeof(next));
- memset(word,0,sizeof(word));
- }
- }*root;
-
- void insert(char *key,int i) {
- trie *p = root;
- char tmp[105];
- int ind = 0;
- int j = 0;
- while(key[j]) {
- int t = book[key[j] - 'a'] - '0';
- tmp[ind++] = key[j];
- if(p->next[t] == NULL) {
- p->next[t] = new trie();
- }
- p = p->next[t];
- tmp[ind] = '\0';
- if(p->num < cou[i][j]) {
- p->num = cou[i][j];
- strcpy(p->word,tmp);
- }
- j++;
- }
- }
-
- void query(char *key) {
- trie *p = root;
- int flag = 0;
- while(*key) {
- int t = *key - '0';
- if(p->next[t] == NULL || flag) { //用flag标记一下,有可能会有前一个单词不存在,后面单词存在字典中,此时应该输出这个的
- printf("MANUALLY\n");
- key++;
- flag = 1;
- continue;
- }
- p = p->next[t];
- printf("%s\n",p->word);
- key ++;
- }
- }
-
- void free(trie *p) { //释放内存而已
- for(int i=0; i<=9; i++) {
- if(p->next[i] != NULL) free(p->next[i]);
- }
- delete p;
- }
-
- int main() {
- #ifndef ONLINE_JUDGE
- freopen("in.txt","r",stdin);
- freopen("D:\\hehe.txt","w",stdout);
- #endif
- int T,cnt;
- cin >> T;
- int casee = 1;
- while(T --) {
- root = new trie();
- int n,i;
- scanf("%d",&n);
- for(i=0; i<n; i++) {
- scanf("%s%d",str[i],&cnt);
- int len = strlen(str[i]);
- for(int j=0; j<len; j++) {
- cou[i][j] = cnt;
- }
- }
- for(i=1; i<n; i++) //相同前缀频率相加,堆在一起算
- for(int j=0; str[i][j] && str[i - 1][j]; j++) {
- if(str[i][j] == str[i-1][j]) {
- cou[i][j] += cou[i-1][j];
- cou[i-1][j] = 0;
- }
- else break;
- }
- for(i=0; i<n; i++) {
- insert(str[i],i);
- }
- printf("Scenario #%d:\n",casee ++);
- int m;
- scanf("%d",&m);
- char str1[111],st[111];
- for(i=0; i<m; i++) {
- scanf("%s",st);
- int len = strlen(st);
- strncpy(str1,st,len-1);
- str1[len-1] = '\0';
- query(str1);
- puts("");
- }
- puts("");
- free(root);
- }
- return 0;
- }

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。