这个题的题解区就没一简单一点的指针题解?(大概是瞎了)
记得有一篇题解有个dalao作者放了几个静态模拟的trie树结果最后放了个动态的跑路了.....
(放个板子就跑路真的不好)
所以本蒟蒻来一发1470ms & 63.52MB的——
(PHP的数组和STL的玄学做法真叫人质壁分离)
回到正题。
->
而不是小数点p
指向a
,那么*p
相当于ap=new type_T();
(因为trie是经典的用空间换时间的数据结构,动态指针实现的trie可以用更少的时间最大限度地换回一部分空间。
指针是结构体实现自引用结构的基础。
——清华大学出版社《c语言XX(第五版)》
trie树的基本操作是插入,查找,删除操作。这是重点.jpg
插入只需要两种操作方式:
str[i]
的指针,挪到指向str[i]
的指针的位置。str[i]
的指针(默认是NULL),那么先将需要的指针分配一个空间,再执行操作1。str[i]
的指针,挪到指向str[i]
的指针的位置。str[i]
的指针,直接返回说找不到字符串。这个题特殊之处在于要多维护一个bool vst
,表示是否已经念过这个字符串。
当遍历完了字符串以后,如果vst==true
,就返回说已经念过了。
否则就vst=true
,然后返回说没问题。
因为用了指针,所以其实也比较简单。
只需要递归到字符串的最后一个元素,然后回溯的时候删除指针即可。
或者开一个指针存一下父亲节点的地址,逆序递推也是可以的。
(本题目没有删除的相关操作)
然后说一下本题思路。
数据结构方面:
每一个trie指针节点存26个节点(表示下一个字符),一个vst(表示是否已经念过这个人名)。
算法方面:
先建一个插入n个字符串的trie,表示原先的人名。
然后查找m次,每次先判断出是否正确,然后会判断出是否已经重复,最后返回没毛病。(我用了unsigned char剩下了一点点空间......)
然后说一下getline毒瘤:是因为字符串最后都有一个换行,getline读入的时候会读进去,所以输出会占用一个空行,所以要么抹掉(substr),要么cin,要么就直接字符数组scanf读入。
最后放上代码:
C++ Code(太丑了,放到剪贴板里)
最后同 Wow_Goodjob dalao:炉石是个非常好的游戏(逃
原文:https://www.cnblogs.com/jelly123/p/10543308.html