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

[42joker]

先找出原先链最大值 X 的节点 G，节点 G 左边节点所有值只能等于 X，然后再找右边的最大 S 值 C 的节点，重复上述步骤，直到最右节点

[42joker]

。。。我这个想法有问题，我在想想再回答

[SYP]

这么修改跟新建一个全新的链表有区别吗？

[42joker]

先找出原先链最大值 X 的节点 G，然后计算其左边所有值的平均值 A，将平均值 A 设为新单链的值，重复上述步骤？

[enzo113]

最优的结果不一定是一条线吧
例如[8 7 8 2 2 2]

[vegito2002]

@SYP 应该是没有区别， 关键是， 用哪一个全新的链表， 找到这个

[42joker]

@enzo113 单链表变为有序的,从大到小,可以大于等于

[enzo113]

@42joker #7 刚刚可能没表达清楚，我的意思是 [8 7 8 2 2 2] 变成 [8 8 8 2 2 2] 满足题目的要求，但是[ 8 8 8 2 2 2]并不是在一条线上，所以用类似直线拟合的思路可能会有点问题

[vegito2002]

找一个距离最近的线应该是不对的



比如这里 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 的小;

[bravecarrot]

很有意思 研究一下

[fov6363]

@42joker 这个想法我稍等写个 demo 尝试下,找两个例子试试再回你

[binux]

这个单链表感觉完全没有用啊，用个数组不是一样的吗？

从最小有效列表，[111...1] 开始
将 0 至 n1 位 +1，使得 △ 变小。得到列表 [2221...1]
将 0 至 n2 (n2<n1) 位 +1，使得 △ 变小。得到列表 [33..322..2111..1]
直到 △ 不再变小。

[UIXX]

建立竖向为节点数值增长的方向，横向为节点顺序增长方向，曼哈顿距离最小且结果中任意两点之间的斜率在 0 到-45 度之间，条件应该够的

[vegito2002]

@binux 如果一次只+1 的话, 这个算法的复杂度太高了, 只要让数组里面的数字之间的差值足够大, 最后的复杂度估计按照面试的标准很难接受.

[UIXX]

修改一下，是相邻两点之间

[binux]

@vegito2002 然后再贪心什么的优化呗。我只是给个思路

[fingerprint]

提供个思路，暂时还没有验证。先遍历把链表里相邻且数字相同的合并，这样就得到一系列有权值（权值为合并的个数）的数。然后再利用加权线性回归来得到一条直线。这条直线的参数如果不为整数，那就应该上下分别取整计算下，最多就是算 4 种参数组合，然后应该就可以得出最优解了。

[42joker]

@enzo113 我觉得应该是题主表达得不好吧，如果是要一条直线的话斜率就是固定的了。。我想应该不是这样

[forthdim]

@vegito2002 你这个论证有问题吧，l2 的△应该是 AF+DE+CE,比 l1 大，楼主的基本思路没问题，上面 @UIXX 的答案也说了，就是找一个 k<0 的直线使得所有点到直线距离最短

[vegito2002]

@forthdim l2 的 delta 只要把 C 拉到 E 就行了， 只有 CE 这么大，AB 不需要改变；