V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
lsmgeb89
V2EX  ›  算法

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

  •  
  •   lsmgeb89 · 2016-12-29 03:43:03 +08:00 · 8978 次点击
    这是一个创建于 2647 天前的主题,其中的信息可能已经有所发展或是发生改变。
    https://leetcode.com/problems/minimum-window-substring/

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

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

    对了,如果面试的时候,面到 hard 难度的题,一般可以做多久?如果是白板写这题的话,感觉还挺长的……
    16 条回复    2017-02-11 20:49:43 +08:00
    eb0c6551
        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 ''
    eb0c6551
        2
    eb0c6551  
       2016-12-29 04:19:34 +08:00
    还是贴图吧。

    https://ooo.0o0.ooo/2016/12/28/58641e4882616.png
    linboki
        3
    linboki  
       2016-12-29 04:25:17 +08:00 via Android
    这题我也花了近 2 个小时才解出来,不过是 O(m+n)解,最后对比网上的解法,似乎我的还更取巧一些,这也是动脑思考的乐趣所在。但我个人并不是为了面试刷 leetcode ,是为了训练思维 锻炼脑袋。感觉楼主动机太功利,容易浮躁,更不容易把题解出来
    Andiry
        4
    Andiry  
       2016-12-29 05:56:19 +08:00
    这题很难吗?一左一右两个指针不就行了,连 DP 都不用
    starvedcat
        5
    starvedcat  
       2016-12-29 06:13:28 +08:00   ❤️ 1
    我的方法是:直接看最高票的 discussion ,看懂了再写
    我觉得,如果是为了准备面试,重要的是学到了知识,而不是所谓“自己思考”的这个过程。直接看 discussion ,无非是从“看书”变成了“看网友”而已
    很多时候你“独立思考”了,花了好长时间终于写出来了。结果一看最高票答案,人家的做法又高效又简洁,你还是得重新写过。所谓“独立思考”,意义在哪里?
    肯定有人会说:“如果是自己想出来的话,会记得更牢!”——这个观点实在是站不住脚,回想一下上学时学习数学物理化学时的情形吧,难道因为那些知识是书本告诉你的(而不是“自己思考”得出的),就记不住了吗?
    SuperFashi
        6
    SuperFashi  
       2016-12-29 07:07:36 +08:00 via Android
    尝试过几次 LeetCode Hard ,毫无成就感。还不如去打 Topcoder 和 Codeforces 。
    lsmgeb89
        7
    lsmgeb89  
    OP
       2016-12-29 07:13:59 +08:00
    @Andiry
    @eb0c6551
    确实,看答案后,感觉是应该能想出来的。

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

    总想着会不会有情况扫不到。
    lsmgeb89
        8
    lsmgeb89  
    OP
       2016-12-29 07:55:47 +08:00 via Android
    @starvedcat 自己想出来的,理解会更加深刻
    jedihy
        9
    jedihy  
       2017-01-01 14:30:19 +08:00
    @starvedcat 题目不是基础知识,看懂的基本下次是写不出来的,得自己写练,一遍是不够的。
    jedihy
        10
    jedihy  
       2017-01-01 14:31:21 +08:00
    这一题其实算是面试中的简单题了
    lsmgeb89
        11
    lsmgeb89  
    OP
       2017-01-01 14:47:18 +08:00 via Android
    @jedihy 知道套路的话,是不难写。只是刚开始刷,有些套路不懂。
    lsmgeb89
        12
    lsmgeb89  
    OP
       2017-01-01 14:47:45 +08:00 via Android
    @jedihy 那什么题算难的?举个例子?
    jedihy
        13
    jedihy  
       2017-01-01 15:19:30 +08:00
    3 维及以上的 DP, patching array, scramble string 之类的
    题号 350 之后的 Hard 都比较难,都出自 FLAG 最难的 onsite 题。
    starvedcat
        14
    starvedcat  
       2017-01-01 16:25:55 +08:00
    @jedihy 无所谓,各人方法不同
    jiangfan
        15
    jiangfan  
       2017-02-10 19:47:49 +08:00
    我做 LeetCode 题差不多都是先自己在半小时内思考解法,超过半小时就看参考解法了。
    Jimrussell
        16
    Jimrussell  
       2017-02-11 20:49:43 +08:00
    同 5 楼
    从没考虑过竞赛方向(不然去 codeforces 之类了)
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   948 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 21:51 · PVG 05:51 · LAX 14:51 · JFK 17:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.