大家做 LeetCode hard 题一般想多久才放弃？

[lsmgeb89]

https://leetcode.com/problems/minimum-window-substring/

例如这题想了快两小时都没想出 O(n) 的解。又不甘心看答案。

因为感觉面试的时候，除非是常规套路题，如果现在想不出来，面试的时候肯定想不出来。

对了，如果面试的时候，面到 hard 难度的题，一般可以做多久？如果是白板写这题的话，感觉还挺长的……

[eb0c6551]

这种技巧性很强的题目并不值得花很多时间自己想。以及熟练掌握技巧后，应该是可以很快地白板写出来的，我写的：

import collections

class Solution(object):
def minWindow(self, s, t):
"""
:type s: str
:type t: str
:rtype: str
"""
missing = len(t)
need = collections.defaultdict(lambda: 0)
best = ' '*(len(s)+1)

for c in t:
need[c] += 1

slow = 0
for fast in range(len(s)):
need[s[fast]] -= 1

missing -= need[s[fast]] >= 0

while missing == 0:
best = min(best, s[slow:fast+1], key=lambda x: len(x))
need[s[slow]] += 1
missing += need[s[slow]] > 0
slow += 1

return best if len(best) < len(s) + 1 else ''

[eb0c6551]

还是贴图吧。

https://ooo.0o0.ooo/2016/12/28/58641e4882616.png

[linboki]

这题我也花了近 2 个小时才解出来，不过是 O(m+n)解，最后对比网上的解法，似乎我的还更取巧一些，这也是动脑思考的乐趣所在。但我个人并不是为了面试刷 leetcode ，是为了训练思维 锻炼脑袋。感觉楼主动机太功利，容易浮躁，更不容易把题解出来

[Andiry]

这题很难吗？一左一右两个指针不就行了，连 DP 都不用

[starvedcat]

我的方法是：直接看最高票的 discussion ，看懂了再写
我觉得，如果是为了准备面试，重要的是学到了知识，而不是所谓“自己思考”的这个过程。直接看 discussion ，无非是从“看书”变成了“看网友”而已
很多时候你“独立思考”了，花了好长时间终于写出来了。结果一看最高票答案，人家的做法又高效又简洁，你还是得重新写过。所谓“独立思考”，意义在哪里？
肯定有人会说：“如果是自己想出来的话，会记得更牢！”——这个观点实在是站不住脚，回想一下上学时学习数学物理化学时的情形吧，难道因为那些知识是书本告诉你的（而不是“自己思考”得出的），就记不住了吗？

[SuperFashi]

尝试过几次 LeetCode Hard ，毫无成就感。还不如去打 Topcoder 和 Codeforces 。

[lsmgeb89]

@Andiry
@eb0c6551
确实，看答案后，感觉是应该能想出来的。

当初也考虑过两个指针的方法，只是在想移动指针的时机的时候，想复杂了。

总想着会不会有情况扫不到。

[lsmgeb89]

@starvedcat 自己想出来的，理解会更加深刻

[jedihy]

@starvedcat 题目不是基础知识，看懂的基本下次是写不出来的，得自己写练，一遍是不够的。

[jedihy]

这一题其实算是面试中的简单题了

[lsmgeb89]

@jedihy 知道套路的话，是不难写。只是刚开始刷，有些套路不懂。

[lsmgeb89]

@jedihy 那什么题算难的？举个例子？

[jedihy]

3 维及以上的 DP, patching array, scramble string 之类的
题号 350 之后的 Hard 都比较难，都出自 FLAG 最难的 onsite 题。

[starvedcat]

@jedihy 无所谓，各人方法不同

[jiangfan]

我做 LeetCode 题差不多都是先自己在半小时内思考解法，超过半小时就看参考解法了。

[Jimrussell]

同 5 楼
从没考虑过竞赛方向（不然去 codeforces 之类了）