“你知道貧窮的本質(zhì)是什么嗎？貧窮的本質(zhì)就是那一堆UP拿著“貧窮的本質(zhì)”收割了一波又一波流量，變得不再貧窮，而像我這樣的觀眾還覺得它說的很對，覺得看完我就能擺脫貧窮了?！?/p>

by self

昨天的每日一題是字典樹。前些天有一道題的標(biāo)準(zhǔn)解法是字典樹，所以看到這一題就想到了。

抽象一下就是，在字典樹里尋找前后綴都滿足的字符串。

很自然的建了一個字典樹，但是查詢的時候發(fā)現(xiàn)了問題：

1.樹只能自上而下遍歷，而且必須有下一個字符才能往下遍歷。也就是說，只有前綴無法遍歷到結(jié)尾，也就無法確定是哪一個字串了。

而且，標(biāo)準(zhǔn)字典樹也沒辦法判定后綴。

2.不知道當(dāng)前節(jié)點(diǎn)屬于哪一個字串，而題目要求了返回索引。這其實(shí)很矛盾，字典樹本身就是為了把重復(fù)的部分消除掉而建立的數(shù)據(jù)結(jié)構(gòu)，把原來的字符串?dāng)?shù)組變成字典樹，是一定會丟掉原來的索引的，因為字符串重復(fù)的部分被提取出來，變成公共的部分了。

一開始我的想法很扯，我給每一個節(jié)點(diǎn)都增加了一個parent指向它的父節(jié)點(diǎn)，在插入的時候記錄每一個最底部的節(jié)點(diǎn)，這個節(jié)點(diǎn)同時保存字串的長度和索引。

這樣，我就可以自下而上的同時判斷前綴后綴，也得到索引了。

但問題是：一個子節(jié)點(diǎn)是有多個父節(jié)點(diǎn)的。

于是，我把父節(jié)點(diǎn)改成了list，每一個子節(jié)點(diǎn)保存它所有的父節(jié)點(diǎn)，這樣就可以從下往上遍歷所有情況了。

最后失敗了，代碼變得極度復(fù)雜需要計算前后綴對應(yīng)哪一個位置，需要遍歷所有底部節(jié)點(diǎn)的同時遍歷它們的父節(jié)點(diǎn)……

這里得到的教訓(xùn)是：

不要一條路走到黑。

“天才崇尚簡潔，愚人崇尚復(fù)雜……如果你丟給它們一堆它們看不懂的東西，它們就會奉你為神”

by?Terry A.Davis(1969-2018)

真相一定是簡潔的，不要試著做加法，改變思路換個角度才是正確的思考方式。

簡而言之，思考時廣度優(yōu)先。

我跳出原來的想法，后退了一步。我在每一個節(jié)點(diǎn)里增加了一個list，用于存儲這個節(jié)點(diǎn)可能被包含在哪一個字串里(可能的索引。

對于前綴，遍歷到前綴長度為止，把最后那個節(jié)點(diǎn)的list拿出來，然后直接用字串?dāng)?shù)組里的元素去比較后綴。

就是這樣簡單的想法，算是無奈地退了一步。

提交以后發(fā)現(xiàn)，復(fù)雜度還可以，速度超過一半的人，內(nèi)存占用超7成。

開始我認(rèn)為字典樹就是要抹去原本字符串的信息，就是要遍歷到結(jié)尾才能確定一個字串，因為這是它的本質(zhì)。所以即使開始就想到了用list存索引，也一直沒這么做……

結(jié)論：

本質(zhì)是不存在的，或者只存在于那些所謂教授，或者知識區(qū)UP或神棍的嘴里。

或者說：

過程很重要，但過程服務(wù)于結(jié)果，為了過程追求過程是無意義的。

而且，我至今其實(shí)沒有真正努力過一次。我想像蔚藍(lán)的Madeline一樣，試試自己能不能做成一件事。

如果把算法變成吃飯喝水一樣的事，我也能成為天才，能成為別人眼中有天賦的人嗎？

天才，天賦。這不重要。下一個目標(biāo)是下一次開始的周賽做完前兩題，下下個目標(biāo)是偶爾四題，然后是穩(wěn)定AK，最后是進(jìn)一次前10……

客觀來看，目前的總刷題是30多，但可以保證每一題都理解了，哪怕一年以后再做還是可以很快想出來。

人腦學(xué)習(xí)或認(rèn)知的原理是從相似的事物中提取出抽象或者說特征。順應(yīng)這個原理，加大刷題量想不出來直接看題解，這樣可行嗎？

是不行的，那樣就是記憶而不是學(xué)習(xí)了。人腦比AI高等的地方就在這里，人腦擁有推理能力，AI只能判斷是橘子還是蘋果，人腦卻能推出結(jié)論：都是水果。

換句話說，人腦可以進(jìn)行更高層次的抽象，但這不是本能，是一種需要去訓(xùn)練習(xí)慣的能力。

因此目前的路線是對的，那么順著這個路線真的可以進(jìn)前10嗎？即使真的沒有天賦還是每天努力刷題，思考，除了吃飯喝水都刷題……

絲毫不自信的說，是可以的。人會無意識夸大一些事，把事實(shí)當(dāng)作謙虛，把人當(dāng)神，被崇拜淹沒理智，被跟風(fēng)磨平清醒的認(rèn)知……

我又開始了，少扯這些沒用的，多思考一些難以理解的問題吧。