[面试][算法] 昨天面试碰到了一个算法题,比较有难度,放上来看各位 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.个人思路是: 将单链表看成一个个波,然后从这群波里画一条线,保证这条线离波上每个点最近,但这个想法不知道有没有科学性和可行性.

[zjsxwc]

取平均数吧，delta 的值就知道了

[lizz666]

我是来学习的

[renhairui]

来学习~^_^

[rrfeng]

@rrfeng 所以把范围压缩到了前两个数之差？

[JerryV2]

@lcdtyph 26
赞同

[cuebyte]

看樓主的 append，覺得是給錯題了。

[Stay4Life]

从左到右读取，递减不变，发现变大就从前面到当前元素都取这一段的平均值，这样子？算法弱鸡

[polymerdg]

<img src="https://i.loli.net/2018/03/28/5abb5244ec800.png" alt=" bg2.jpg"/>
求最小阴影面积

[binux]

来个 O(nlogn) 复杂度的算法

https://gist.github.com/binux/1891d88a3a7e47775f490fc1e32b8fa7

和 42L 结果一致

[polymerdg]

https://i.loli.net/2018/03/28/5abb52de043ab.jpg

[bigwang]

各位想太多了，这只是一个 10 分钟的题
链表排序，二分法不适合，△值最小 ，排序结果是确定的，哪就要求排序结果稳定，答案就是 冒泡排序

[xxlong]

@Lpl 不太懂，但是我想知道结果是直线的怎么能证明自己的结果是最优呢？答案是直线的话问题太大了吧？

[xxlong]

@fov6363 画直线的想法不太对吧，最后的结果怎么能确定是直线呢？

[contmonad]

@qwsqwa 是的，我以为面试一般考常规题。刚才查了下这道的原题出自 https://stackoverflow.com/a/33865020

[fanfx]

感觉求平均值就可以了，例如第一道题：2+4+1+3=10 平均数是 2.5 由于第一个数是 2， 可以保持不变结论就是 2 2 2 2，三角也是等于 4.第二题。1+19+2=22 平均数 7.*** ，跟第位数字相比 还是 7 最接近，第一位数字为 7 二位数字为 7 三位数字可以维持 2 不变。结果三角也是等于 18. 不知道怎么样。

[xxlong]

@binux 结果有问题吧。。

[Lpl]

@xxlong 是有问题，还是用 DP 吧

[fyxtc]

楼主最后进了吗。。。。

[utanbo]

这就是有约束的极值问题吧。
求 min( sum(pow((x[i]-y[i]),2)) )然后约束 st. 对于任意 i 有 y[i]>= y[i+1]
这个二次的多项式里，x[i]相当于是参数，y[i]是变量。i 从 1 到 n。

[Parallel]

USACO 2008 February 金组原题 / POJ 3666
动态规划求解。
此帖终结。