一个单链表,每个节点里存储都是正整数,现在是无序的,可能会有重复数字,可以修改每个节点里的值,达到以下两个目标:
[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
42joker 2018-03-28 11:06:36 +08:00
先找出原先链最大值 X 的节点 G,节点 G 左边节点所有值只能等于 X,然后再找右边的最大 S 值 C 的节点,重复上述步骤,直到最右节点
|
2
42joker 2018-03-28 11:08:12 +08:00
。。。我这个想法有问题,我在想想再回答
|
3
SYP 2018-03-28 11:11:30 +08:00
这么修改跟新建一个全新的链表有区别吗?
|
4
42joker 2018-03-28 11:11:36 +08:00
先找出原先链最大值 X 的节点 G,然后计算其左边所有值的平均值 A,将平均值 A 设为新单链的值,重复上述步骤?
|
5
enzo113 2018-03-28 11:16:30 +08:00
最优的结果不一定是一条线吧
例如[8 7 8 2 2 2] |
6
vegito2002 2018-03-28 11:17:25 +08:00 via iPad
@SYP 应该是没有区别, 关键是, 用哪一个全新的链表, 找到这个
|
8
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]并不是在一条线上,所以用类似直线拟合的思路可能会有点问题
|
9
vegito2002 2018-03-28 11:27:15 +08:00
|
10
bravecarrot 2018-03-28 11:27:31 +08:00 via iPhone
很有意思 研究一下
|
12
binux 2018-03-28 11:29:05 +08:00 1
这个单链表感觉完全没有用啊,用个数组不是一样的吗?
从最小有效列表,[111...1] 开始 将 0 至 n1 位 +1,使得 △ 变小。得到列表 [2221...1] 将 0 至 n2 (n2<n1) 位 +1,使得 △ 变小。得到列表 [33..322..2111..1] 直到 △ 不再变小。 |
13
UIXX 2018-03-28 11:30:21 +08:00
建立竖向为节点数值增长的方向,横向为节点顺序增长方向,曼哈顿距离最小且结果中任意两点之间的斜率在 0 到-45 度之间,条件应该够的
|
14
vegito2002 2018-03-28 11:31:40 +08:00
@binux 如果一次只+1 的话, 这个算法的复杂度太高了, 只要让数组里面的数字之间的差值足够大, 最后的复杂度估计按照面试的标准很难接受.
|
15
UIXX 2018-03-28 11:32:32 +08:00
修改一下,是相邻两点之间
|
16
binux 2018-03-28 11:37:30 +08:00
@vegito2002 然后再贪心什么的优化呗。我只是给个思路
|
17
fingerprint 2018-03-28 11:38:11 +08:00
提供个思路,暂时还没有验证。先遍历把链表里相邻且数字相同的合并,这样就得到一系列有权值(权值为合并的个数)的数。然后再利用加权线性回归来得到一条直线。这条直线的参数如果不为整数,那就应该上下分别取整计算下,最多就是算 4 种参数组合,然后应该就可以得出最优解了。
|
19
forthdim 2018-03-28 11:39:58 +08:00
@vegito2002 你这个论证有问题吧,l2 的△应该是 AF+DE+CE,比 l1 大,楼主的基本思路没问题,上面 @UIXX 的答案也说了,就是找一个 k<0 的直线使得所有点到直线距离最短
|
20
vegito2002 2018-03-28 11:43:13 +08:00 via iPad
@forthdim l2 的 delta 只要把 C 拉到 E 就行了, 只有 CE 这么大,AB 不需要改变;
|
21
LxExExl 2018-03-28 11:43:31 +08:00 via iPhone
我直观感觉就是个贪心
对于 i 和 i+1 若递减 则不变 否则使 a[i]等于 a[i+1] |
23
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 没了。 我也同意这个应该是有一个可以简化问题的观察的, 但是不太好找; 而且真正面试的时候估计还是要证明自己的猜想的 |
24
hJohn 2018-03-28 11:47:13 +08:00
这是哪家公司的面试题目呀。。。有点难啊
|
25
vegito2002 2018-03-28 11:48:12 +08:00 via iPad
我也想问一下 OP, 这个题目给的是多少时间? 感觉 LC 的 hard 级别了有点,当然也有可能是我没想到点子上
|
26
lcdtyph 2018-03-28 11:48:26 +08:00
如果真是找直线的话就是最小二乘拟合嘛。
|
27
UIXX 2018-03-28 11:51:45 +08:00
补充详细。这道题挺直白的。
假设我们把每个节点看作是坐标的维度,楼主的题目就是已知一个四维点,求与已知点曼哈顿距离最小的点。但是这个点有约束条件。 假设我们建立一个二维坐标,横轴为节点顺序,竖轴为节点数值,还要求结果的那条链中任意两个相邻点的斜率在 0-负无穷之间。 综上所述... |
28
hjb912 2018-03-28 11:56:56 +08:00
求平均数,再向上或向下取整
|
29
vegito2002 2018-03-28 11:58:47 +08:00 via iPad
@UIXX 你这个思路好像整体是对的, 虽然我没有接触过这方面的编程实践, 不知道这种 constraint 搜索问题最后实现起来是什么难度, 尤其是维度增加的情况下。 不知道楼主面试的是什么职位, 如果面试的是算法工程师或者机器学习方面的, 还是有可能最后就是想要这个答案的。
如果是普通软件开发的面试, 感觉可能想要的是更加特性的一个解法。 |
30
hjb912 2018-03-28 11:59:48 +08:00
求中位数吧,算术平均数往往会受到异常大或异常小的数值影响
|
31
txx 2018-03-28 12:13:00 +08:00
这道题可以反着做,我从二分 delta,然后根据 delta 的结果去验证可行性...
|
32
fml 2018-03-28 12:38:18 +08:00
@vegito2002 #9 你这个图是用什么做的啊?
|
33
feverzsj 2018-03-28 12:40:31 +08:00
这难道不是面试官瞎诌的吗,要么就是他记错了
|
34
Bryan0Z 2018-03-28 12:42:15 +08:00 via Android
看起来像动态规划?
|
35
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, 哪个小就是最好的纠正方式. 这个只是一个抛砖引玉, 暂时没有办法证明这个思路. |
36
vegito2002 2018-03-28 12:49:03 +08:00
@fml notability 手画的
|
37
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 位中大的。 以此类推 |
38
Exceptionluo 2018-03-28 12:59:39 +08:00
2->4->1->3
10->0>0>0 1->19->2 22->0->0 |
39
binux 2018-03-28 13:11:41 +08:00
@binux 发现对已排序无效,补一下
第 n 位时,从 n 向 0 找一个分割点,使得右边中位数总小于左边中位数,取右边中位数 第 n-1 位时,从 n-1 向 0 找一个分割点,使得右边中位数总小于左边中位数,取右边中位数 以此类推 |
40
winglight2016 2018-03-28 13:13:50 +08:00
没有复杂度要求的话,用线性回归吧
|
41
batman2010 2018-03-28 13:21:07 +08:00
(试着答一下)
链表不是考点,可以直接看成数组。 先求数组的中位数,记为 m。 从右向左遍历 1. 如果递增,则继续; 2. 如果遇到非递增的元素(记为 a ),就把它右边的所有数组元素向中位数 m 对齐,并累加 delta 值。如果 a 小于 m,a 也向 m 对齐。把 a 作为新的遍历起点。 不断重复。 |
42
qwsqwa 2018-03-28 13:21:08 +08:00 9
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) |
43
contmonad 2018-03-28 13:27:34 +08:00 via iPhone
你确定是最小化 delta 而不是修改次数?
|
44
lance6716276 2018-03-28 13:32:16 +08:00 via Android
有点像保序回归,只不过保序回归是用的欧式距离而不是曼哈顿距离
|
46
Xs0ul 2018-03-28 13:43:04 +08:00
感觉很像是带约束的优化问题
|
47
cover 2018-03-28 13:44:02 +08:00
这种类型第一感觉是 dp,空间复杂度换时间复杂度
|
49
vegito2002 2018-03-28 13:51:38 +08:00 via iPad
@qwsqwa 膜拜一下, 这个思路可以说是很犀利了
|
51
vegito2002 2018-03-28 13:54:40 +08:00 via iPad
@qwsqwa 这里的第二维是 max value, 因为步长是 1, 可不可以这样, 第二维长度直接定义为链表本身的长度,也就是说只循环链表本身包含的这些个离散值, 而不是一次-1 这样的搜索?
|
52
cover 2018-03-28 13:56:06 +08:00
@qwsqwa 我有一个大胆的想法,会不会结果变化的数一定是在 这原先给的 x 个数中间,也就是不会出现中间数这种做法,例如 4 2 4 最后变化完一定是 4,2 里面选,那么你这个复杂度就会变成 o ( n*n )。。。 但是我没想通这个点是否正确
|
54
qwsqwa 2018-03-28 13:58:20 +08:00
@vegito2002 感觉可行,可以优化到 O(n*min(m,n))。
|
55
jorneyr 2018-03-28 14:05:40 +08:00
同一个链表有序,难道还有多种有序序列?
|
56
jrient 2018-03-28 14:22:37 +08:00 1
我说下我的想法把
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 步 个人认为,这个问题的关键在于如何找到新链表的最大值并定义新链表是顺序还是倒序排列 |
57
Lpl 2018-03-28 14:35:19 +08:00 2
这个问题可以用数学推导的方法来做,时间复杂度是 O(n)
![]( ) |
60
Veigar 2018-03-28 14:55:01 +08:00
这题目主要的作用是让你做不出来,压价用的。。并不是想让你真的做出来 你做出来就坏了
|
61
zjsxwc 2018-03-28 15:03:57 +08:00 via Android
取平均数吧,delta 的值就知道了
|
62
lizz666 2018-03-28 15:05:18 +08:00
我是来学习的
|
63
renhairui 2018-03-28 15:09:38 +08:00
来学习~^_^
|
66
cuebyte 2018-03-28 15:36:43 +08:00
看樓主的 append,覺得是給錯題了。
|
67
Stay4Life 2018-03-28 15:43:15 +08:00 via Android
从左到右读取,递减不变,发现变大就从前面到当前元素都取这一段的平均值,这样子?算法弱鸡
|
68
polymerdg 2018-03-28 16:29:51 +08:00
<img src="https://i.loli.net/2018/03/28/5abb5244ec800.png" alt=" bg2.jpg"/>
求最小阴影面积 |
69
binux 2018-03-28 16:30:29 +08:00
|
70
polymerdg 2018-03-28 16:31:36 +08:00
|
71
bigwang 2018-03-28 16:46:07 +08:00
各位想太多了,这只是一个 10 分钟的题
链表排序,二分法不适合,△值最小 ,排序结果是确定的,哪就要求排序结果稳定,答案就是 冒泡排序 |
74
contmonad 2018-03-28 17:15:02 +08:00 via iPhone 1
@qwsqwa 是的,我以为面试一般考常规题。刚才查了下这道的原题出自 https://stackoverflow.com/a/33865020
|
75
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. 不知道怎么样。
|
78
fyxtc 2018-03-28 17:57:07 +08:00
楼主最后进了吗。。。。
|
79
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。 |
80
Parallel 2018-03-28 18:03:49 +08:00 via iPhone 6
USACO 2008 February 金组原题 / POJ 3666
动态规划求解。 此帖终结。 |
81
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])) |
82
flowarmor 2018-03-28 18:36:37 +08:00
动态规划。
|
83
xrlin 2018-03-28 20:47:16 +08:00
第一眼就想到动态规划,但还是没想到具体思路。
|
84
mickeyandkaka 2018-03-28 22:10:01 +08:00
|
85
ksdx 2018-03-28 22:34:31 +08:00
这个应该就是求解,数轴上到任意 n 个点的距离和最短吧,如果不限制是正整数的话,那么这个点(对应具体数值)在中间位置就可以(左右点数量相等,要考虑 n 为奇偶数,要考虑 n 个数有重复……)。差不多了
|
86
ksdx 2018-03-28 22:43:37 +08:00
也可以用物理的方式理解,假设数轴是在一个平面上,每个点都打个洞,用线挂一个等重小球,穿过这个洞。然后到 n 个点距离和最短就等于是把这 n 条线打结在一个点上,然后由于小球重力,会在某个位置平衡,这是小球总的势能降到最低(水往低处流,能量最小~)。势能最小也意味着在平面上的线长度和最小,平面下的线长度和最长。由于是数轴,所以只要考虑左右平衡,左右小球数量相等,那么就会达到平衡,考虑下奇偶数。(类似三角形费马点)
这个也可以扩展到,平面、空间里。 |
87
vegito2002 2018-03-29 00:18:06 +08:00
一觉醒来真的是...楼主你面的到底是什么公司啊, POJ 的题目都出.
|
88
nomoon 2018-03-29 00:26:46 +08:00
最长非降子序列?
|
89
Paddington 2018-03-29 00:47:53 +08:00
好像发现这道题没有很简单。
|
90
imn1 2018-03-29 01:45:07 +08:00
为啥我第一时间想到的是方差?
|
91
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) |
92
kaiak 2018-03-29 03:51:58 +08:00
应该是用动态规划+中位数吧
|
93
binux 2018-03-29 04:14:14 +08:00
|
95
binux 2018-03-29 10:51:16 +08:00
|
96
hjb912 2018-03-29 10:58:15 +08:00
看到最小中位数我都笑了。把所有数据取出来求一个中位数就够了,为什么要反复求中位数?
[中位数] 是对变量中心位置的一种度量,这概念属于描述统计学数值方法,楼主你面的公司应该跟数据分析有关哦我猜:) |
98
Alan1994 2018-03-29 17:37:03 +08:00
这道题实际上就是弱条件下的保序回归。保序回归要求的是欧式距离最短,在欧式距离最短的情况下曼哈顿距离肯定也是最短的。
|
99
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 |