首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  程序员

[面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 v 友有没有办法和思路?

  •  2
     
  •   fov6363 · 296 天前 · 8797 次点击
    这是一个创建于 296 天前的主题,其中的信息可能已经有所发展或是发生改变。

    一个单链表,每个节点里存储都是正整数,现在是无序的,可能会有重复数字,可以修改每个节点里的值,达到以下两个目标:

    [1] 单链表变为有序的,从大到小,可以大于等于.
    [2] 修改的△值最小.
    

    举例:

    1.单链表 2->4->1->3 ,可能改为 3->3->1->1 此时,此时链表有序,此时的△ = |(2 - 3)| + |(4 - 3)| + |(1 - 1)| + |(3 - 1)| = 4. 或者可以改为 2->2->2->2 此时的△ = |(2 - 2)| + |(4 - 2)| + |(1-2)| + |(3-2)| = 4.
    2.单链表 1->19->2 ,可能改为 2->2->2,△ = 1 + 17 + 0 = 18.
    

    补充;

    1.顺序影响因素很在,有的链表如果本身是顺序的,即不需要更改.
    2.暂没有正确答案,也没有问面试官解题思路.
    3.个人思路是: 将单链表看成一个个波,然后从这群波里画一条线,保证这条线离波上每个点最近,但这个想法不知道有没有科学性和可行性.
    
    第 1 条附言  ·  296 天前
    面试岗位是: 后端开发工程师,非算法方向的,之前面试的题都比较简单,都是业务相关的,只有最后一个题是算法,也就是这道,时间大概有 10 分钟吧(面试官出去再回来),很大可能面试官也不知道解法,但想考察一下思路 /想法这方面的能力-> 这是我的推断,因为看了评论后发现这题好难....我当时没问答案的原因是,以为百度一下就知道了...还以为是比较常见的算法题
    100 回复  |  直到 2018-05-06 05:30:38 +08:00
        1
    42joker   296 天前
    先找出原先链最大值 X 的节点 G,节点 G 左边节点所有值只能等于 X,然后再找右边的最大 S 值 C 的节点,重复上述步骤,直到最右节点
        2
    42joker   296 天前
    。。。我这个想法有问题,我在想想再回答
        3
    SYP   296 天前
    这么修改跟新建一个全新的链表有区别吗?
        4
    42joker   296 天前
    先找出原先链最大值 X 的节点 G,然后计算其左边所有值的平均值 A,将平均值 A 设为新单链的值,重复上述步骤?
        5
    enzo113   296 天前
    最优的结果不一定是一条线吧
    例如[8 7 8 2 2 2]
        6
    vegito2002   296 天前 via iPad
    @SYP 应该是没有区别, 关键是, 用哪一个全新的链表, 找到这个
        7
    42joker   296 天前
    @enzo113 单链表变为有序的,从大到小,可以大于等于
        8
    enzo113   296 天前
    @42joker #7 刚刚可能没表达清楚,我的意思是 [8 7 8 2 2 2] 变成 [8 8 8 2 2 2] 满足题目的要求,但是[ 8 8 8 2 2 2]并不是在一条线上,所以用类似直线拟合的思路可能会有点问题
        9
    vegito2002   296 天前
    找一个距离最近的线应该是不对的



    比如这里 ABC 这个波. 比较 l1, 中间这条线, 和 l2, 也就是 BE 所在的线;

    A 垂线交点假如是 F, 忘记标了;

    l1: 对 ABC 的距离之和是 AF + DE + CD = AF + CE, 修改成 l1 对应的 delta 也是这个值;

    l2: 对 ABC 的距离之和是: AF + DE + CD + DE = AF + CE + DE, 比 l1 大, 但是他的 delta 只有 CE, 比 l1 的小;
        10
    bravecarrot   296 天前 via iPhone
    很有意思 研究一下
        11
    fov6363   296 天前
    @42joker 这个想法我稍等写个 demo 尝试下,找两个例子试试再回你
        12
    binux   296 天前   ♥ 1
    这个单链表感觉完全没有用啊,用个数组不是一样的吗?

    从最小有效列表,[111...1] 开始
    将 0 至 n1 位 +1,使得 △ 变小。得到列表 [2221...1]
    将 0 至 n2 (n2<n1) 位 +1,使得 △ 变小。得到列表 [33..322..2111..1]
    直到 △ 不再变小。
        13
    UIXX   296 天前
    建立竖向为节点数值增长的方向,横向为节点顺序增长方向,曼哈顿距离最小且结果中任意两点之间的斜率在 0 到-45 度之间,条件应该够的
        14
    vegito2002   296 天前
    @binux 如果一次只+1 的话, 这个算法的复杂度太高了, 只要让数组里面的数字之间的差值足够大, 最后的复杂度估计按照面试的标准很难接受.
        15
    UIXX   296 天前
    修改一下,是相邻两点之间
        16
    binux   296 天前
    @vegito2002 然后再贪心什么的优化呗。我只是给个思路
        17
    fingerprint   296 天前
    提供个思路,暂时还没有验证。先遍历把链表里相邻且数字相同的合并,这样就得到一系列有权值(权值为合并的个数)的数。然后再利用加权线性回归来得到一条直线。这条直线的参数如果不为整数,那就应该上下分别取整计算下,最多就是算 4 种参数组合,然后应该就可以得出最优解了。
        18
    42joker   296 天前
    @enzo113 我觉得应该是题主表达得不好吧,如果是要一条直线的话斜率就是固定的了。。我想应该不是这样
        19
    forthdim   296 天前
    @vegito2002 你这个论证有问题吧,l2 的△应该是 AF+DE+CE,比 l1 大,楼主的基本思路没问题,上面 @UIXX 的答案也说了,就是找一个 k<0 的直线使得所有点到直线距离最短
        20
    vegito2002   296 天前 via iPad
    @forthdim l2 的 delta 只要把 C 拉到 E 就行了, 只有 CE 这么大,AB 不需要改变;
        21
    LxExExl   296 天前 via iPhone
    我直观感觉就是个贪心

    对于 i 和 i+1 若递减 则不变
    否则使 a[i]等于 a[i+1]
        22
    ftdejo   296 天前
    @LxExExl 直接贪心肯定不行。。考虑下递增情况
        23
    vegito2002   296 天前 via iPad
    @LxExExl 那你怎么处理 1 2 3 呢?

    i = 0, 变成 2 2 3
    i = 1, 变成 2 3 3

    没了。

    我也同意这个应该是有一个可以简化问题的观察的, 但是不太好找; 而且真正面试的时候估计还是要证明自己的猜想的
        24
    hJohn   296 天前
    这是哪家公司的面试题目呀。。。有点难啊
        25
    vegito2002   296 天前 via iPad
    我也想问一下 OP, 这个题目给的是多少时间? 感觉 LC 的 hard 级别了有点,当然也有可能是我没想到点子上
        26
    lcdtyph   296 天前
    如果真是找直线的话就是最小二乘拟合嘛。
        27
    UIXX   296 天前
    补充详细。这道题挺直白的。
    假设我们把每个节点看作是坐标的维度,楼主的题目就是已知一个四维点,求与已知点曼哈顿距离最小的点。但是这个点有约束条件。
    假设我们建立一个二维坐标,横轴为节点顺序,竖轴为节点数值,还要求结果的那条链中任意两个相邻点的斜率在 0-负无穷之间。
    综上所述...
        28
    hjb912   296 天前
    求平均数,再向上或向下取整
        29
    vegito2002   296 天前 via iPad
    @UIXX 你这个思路好像整体是对的, 虽然我没有接触过这方面的编程实践, 不知道这种 constraint 搜索问题最后实现起来是什么难度, 尤其是维度增加的情况下。 不知道楼主面试的是什么职位, 如果面试的是算法工程师或者机器学习方面的, 还是有可能最后就是想要这个答案的。

    如果是普通软件开发的面试, 感觉可能想要的是更加特性的一个解法。
        30
    hjb912   296 天前
    求中位数吧,算术平均数往往会受到异常大或异常小的数值影响
        31
    txx   296 天前
    这道题可以反着做,我从二分 delta,然后根据 delta 的结果去验证可行性...
        32
    fml   296 天前
    @vegito2002 #9 你这个图是用什么做的啊?
        33
    feverzsj   296 天前
    这难道不是面试官瞎诌的吗,要么就是他记错了
        34
    Bryan0Z   296 天前 via Android
    看起来像动态规划?
        35
    vegito2002   296 天前
    我始终认为找一条直线是一个坑, 我 9L 的论证已经证明.
    而且 UIXX 的思路整体也是正确的. 按照他的思路, 在三维, 也就是链表长度是 3 的情况下, 三维空间里面可以脑补一下, 最近的这个点完全不一定在 x = y && y = z 这条直线上, 也就是认为最优的新链表里面所有的节点都相等不太合理.

    i 代表 index, [i]代表这个 index 位置的节点.
    我有一个尝试性的思路: 对于任意两个元素, 如果 i < j, 但是!([i] >= [j]), 那么定义(i, j)为一个反转.

    我有一个尝试性的思路:
    第一遍:
    对于每一个 i, 找到 i 左边的最小值, 记录为 min[i]
    记录 delta[i] = max (nums[i] - min[i], 0)
    然后 sum delta[i] for i in range (N), 得到一个 delta1; 这一个对应于把所有的 i 作为右端点参与的反转进行纠正, 纠正方式是将 nums[i[向下拉;

    第二遍:
    对于每一个 i, 找到 i 右边的最大值, 记录为 max[i].
    delta[i] = max (max[i] - nums[i], 0)
    delta2 = sum delta[i] for i in range (N). 这个对应于把所有 i 作为左端点参与的反转进行纠正, 纠正的方式是将 nums[i]向上拉.

    比较两个 delta, 哪个小就是最好的纠正方式.



    这个只是一个抛砖引玉, 暂时没有办法证明这个思路.
        36
    vegito2002   296 天前
    @fml notability 手画的
        37
    binux   296 天前
    @binux 继续我那个思路
    第 n 位修改为 [a0...an] 的中位数。 (即所有位叠加 1,能得到的最小 △)
    第 n-1 位修改为 [a0...a(n-1)] 的中位数 与 第 n 位中大的。(即 0...n-1 位叠加 1,能得到的最小 △)
    第 n-2 位修改为 [a0...a(n-2)] 的中位数 与 第 n-1 位中大的。
    以此类推
        38
    Exceptionluo   296 天前
    2->4->1->3
    10->0>0>0

    1->19->2
    22->0->0
        39
    binux   296 天前
    @binux 发现对已排序无效,补一下
    第 n 位时,从 n 向 0 找一个分割点,使得右边中位数总小于左边中位数,取右边中位数
    第 n-1 位时,从 n-1 向 0 找一个分割点,使得右边中位数总小于左边中位数,取右边中位数
    以此类推
        40
    winglight2016   296 天前
    没有复杂度要求的话,用线性回归吧
        41
    batman2010   296 天前
    (试着答一下)

    链表不是考点,可以直接看成数组。

    先求数组的中位数,记为 m。

    从右向左遍历
    1. 如果递增,则继续;
    2. 如果遇到非递增的元素(记为 a ),就把它右边的所有数组元素向中位数 m 对齐,并累加 delta 值。如果 a 小于 m,a 也向 m 对齐。把 a 作为新的遍历起点。
    不断重复。
        42
    qwsqwa   296 天前   ♥ 9
    DP:
    原链表为 a ;
    dp[n][m],表示前 n 个数最小值大于等于 m 时需要的最小△值。
    '''
    def f(a):
    ma = max(a)
    dp = [[0] * (ma + 1) + [float("inf")] for _ in range(len(a) + 1)]

    for i in range(1, len(a) + 1):
    for j in range(ma, -1, -1):
    dp[i][j] = min(dp[i][j + 1], dp[i - 1][j] + abs(a[i - 1] - j))

    return dp[len(a)][0]
    '''
    时间复杂度 O(n*m)
        43
    contmonad   296 天前 via iPhone
    你确定是最小化 delta 而不是修改次数?
        44
    lance6716276   296 天前 via Android
    有点像保序回归,只不过保序回归是用的欧式距离而不是曼哈顿距离
        45
    qwsqwa   296 天前
    @contmonad 修改次数就是最长递减子序列。
        46
    Xs0ul   296 天前
    感觉很像是带约束的优化问题
        47
    cover   296 天前
    这种类型第一感觉是 dp,空间复杂度换时间复杂度
        48
    fov6363   296 天前
    @contmonad 确定是求 delta 最优
        49
    vegito2002   296 天前 via iPad
    @qwsqwa 膜拜一下, 这个思路可以说是很犀利了
        50
    cover   296 天前
    @qwsqwa 这个太大了吧。。如果 m 很大的情况下基本不可行
        51
    vegito2002   296 天前 via iPad
    @qwsqwa 这里的第二维是 max value, 因为步长是 1, 可不可以这样, 第二维长度直接定义为链表本身的长度,也就是说只循环链表本身包含的这些个离散值, 而不是一次-1 这样的搜索?
        52
    cover   296 天前
    @qwsqwa 我有一个大胆的想法,会不会结果变化的数一定是在 这原先给的 x 个数中间,也就是不会出现中间数这种做法,例如 4 2 4 最后变化完一定是 4,2 里面选,那么你这个复杂度就会变成 o ( n*n )。。。 但是我没想通这个点是否正确
        53
    cover   296 天前
    @cover 如果是这样的话,那这个复杂度就可以接受了
        54
    qwsqwa   296 天前
    @vegito2002 感觉可行,可以优化到 O(n*min(m,n))。
        55
    jorneyr   296 天前
    同一个链表有序,难道还有多种有序序列?
        56
    jrient   296 天前   ♥ 1
    我说下我的想法把
    1.找到最大点 a[x]和最小点 a[y]
    2.分别找到离 x 和 y 最近的边缘 m 和 n
    3.分别取 x-m 和 y-n 的值的平均值((a[x]+...+a[m])/(|x-m|)) p q
    4.对比|a[x]-p| 和 |a[y]-q| 选出大的一个。
    5.假设|a[x]-p| 大;将新单链表 x-m 的值设为 p
    6.在不改变键值的情况下,将 a 中 x-m 区域的内容 unset 掉
    7.使用新的 a 链表,回到第 1 步

    个人认为,这个问题的关键在于如何找到新链表的最大值并定义新链表是顺序还是倒序排列
        57
    Lpl   296 天前   ♥ 2
    这个问题可以用数学推导的方法来做,时间复杂度是 O(n)
    ![]( )
        58
    rrfeng   296 天前 via Android
    @Lpl 怎么确定的 a 范围?
        59
    Lpl   296 天前
    @rrfeng 第一个数如果是最大数,a 肯定要是 0。如果不是最大数;如果不是最大数,那么 a 肯定 < 0
        60
    Veigar   296 天前
    这题目主要的作用是让你做不出来,压价用的。。并不是想让你真的做出来 你做出来就坏了
        61
    zjsxwc   296 天前 via Android
    取平均数吧,delta 的值就知道了
        62
    lizz666   296 天前
    我是来学习的
        63
    renhairui   296 天前
    来学习~^_^
        64
    rrfeng   296 天前 via Android
    @rrfeng 所以把范围压缩到了前两个数之差?
        65
    JerryV2   296 天前
    @lcdtyph 26
    赞同
        66
    cuebyte   296 天前
    看樓主的 append,覺得是給錯題了。
        67
    Stay4Life   296 天前 via Android
    从左到右读取,递减不变,发现变大就从前面到当前元素都取这一段的平均值,这样子?算法弱鸡
        68
    polymerdg   296 天前
    <img src="https://i.loli.net/2018/03/28/5abb5244ec800.png" alt=" bg2.jpg"/>
    求最小阴影面积
        69
    binux   296 天前
    来个 O(nlogn) 复杂度的算法



    和 42L 结果一致
        71
    bigwang   296 天前
    各位想太多了,这只是一个 10 分钟的题
    链表排序,二分法不适合,△值最小 ,排序结果是确定的,哪就要求排序结果稳定,答案就是 冒泡排序
        72
    xxlong   296 天前
    @Lpl 不太懂,但是我想知道结果是直线的怎么能证明自己的结果是最优呢?答案是直线的话问题太大了吧?
        73
    xxlong   296 天前
    @fov6363 画直线的想法不太对吧,最后的结果怎么能确定是直线呢?
        74
    contmonad   296 天前 via iPhone   ♥ 1
    @qwsqwa 是的,我以为面试一般考常规题。刚才查了下这道的原题出自 https://stackoverflow.com/a/33865020
        75
    fanfx   296 天前
    感觉求平均值就可以了,例如第一道题:2+4+1+3=10 平均数是 2.5 由于第一个数是 2, 可以保持不变结论就是 2 2 2 2,三角也是等于 4.第二题。1+19+2=22 平均数 7.*** ,跟第位数字相比 还是 7 最接近,第一位数字为 7 二位数字为 7 三位数字可以维持 2 不变。结果三角也是等于 18. 不知道怎么样。
        76
    xxlong   296 天前
    @binux 结果有问题吧。。
        77
    Lpl   296 天前
    @xxlong 是有问题,还是用 DP 吧
        78
    fyxtc   296 天前
    楼主最后进了吗。。。。
        79
    utanbo   296 天前
    这就是有约束的极值问题吧。
    求 min( sum(pow((x[i]-y[i]),2)) )然后约束 st. 对于任意 i 有 y[i]>= y[i+1]
    这个二次的多项式里,x[i]相当于是参数,y[i]是变量。i 从 1 到 n。
        80
    Parallel   296 天前 via iPhone   ♥ 6
    USACO 2008 February 金组原题 / POJ 3666
    动态规划求解。
    此帖终结。
        81
    CosimoZi   296 天前
    这个对吗?
    def c(l):
    if len(l) == 2:
    if l[-2] >= l[-1]:
    return 0
    return l[-1] - l[-2]
    if l[-2] >= l[-1]:
    return c(l[:-1])
    return min(c(l[:-1]) + l[-1] - l[-2], c(l[:-1]) + sum(l[-1] - i for i in l[:-1] if i < l[-1]))
        82
    flowarmor   296 天前
    动态规划。
        83
    xrlin   295 天前
    第一眼就想到动态规划,但还是没想到具体思路。
        84
    mickeyandkaka   295 天前
    https://blog.csdn.net/guhaiteng/article/details/52739135

    原题,这种题目其实很多的。
        85
    ksdx   295 天前
    这个应该就是求解,数轴上到任意 n 个点的距离和最短吧,如果不限制是正整数的话,那么这个点(对应具体数值)在中间位置就可以(左右点数量相等,要考虑 n 为奇偶数,要考虑 n 个数有重复……)。差不多了
        86
    ksdx   295 天前
    也可以用物理的方式理解,假设数轴是在一个平面上,每个点都打个洞,用线挂一个等重小球,穿过这个洞。然后到 n 个点距离和最短就等于是把这 n 条线打结在一个点上,然后由于小球重力,会在某个位置平衡,这是小球总的势能降到最低(水往低处流,能量最小~)。势能最小也意味着在平面上的线长度和最小,平面下的线长度和最长。由于是数轴,所以只要考虑左右平衡,左右小球数量相等,那么就会达到平衡,考虑下奇偶数。(类似三角形费马点)
    这个也可以扩展到,平面、空间里。
        87
    vegito2002   295 天前
    一觉醒来真的是...楼主你面的到底是什么公司啊, POJ 的题目都出.
        88
    nomoon   295 天前
    最长非降子序列?
        89
    Paddington   295 天前
    好像发现这道题没有很简单。
        90
    imn1   295 天前
    为啥我第一时间想到的是方差?
        91
    binux   295 天前
    @xxlong



    并没有问题,是可以 AC 的,是算法是可以证明的。
    基本思路就是从 An...An-1, An...An-1, An...An-2 找中位数最小的,然后二分为两个数组。
    可以证明左边的 B0...Bm 一定大于 Bm...Bn 。

    极端情况下(已排序数组),需要反复计算 A0...An, A0...An-1, A0..An-2 的中位数,不过这是可以优化的。复杂度应该是 O(nlogn)
        92
    kaiak   295 天前
    应该是用动态规划+中位数吧
        93
    binux   295 天前
    @binux 优化一下查找最小中位数,这样时间就正常了


        94
    glasslion   295 天前
    @binux ==! USACO Gold 的题目
        95
    binux   295 天前
    @glasslion #94 http://poj.org/problem?id=3666

    Source
    USACO 2008 February Gold
        96
    hjb912   295 天前
    看到最小中位数我都笑了。把所有数据取出来求一个中位数就够了,为什么要反复求中位数?
    [中位数] 是对变量中心位置的一种度量,这概念属于描述统计学数值方法,楼主你面的公司应该跟数据分析有关哦我猜:)
        97
    xxlong   295 天前
    @binux 厉害啊 没学过算法 不过解法是真的优美
        98
    Alan1994   295 天前
    这道题实际上就是弱条件下的保序回归。保序回归要求的是欧式距离最短,在欧式距离最短的情况下曼哈顿距离肯定也是最短的。
        99
    Alan1994   295 天前
    附上:
    ① 维基百科: https://en.wikipedia.org/wiki/Isotonic_regression
    ② 硕士论文《保序回归的算法及应用》: https://wenku.baidu.com/view/ade7744eee06eff9aef8079f.html
        100
    chaoxu   257 天前
    的确可以 model 为 isotonic regression, 并且可以 model 成一个 min-cost flow on a series-parallel graph.
    然后就能 O(n log n)获得解法了.
    算是这里面问题的简化版本.
    http://chaoxuprime.com/posts/2015-01-27-bounded-regression-on-data-streams.html
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2222 人在线   最高记录 4236   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 24ms · UTC 12:24 · PVG 20:24 · LAX 04:24 · JFK 07:24
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1