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

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

[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 不需要改变；

[LxExExl]

我直观感觉就是个贪心

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

[ftdejo]

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

[vegito2002]

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

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

没了。

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

[hJohn]

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

[vegito2002]

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

[lcdtyph]

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

[UIXX]

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

[hjb912]

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

[vegito2002]

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

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

[hjb912]

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

[txx]

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

[fml]

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

[feverzsj]

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

[Bryan0Z]

看起来像动态规划？

[vegito2002]

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

@fml notability 手画的

[binux]

@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]

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

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

[binux]

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

[winglight2016]

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

[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]

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

[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
动态规划求解。
此帖终结。

[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