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

[CosimoZi]

这个对吗?
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]))

[flowarmor]

动态规划。

[xrlin]

第一眼就想到动态规划，但还是没想到具体思路。

[mickeyandkaka]

https://blog.csdn.net/guhaiteng/article/details/52739135

原题，这种题目其实很多的。

[ksdx]

这个应该就是求解，数轴上到任意 n 个点的距离和最短吧，如果不限制是正整数的话，那么这个点（对应具体数值）在中间位置就可以（左右点数量相等，要考虑 n 为奇偶数，要考虑 n 个数有重复……）。差不多了

[ksdx]

也可以用物理的方式理解，假设数轴是在一个平面上，每个点都打个洞，用线挂一个等重小球，穿过这个洞。然后到 n 个点距离和最短就等于是把这 n 条线打结在一个点上，然后由于小球重力，会在某个位置平衡，这是小球总的势能降到最低（水往低处流，能量最小~）。势能最小也意味着在平面上的线长度和最小，平面下的线长度和最长。由于是数轴，所以只要考虑左右平衡，左右小球数量相等，那么就会达到平衡，考虑下奇偶数。（类似三角形费马点）
这个也可以扩展到，平面、空间里。

[vegito2002]

一觉醒来真的是...楼主你面的到底是什么公司啊, POJ 的题目都出.

[nomoon]

最长非降子序列？

[Paddington]

好像发现这道题没有很简单。

[imn1]

为啥我第一时间想到的是方差？

[binux]

@xxlong

https://gist.github.com/binux/1fc354bfd95836e92f19e3250527b2c9

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

极端情况下（已排序数组），需要反复计算 A0...An, A0...An-1, A0..An-2 的中位数，不过这是可以优化的。复杂度应该是 O(nlogn)

[kaiak]

应该是用动态规划+中位数吧

[binux]

@binux 优化一下查找最小中位数，这样时间就正常了

https://gist.github.com/binux/f1a2eee0f71c3233d1d2da6d71b85ff2

[glasslion]

@binux ==! USACO Gold 的题目

[binux]

@glasslion #94 http://poj.org/problem?id=3666

Source
USACO 2008 February Gold

[hjb912]

看到最小中位数我都笑了。把所有数据取出来求一个中位数就够了，为什么要反复求中位数？
[中位数] 是对变量中心位置的一种度量，这概念属于描述统计学数值方法，楼主你面的公司应该跟数据分析有关哦我猜：）

[xxlong]

@binux 厉害啊 没学过算法 不过解法是真的优美

[Alan1994]

这道题实际上就是弱条件下的保序回归。保序回归要求的是欧式距离最短，在欧式距离最短的情况下曼哈顿距离肯定也是最短的。

[Alan1994]

附上：
① 维基百科： https://en.wikipedia.org/wiki/Isotonic_regression
② 硕士论文《保序回归的算法及应用》： https://wenku.baidu.com/view/ade7744eee06eff9aef8079f.html

[chaoxu]

的确可以 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