1
eb0c6551 2016-12-29 04:15:26 +08:00
这种技巧性很强的题目并不值得花很多时间自己想。以及熟练掌握技巧后,应该是可以很快地白板写出来的,我写的:
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 '' |
2
eb0c6551 2016-12-29 04:19:34 +08:00
还是贴图吧。
https://ooo.0o0.ooo/2016/12/28/58641e4882616.png |
3
linboki 2016-12-29 04:25:17 +08:00 via Android
这题我也花了近 2 个小时才解出来,不过是 O(m+n)解,最后对比网上的解法,似乎我的还更取巧一些,这也是动脑思考的乐趣所在。但我个人并不是为了面试刷 leetcode ,是为了训练思维 锻炼脑袋。感觉楼主动机太功利,容易浮躁,更不容易把题解出来
|
4
Andiry 2016-12-29 05:56:19 +08:00
这题很难吗?一左一右两个指针不就行了,连 DP 都不用
|
5
starvedcat 2016-12-29 06:13:28 +08:00 1
我的方法是:直接看最高票的 discussion ,看懂了再写
我觉得,如果是为了准备面试,重要的是学到了知识,而不是所谓“自己思考”的这个过程。直接看 discussion ,无非是从“看书”变成了“看网友”而已 很多时候你“独立思考”了,花了好长时间终于写出来了。结果一看最高票答案,人家的做法又高效又简洁,你还是得重新写过。所谓“独立思考”,意义在哪里? 肯定有人会说:“如果是自己想出来的话,会记得更牢!”——这个观点实在是站不住脚,回想一下上学时学习数学物理化学时的情形吧,难道因为那些知识是书本告诉你的(而不是“自己思考”得出的),就记不住了吗? |
6
SuperFashi 2016-12-29 07:07:36 +08:00 via Android
尝试过几次 LeetCode Hard ,毫无成就感。还不如去打 Topcoder 和 Codeforces 。
|
7
lsmgeb89 OP |
8
lsmgeb89 OP @starvedcat 自己想出来的,理解会更加深刻
|
9
jedihy 2017-01-01 14:30:19 +08:00
@starvedcat 题目不是基础知识,看懂的基本下次是写不出来的,得自己写练,一遍是不够的。
|
10
jedihy 2017-01-01 14:31:21 +08:00
这一题其实算是面试中的简单题了
|
13
jedihy 2017-01-01 15:19:30 +08:00
3 维及以上的 DP, patching array, scramble string 之类的
题号 350 之后的 Hard 都比较难,都出自 FLAG 最难的 onsite 题。 |
14
starvedcat 2017-01-01 16:25:55 +08:00
@jedihy 无所谓,各人方法不同
|
15
jiangfan 2017-02-10 19:47:49 +08:00
我做 LeetCode 题差不多都是先自己在半小时内思考解法,超过半小时就看参考解法了。
|
16
Jimrussell 2017-02-11 20:49:43 +08:00
同 5 楼
从没考虑过竞赛方向(不然去 codeforces 之类了) |