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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2418 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

第 1 条附言 · 2018-03-28 13:50:09 +08:00

面试岗位是: 后端开发工程师,非算法方向的,之前面试的题都比较简单,都是业务相关的,只有最后一个题是算法,也就是这道,时间大概有 10 分钟吧(面试官出去再回来),很大可能面试官也不知道解法,但想考察一下思路 /想法这方面的能力-> 这是我的推断,因为看了评论后发现这题好难....我当时没问答案的原因是,以为百度一下就知道了...还以为是比较常见的算法题

单链表

链表

面试

思路

100 条回复 • 2018-05-06 05:30:38 +08:00

42joker

2018-03-28 11:06:36 +08:00

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

42joker

2018-03-28 11:08:12 +08:00

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

SYP

2018-03-28 11:11:30 +08:00

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

42joker

2018-03-28 11:11:36 +08:00

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

enzo113

2018-03-28 11:16:30 +08:00

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

vegito2002

2018-03-28 11:17:25 +08:00 via iPad

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

42joker

2018-03-28 11:23:53 +08:00

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

enzo113

2018-03-28 11:27:03 +08:00

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

vegito2002

2018-03-28 11:27:15 +08:00

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

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

2018-03-28 11:27:31 +08:00 via iPhone

很有意思研究一下

fov6363

2018-03-28 11:27:38 +08:00

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

binux

2018-03-28 11:29:05 +08:00

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

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

UIXX

2018-03-28 11:30:21 +08:00

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

vegito2002

2018-03-28 11:31:40 +08:00

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

UIXX

2018-03-28 11:32:32 +08:00

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

binux

2018-03-28 11:37:30 +08:00

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

fingerprint

2018-03-28 11:38:11 +08:00

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

42joker

2018-03-28 11:39:49 +08:00

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

forthdim

2018-03-28 11:39:58 +08:00

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

vegito2002

2018-03-28 11:43:13 +08:00 via iPad

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

LxExExl

2018-03-28 11:43:31 +08:00 via iPhone

我直观感觉就是个贪心

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

ftdejo

2018-03-28 11:45:30 +08:00

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

vegito2002

2018-03-28 11:46:28 +08:00 via iPad

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

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

没了。

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

hJohn

2018-03-28 11:47:13 +08:00

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

vegito2002

2018-03-28 11:48:12 +08:00 via iPad

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

lcdtyph

2018-03-28 11:48:26 +08:00

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

UIXX

2018-03-28 11:51:45 +08:00

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

hjb912

2018-03-28 11:56:56 +08:00

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

vegito2002

2018-03-28 11:58:47 +08:00 via iPad

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

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

hjb912

2018-03-28 11:59:48 +08:00

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

txx

2018-03-28 12:13:00 +08:00

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

fml

2018-03-28 12:38:18 +08:00

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

feverzsj

2018-03-28 12:40:31 +08:00

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

Bryan0Z

2018-03-28 12:42:15 +08:00 via Android

看起来像动态规划？

vegito2002

2018-03-28 12:48:48 +08:00

我始终认为找一条直线是一个坑, 我 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

2018-03-28 12:49:03 +08:00

@fml notability 手画的

binux

2018-03-28 12:49:27 +08:00

@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

2018-03-28 12:59:39 +08:00

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

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

binux

2018-03-28 13:11:41 +08:00

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

winglight2016

2018-03-28 13:13:50 +08:00

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

batman2010

2018-03-28 13:21:07 +08:00

（试着答一下）

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

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

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

qwsqwa

2018-03-28 13:21:08 +08:00

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

2018-03-28 13:27:34 +08:00 via iPhone

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

lance6716276

2018-03-28 13:32:16 +08:00 via Android

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

qwsqwa

2018-03-28 13:35:51 +08:00

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

Xs0ul

2018-03-28 13:43:04 +08:00

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

cover

2018-03-28 13:44:02 +08:00

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

fov6363

2018-03-28 13:50:55 +08:00

@contmonad 确定是求 delta 最优

vegito2002

2018-03-28 13:51:38 +08:00 via iPad

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

cover

2018-03-28 13:51:46 +08:00

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

vegito2002

2018-03-28 13:54:40 +08:00 via iPad

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

cover

2018-03-28 13:56:06 +08:00

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

cover

2018-03-28 13:56:56 +08:00

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

qwsqwa

2018-03-28 13:58:20 +08:00

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

jorneyr

2018-03-28 14:05:40 +08:00

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

jrient

2018-03-28 14:22:37 +08:00

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

2018-03-28 14:35:19 +08:00

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

)

rrfeng

2018-03-28 14:51:13 +08:00 via Android

@Lpl 怎么确定的 a 范围？

Lpl

2018-03-28 14:54:26 +08:00

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

Veigar

2018-03-28 14:55:01 +08:00

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

zjsxwc

2018-03-28 15:03:57 +08:00 via Android

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

lizz666

2018-03-28 15:05:18 +08:00

我是来学习的

renhairui

2018-03-28 15:09:38 +08:00

来学习~^_^

rrfeng

2018-03-28 15:10:41 +08:00 via Android

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

JerryV2

2018-03-28 15:22:30 +08:00

@lcdtyph 26
赞同

cuebyte

2018-03-28 15:36:43 +08:00

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

Stay4Life

2018-03-28 15:43:15 +08:00 via Android

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

polymerdg

2018-03-28 16:29:51 +08:00

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

binux

2018-03-28 16:30:29 +08:00

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

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

和 42L 结果一致

polymerdg

2018-03-28 16:31:36 +08:00

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

bigwang

2018-03-28 16:46:07 +08:00

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

xxlong

2018-03-28 16:51:24 +08:00

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

xxlong

2018-03-28 16:57:02 +08:00

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

contmonad

2018-03-28 17:15:02 +08:00 via iPhone

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

fanfx

2018-03-28 17:15:53 +08:00

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

xxlong

2018-03-28 17:22:33 +08:00

@binux 结果有问题吧。。

Lpl

2018-03-28 17:34:12 +08:00

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

fyxtc

2018-03-28 17:57:07 +08:00

楼主最后进了吗。。。。

utanbo

2018-03-28 18:02:23 +08:00

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

Parallel

2018-03-28 18:03:49 +08:00 via iPhone

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

CosimoZi

2018-03-28 18:19:22 +08:00

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

2018-03-28 18:36:37 +08:00

动态规划。

xrlin

2018-03-28 20:47:16 +08:00

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

mickeyandkaka

2018-03-28 22:10:01 +08:00

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

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

ksdx

2018-03-28 22:34:31 +08:00

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

ksdx

2018-03-28 22:43:37 +08:00

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

vegito2002

2018-03-29 00:18:06 +08:00

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

nomoon

2018-03-29 00:26:46 +08:00

最长非降子序列？

Paddington

2018-03-29 00:47:53 +08:00

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

imn1

2018-03-29 01:45:07 +08:00

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

binux

2018-03-29 02:28:41 +08:00

@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

2018-03-29 03:51:58 +08:00

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

binux

2018-03-29 04:14:14 +08:00

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

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

glasslion

2018-03-29 10:28:35 +08:00

@binux ==! USACO Gold 的题目

binux

2018-03-29 10:51:16 +08:00

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

Source
USACO 2008 February Gold

hjb912

2018-03-29 10:58:15 +08:00

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

xxlong

2018-03-29 12:41:14 +08:00

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

Alan1994

2018-03-29 17:37:03 +08:00

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

Alan1994

2018-03-29 17:48:01 +08:00

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

100

chaoxu

2018-05-06 05:30:38 +08:00

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