一题多解需要记住每一种解法还是只记住最优解？

比如柱形图中最大矩形面积这道题，有几种解法，用分治法复杂度是nlgn，用stack是n，需要两种解法都记住么？面试里面会不会遇到一些面试官要求把稍差一些的分治法也写一下的情况？

这题完全不会d&c，但确实是直觉应该这样写。

但是你说找左边跟右边的第一个比自己小的高度这个也不算难吧。主要是找第一个比自己小的用stack挺常见的， 或者用ufds， 平均处理时间应该是alpha，还是比stack好一点，应用相对多一点点。

补充内容 (2018-5-22 11:20):
至于哪种方法， 其实不能说背答案吧。你应该熟悉自己最喜欢的方法。如果实在记不住， 那还是背一个容易记得答案比较好。。

肥宅快乐水 发表于 2018-5-22 11:17
这题完全不会d&c，但确实是直觉应该这样写。

但是你说找左边跟右边的第一个比自己小的高度这个也不算难 ...

谢谢了。

倒不是为了背答案，只不过是想知道刷题的时候一道题是不是需要多种方法刷，所有的方法都要熟悉能秒，比如subset这道题，求一个数组所有的subset，面试官会不会要求递归循环两种方法都要会写？最好能有面试中遇到相似情况的讲讲经验。。。

slowloris 发表于 2018-5-22 11:33
谢谢了。

倒不是为了背答案，只不过是想知道刷题的时候一道题是不是需要多种方法刷，所有的方法都要熟 ...

嗯。。你说的也有道理。。

这道题我以前只会iterative， 后来学会了dfs就不iterative了。。 当然这两种应该都会才对。

如果说是某一种 ad hoc的题， 那估计不会问什么太多奇怪的方法。

除非你说这个 n方也能做， nlgn也能做， 那恐怕两个都要聊一下，速度快在哪，空间差在哪，为什么快，数据结构差别，如果size非常大怎么办这一类的。

假如说有几种很明显的做法可以解，那你肯定是都得聊的。。也看面试官我感觉

我最近做的题都是在说怎么快怎么来， 比如sample size小于20的时候推荐用complete search，因为一定能做出来。但是这种答案似乎在面试中站不住脚。。(⊙ˍ⊙)

必须是多种。一上来bug free给最优解，很多面试官不喜欢这样。

我感觉理解才是最重要的。记解法难以长久。

coco125 发表于 2018-5-23 23:55
我感觉理解才是最重要的。记解法难以长久。

关键是很多方法平时根本用不到，不刻意去记很快就忘了一些细节，像求substring的算法KMP，BM，AC这些我只能记个大概，突然叫我一遍写出来肯定有bug。

最好是理解分析多解