字典树

“你知道贫穷的本质是什么吗？贫穷的本质就是那一堆UP拿着“贫穷的本质”收割了一波又一波流量，变得不再贫穷，而像我这样的观众还觉得它说的很对，觉得看完我就能摆脱贫穷了。”

by self

昨天的每日一题是字典树。前些天有一道题的标准解法是字典树，所以看到这一题就想到了。

抽象一下就是，在字典树里寻找前后缀都满足的字符串。

很自然的建了一个字典树，但是查询的时候发现了问题：

1.树只能自上而下遍历，而且必须有下一个字符才能往下遍历。也就是说，只有前缀无法遍历到结尾，也就无法确定是哪一个字串了。

而且，标准字典树也没办法判定后缀。

2.不知道当前节点属于哪一个字串，而题目要求了返回索引。这其实很矛盾，字典树本身就是为了把重复的部分消除掉而建立的数据结构，把原来的字符串数组变成字典树，是一定会丢掉原来的索引的，因为字符串重复的部分被提取出来，变成公共的部分了。

一开始我的想法很扯，我给每一个节点都增加了一个parent指向它的父节点，在插入的时候记录每一个最底部的节点，这个节点同时保存字串的长度和索引。

这样，我就可以自下而上的同时判断前缀后缀，也得到索引了。

但问题是：一个子节点是有多个父节点的。

于是，我把父节点改成了list，每一个子节点保存它所有的父节点，这样就可以从下往上遍历所有情况了。

最后失败了，代码变得极度复杂需要计算前后缀对应哪一个位置，需要遍历所有底部节点的同时遍历它们的父节点……

这里得到的教训是：

不要一条路走到黑。

“天才崇尚简洁，愚人崇尚复杂……如果你丢给它们一堆它们看不懂的东西，它们就会奉你为神”

by Terry A.Davis(1969-2018)

真相一定是简洁的，不要试着做加法，改变思路换个角度才是正确的思考方式。

简而言之，思考时广度优先。

我跳出原来的想法，后退了一步。我在每一个节点里增加了一个list，用于存储这个节点可能被包含在哪一个字串里(可能的索引。

对于前缀，遍历到前缀长度为止，把最后那个节点的list拿出来，然后直接用字串数组里的元素去比较后缀。

就是这样简单的想法，算是无奈地退了一步。

提交以后发现，复杂度还可以，速度超过一半的人，内存占用超7成。

开始我认为字典树就是要抹去原本字符串的信息，就是要遍历到结尾才能确定一个字串，因为这是它的本质。所以即使开始就想到了用list存索引，也一直没这么做……

结论：

本质是不存在的，或者只存在于那些所谓教授，或者知识区UP或神棍的嘴里。

或者说：

过程很重要，但过程服务于结果，为了过程追求过程是无意义的。

而且，我至今其实没有真正努力过一次。我想像蔚蓝的Madeline一样，试试自己能不能做成一件事。

如果把算法变成吃饭喝水一样的事，我也能成为天才，能成为别人眼中有天赋的人吗？

天才，天赋。这不重要。下一个目标是下一次开始的周赛做完前两题，下下个目标是偶尔四题，然后是稳定AK，最后是进一次前10……

客观来看，目前的总刷题是30多，但可以保证每一题都理解了，哪怕一年以后再做还是可以很快想出来。

人脑学习或认知的原理是从相似的事物中提取出抽象或者说特征。顺应这个原理，加大刷题量想不出来直接看题解，这样可行吗？

是不行的，那样就是记忆而不是学习了。人脑比AI高等的地方就在这里，人脑拥有推理能力，AI只能判断是橘子还是苹果，人脑却能推出结论：都是水果。

换句话说，人脑可以进行更高层次的抽象，但这不是本能，是一种需要去训练习惯的能力。

因此目前的路线是对的，那么顺着这个路线真的可以进前10吗？即使真的没有天赋还是每天努力刷题，思考，除了吃饭喝水都刷题……

丝毫不自信的说，是可以的。人会无意识夸大一些事，把事实当作谦虚，把人当神，被崇拜淹没理智，被跟风磨平清醒的认知……

我又开始了，少扯这些没用的，多思考一些难以理解的问题吧。