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

说几个 leetcode 上看似简单却又非常困难的问题

  •  1
     
  •   Goldilocks · 2020-11-10 05:13:18 +08:00 · 3333 次点击
    这是一个创建于 1234 天前的主题,其中的信息可能已经有所发展或是发生改变。
    1. Merge two sorted array

    https://leetcode.com/problems/merge-sorted-array/

    Q1: 算法复杂度的下界是多少?如何算出来的?

    Q2: 常规两个指针线性的往前走谁都会写,但是如何 binary search 加速它?aka. binary search merge

    1. Shuffle the Array

    https://leetcode.com/problems/shuffle-the-array

    如何 inplace 的在线性的时间复杂度完成它?如何证明你的算法是对的?

    这个题其实是在考察你对抽象代数的理解。因为这个所谓的 shuffle 就是 permutation 。permutation group 可以被分解成 orbits 。然后你就只需要一个 orbit 、一个 orbit 的去处理就行了。但是如何找出这些 orbits 呢?能不能同时处理多个 orbits 呢?

    1. Running Sum of 1d Array https://leetcode.com/problems/running-sum-of-1d-array/

    看起来很简单是吧? 如果是浮点数怎么办?如何利用 binary tree 最小化计算误差?

    1. find the median number of an array

    《算法导论》花了很大的篇幅去讲这个问题,没有认真学过的人肯定是不懂的,尤其是那个最坏情况为线性时间的选择算法,为什么《算法导论》上是每 5 个一组但是 TAOCP 上的描述是 7 个一组?除了这些 textbook 算法外,你还有什么 idea ?比如如何用概率论和统计学知识开发一个期望线性的随机化算法?

    一味的刷题是没有用的,对于找到这些 easy 问题的答案没有帮助。

    同时这也回答了另一个问题:面试的时候怎么判断面试者是不是速成的? 很简单,认真学过算法的科班学生,多少会对这些问题有些 sense 。而速成的只能靠刷题,刷不出这些 idea 。他甚至不知道 binary search merge 的存在。但是如果他但凡看过 MIT 、普林斯顿或任何一个名校的算法公开课,他都会知道 binary merge/median find 不是那么的简单的问题。

    16 条回复    2021-06-20 19:46:35 +08:00
    Girlphobia
        1
    Girlphobia  
       2020-11-10 05:21:41 +08:00   ❤️ 1
    坚定了我有空一定要把垫显示器的《算法导论》拿出来仔细看一遍的决心。
    daozhihun
        2
    daozhihun  
       2020-11-10 08:43:30 +08:00
    如果你只是想要知道别人是否认真学过算法,直接出个题目考网络流算法、A*搜索剪枝不是更好吗?
    我觉得面试的目的是考察对方的思维能力,而不是单纯地判断他是否看过哪些公开课什么的。
    lights
        3
    lights  
       2020-11-10 09:08:03 +08:00 via iPhone
    这是要造火箭还是造无人汽车啊
    GtDzx
        4
    GtDzx  
       2020-11-10 09:17:19 +08:00
    binary search merge 是啥? 怎么加速的? 还真没听说过...
    SingeeKing
        5
    SingeeKing  
       2020-11-10 09:22:29 +08:00 via iPhone
    @GtDzx 简单说就是楼主列举的第一题的 O(logN) 解法
    GtDzx
        6
    GtDzx  
       2020-11-10 22:59:31 +08:00
    @SingeeKing 这题至少要把 2 个数组遍历一遍吧,还能 O(logN)? 讲讲怎么做?
    levelworm
        7
    levelworm  
       2020-11-12 23:48:17 +08:00
    @Girlphobia 当初看了几页就放弃了,感觉还是红色那本舒服一点。不过我觉得还是从项目中寻找问题比较好。。。否则看完也忘记了。
    Sevenskey
        8
    Sevenskey  
       2020-12-06 19:45:22 +08:00
    @SingeeKing 呃,这题最优解是 o(m+n)啦,没有 log 的解法
    Goldilocks
        9
    Goldilocks  
    OP
       2020-12-07 03:15:22 +08:00
    @Sevenskey 你能证明它至少需要 o(m+n)次比较吗?不能啊。
    Sevenskey
        10
    Sevenskey  
       2020-12-18 23:21:49 +08:00
    @Goldilocks 。。那你能证明它在某种算法下最多只需要 log(m+n)的比较吗
    e583409
        11
    e583409  
       2021-01-03 09:04:49 +08:00
    我理解 刷题的目很多人没有搞懂 为了数量 而不是质量 为了刷题而刷题
    这个是我的答案 https://github.com/xrfinbupt/leetcode_java
    Goldilocks
        12
    Goldilocks  
    OP
       2021-01-03 13:16:25 +08:00 via Android
    二路归并,其实是在问,如果你把 m 个排好序的数字插入到另外 n 个排好序的数组中,那么那 m 个数的 position 有多少种可能性?
    然后再回过头来,基于比较的排序,为什么下界是 nlogn ?
    把这两个问题的答案结合起来,就可以得知二路归并的算法复杂度下界。
    Goldilocks
        13
    Goldilocks  
    OP
       2021-01-03 13:17:34 +08:00 via Android
    举个例子,当 m 等于 1,那么显然共有 n+1 种可能性。用 log ( n+1 )次比较就能解决问题
    Sevenskey
        14
    Sevenskey  
       2021-01-10 02:42:05 +08:00
    @Goldilocks 啊这,那你这复杂度不是 log(n+m)而是 mlogn 啊。。另外大 o 记号是表示上界的
    Goldilocks
        15
    Goldilocks  
    OP
       2021-01-10 07:08:25 +08:00
    @Sevenskey 我自始自终就没说过 log(n+m)啊。而且也不是 mlogn 。我甚至连大 O 都没有提过。对于这样的简单问题,大 O 太粗糙了。大 O 是上界,所以要看谁能找到更精确的上界中的下界。
    e583409
        16
    e583409  
       2021-06-20 19:46:35 +08:00
    @e583409 不知不觉 用半年 刷了 178 道题
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   4812 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 77ms · UTC 09:56 · PVG 17:56 · LAX 02:56 · JFK 05:56
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.