（更新offer）胡子大叔刷题直播

刷了LeetCode: Wildcard Matching。

这也是条硬骨头，好在……曾经刷过。翻出了15年的笔记，基本就是复刻了一下。用的双指针，python beat 100%。
也可以DP，DP的递推式也很unstandable。但是DP的时间不是很理想，就没复刻了。

所以作笔记真的很重要啊。因为你刷题的当时，记忆是最清新准确的，具体到要不要+1，哪个if-else是针对哪个corner case都记得清清楚楚，花几分钟写一下，以后的你会感谢自己的！

好了，wildcard matching刷完，正式标志着Explore-Facebook页面下Backtracking的题也刷完了。接着刷Explore-Google下面的Recursion吧，只有四道，今天应该可以搞定

天公不作美。on-call遇到incident，从中午搞到现在，饭都没有吃上。不过今天还是会努力把这四道题写完的！

刷了Implement Trie (Prefix Tree)。因为Explore-Google-Resursion下面最高频的那道Word Square需要用到Trie，索性以此为契机，复习了一下Trie

Trie就是，记不清的时候觉得它很神秘，熟练了以后发现就那么回事，不要自己吓自己！

刷了Word Squares。几乎就是为trie而存在的题目。所以就没用hashtable，而用了trie来存prefix。

trie本身的implement很长，看起来码量很大。其实抛开之后就是很套路的递归 + 回溯问题。permutation，还有找岛屿之类的都见惯了

刷了Valid Word Square，和上一道相关的题目，是easy，但长度不等的case也不是特别intuitive了。今天说的4道recursion只完成了一道，做了两道别的题，明天继续吧

看楼主刷题分析，感觉楼主很牛逼。

love1point 发表于 2018-11-12 03:22
看楼主刷题分析，感觉楼主很牛逼。

您捧，您捧。都是做不出来就看别人的解法，没有多少独创的东西

刷了Android Unlock Patterns。大概n年之前就看到了这道题，现在才动手做。题目没有解释清楚，比如图4从9到2其实不算经过了6。这样就简单了很多，很多，很多。


回溯 + 递归的套路已经不能再套路了，唯一的难点就是检查下一个点是否有效。leetcode官方解给出的各种if-else is too smart. 其实我很不喜欢这种聪明的小技巧（比如用相加为奇数来检查相邻和knight move），因为这不是intuitive的东西，也不是现场能想出来的东西。即使你侥幸背下来了，也会让面试官觉得很突兀。

我自己写了个判据可以不用分任何情况，各种情况统一判断。要用还是用general method。

顺便说一句，反对论坛上那种为了缩短行数而把可读性搞得巨差的代码，这是面试，是给人读的。想以短为追求去参加code golf比赛好么

刷了Word Search II，也是一道hard。用trie剪枝，而且找到一个word之后从trie里移出这个词再次剪枝。饶是如此，时间成本也还是很大。用hash来存prefix已经不可能了

again，因为implement了trie的insert + delete，使得辅助代码变得很长。但实际上不是很难，属于那种明白了思路就很好码的题（相较于那种你当时能调出来，过后怎么也想不起来的那种“技巧”题。真到面试那天，还是请愿遇到这种麻烦一点的套路题，而不是需要特别巧解的题