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

[fov6363]

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

[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.个人思路是: 将单链表看成一个个波,然后从这群波里画一条线,保证这条线离波上每个点最近,但这个想法不知道有没有科学性和可行性.

[LxExExl]

我直观感觉就是个贪心

对于 i 和 i+1 若递减 则不变
否则使 a[i]等于 a[i+1]

[ftdejo]

@LxExExl 直接贪心肯定不行。。考虑下递增情况

[vegito2002]

@LxExExl 那你怎么处理 1 2 3 呢？

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

没了。

我也同意这个应该是有一个可以简化问题的观察的， 但是不太好找； 而且真正面试的时候估计还是要证明自己的猜想的

[hJohn]

这是哪家公司的面试题目呀。。。有点难啊

[vegito2002]

我也想问一下 OP， 这个题目给的是多少时间？ 感觉 LC 的 hard 级别了有点，当然也有可能是我没想到点子上

[lcdtyph]

如果真是找直线的话就是最小二乘拟合嘛。

[UIXX]

补充详细。这道题挺直白的。
假设我们把每个节点看作是坐标的维度，楼主的题目就是已知一个四维点，求与已知点曼哈顿距离最小的点。但是这个点有约束条件。
假设我们建立一个二维坐标，横轴为节点顺序，竖轴为节点数值，还要求结果的那条链中任意两个相邻点的斜率在 0-负无穷之间。
综上所述...

[hjb912]

求平均数，再向上或向下取整

[vegito2002]

@UIXX 你这个思路好像整体是对的， 虽然我没有接触过这方面的编程实践， 不知道这种 constraint 搜索问题最后实现起来是什么难度， 尤其是维度增加的情况下。 不知道楼主面试的是什么职位， 如果面试的是算法工程师或者机器学习方面的， 还是有可能最后就是想要这个答案的。

如果是普通软件开发的面试， 感觉可能想要的是更加特性的一个解法。

[hjb912]

求中位数吧，算术平均数往往会受到异常大或异常小的数值影响

[txx]

这道题可以反着做，我从二分 delta，然后根据 delta 的结果去验证可行性...

[fml]

@vegito2002 #9 你这个图是用什么做的啊？

[feverzsj]

这难道不是面试官瞎诌的吗，要么就是他记错了

[Bryan0Z]

看起来像动态规划？

[vegito2002]

我始终认为找一条直线是一个坑, 我 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, 哪个小就是最好的纠正方式.



这个只是一个抛砖引玉, 暂时没有办法证明这个思路.

[vegito2002]

@fml notability 手画的

[binux]

@binux 继续我那个思路
第 n 位修改为 [a0...an] 的中位数。 （即所有位叠加 1，能得到的最小 △）
第 n-1 位修改为 [a0...a(n-1)] 的中位数 与 第 n 位中大的。（即 0...n-1 位叠加 1，能得到的最小 △）
第 n-2 位修改为 [a0...a(n-2)] 的中位数 与 第 n-1 位中大的。
以此类推

[Exceptionluo]

2->4->1->3
10->0>0>0

1->19->2
22->0->0

[binux]

@binux 发现对已排序无效，补一下
第 n 位时，从 n 向 0 找一个分割点，使得右边中位数总小于左边中位数，取右边中位数
第 n-1 位时，从 n-1 向 0 找一个分割点，使得右边中位数总小于左边中位数，取右边中位数
以此类推

[winglight2016]

没有复杂度要求的话，用线性回归吧