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

[batman2010]

（试着答一下）

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

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

从右向左遍历
1. 如果递增，则继续；
2. 如果遇到非递增的元素（记为 a ），就把它右边的所有数组元素向中位数 m 对齐，并累加 delta 值。如果 a 小于 m，a 也向 m 对齐。把 a 作为新的遍历起点。
不断重复。

[qwsqwa]

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)

[contmonad]

你确定是最小化 delta 而不是修改次数？

[lance6716276]

有点像保序回归，只不过保序回归是用的欧式距离而不是曼哈顿距离

[qwsqwa]

@contmonad 修改次数就是最长递减子序列。

[Xs0ul]

感觉很像是带约束的优化问题

[cover]

这种类型第一感觉是 dp，空间复杂度换时间复杂度

[fov6363]

@contmonad 确定是求 delta 最优

[vegito2002]

@qwsqwa 膜拜一下， 这个思路可以说是很犀利了

[cover]

@qwsqwa 这个太大了吧。。如果 m 很大的情况下基本不可行

[vegito2002]

@qwsqwa 这里的第二维是 max value， 因为步长是 1， 可不可以这样， 第二维长度直接定义为链表本身的长度，也就是说只循环链表本身包含的这些个离散值， 而不是一次-1 这样的搜索？

[cover]

@qwsqwa 我有一个大胆的想法，会不会结果变化的数一定是在 这原先给的 x 个数中间，也就是不会出现中间数这种做法，例如 4 2 4 最后变化完一定是 4，2 里面选，那么你这个复杂度就会变成 o （ n*n ）。。。 但是我没想通这个点是否正确

[cover]

@cover 如果是这样的话，那这个复杂度就可以接受了

[qwsqwa]

@vegito2002 感觉可行，可以优化到 O(n*min(m,n))。

[jorneyr]

同一个链表有序，难道还有多种有序序列？

[jrient]

我说下我的想法把
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 步

个人认为，这个问题的关键在于如何找到新链表的最大值并定义新链表是顺序还是倒序排列

[Lpl]

这个问题可以用数学推导的方法来做，时间复杂度是 O(n)

[rrfeng]

@Lpl 怎么确定的 a 范围？

[Lpl]

@rrfeng 第一个数如果是最大数，a 肯定要是 0。如果不是最大数；如果不是最大数，那么 a 肯定 < 0

[Veigar]

这题目主要的作用是让你做不出来，压价用的。。并不是想让你真的做出来 你做出来就坏了