《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1979|回复: 7
收起左侧

[算法题] Amazon 面试题, Four Integers 问题解法

[复制链接] |试试Instant~ |关注本帖
HuaZhe 发表于 2016-9-20 21:41:27 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
大家好, 又有问题需要求助了!

最近刷题遇到了four integers 问题, 就是给 4 个整形数, 通过交换他们的位置,使F(S)= abs(S[0]-S[1]) + abs(S[1]-S[2]) + abs(S[2]-S[3]) 的值最大。

大家有什么思路吗? 万分感谢!
magicsets 发表于 2017-7-26 01:02:19 | 显示全部楼层
本帖最后由 magicsets 于 2017-7-26 01:25 编辑

这题可以重新表述一下:数轴上有a,b,c,d四个点(不妨设a < b < c < d),从某个点出发,沿数轴访问其它点各一次,问路径的最大长度是多少。

比如说
(1) 路径
  1. a --> b --> c --> d
复制代码
的长度为|ab| + |bc| + |cd|

(2) 路径
  1. a --------> c
  2.       b <--
  3.         --------> d
复制代码
的长度为|ab| + 3|bc| + |cd|


可能的组合并不多,稍微枚举一下可以发现最长的是这条:
  1. a <-------- c
  2.   --------------> d
  3.       b <--------
复制代码
长度为2|ab| + 3|bc| + 2|cd| -- 按照c,a,d,b的顺序。

而由a,b,c,d变换到c,a,d,b,一种可行方法就是
第一个数和第二个数交换, 第三个数和第四个数交换, 再第一个数和第四个数交换

PS: 如果要严格证明的话,可以用枚举+排除的方法,因为路径总数只有4!=24种,其中还有一部分是由对称性而重复的。
回复 支持 4 反对 0

使用道具 举报

grady0407 发表于 2016-9-20 22:38:35 | 显示全部楼层
我觉得可以这样想,假设a1<a2<a3<a4, 那么a4-a1, a4-a2是最大的两个差,所以一定要a1, a4, a2 或者 a2, a4, a1. 至于a3 放哪,看一看发现a2, a4, a1, a3是最大的。 当然, a3, a1, a4, a2也是一样的
回复 支持 反对

使用道具 举报

 楼主| HuaZhe 发表于 2016-9-21 00:11:30 | 显示全部楼层
grady0407 发表于 2016-9-20 22:38
我觉得可以这样想,假设a1

嗯我看网上有网友的答案是。 把这个四个int值给排序,然后将 第一个数和第二个数交换, 第三个数和第四个数交换, 再第一个数和第四个数交换。。。这是啥
回复 支持 反对

使用道具 举报

waynetang 发表于 2017-7-25 12:43:50 | 显示全部楼层
本帖最后由 waynetang 于 2017-7-25 12:52 编辑

我也想知道为什么,求好心人解答
回复 支持 反对

使用道具 举报

saklyn 发表于 2017-7-26 01:25:07 | 显示全部楼层
面试的时候出不了最优解直接暴力解再排除也行的,情况也没多少。这种需要纸和笔的电面要怎么说?
最大和最小的肯定在最中间,2种排列方式,后面再对中间两种试个两次也很简单。
回复 支持 反对

使用道具 举报

2011051305 发表于 2017-7-26 02:40:21 | 显示全部楼层
请问这个问题是面巾里的吗? 刷题的tag里没有这个诶。。难道我刷的是假题...
回复 支持 反对

使用道具 举报

JustSoSo 发表于 2017-7-26 06:07:37 | 显示全部楼层
可以用全排列吗? 总共也就 (4!)种情况啊
回复 支持 反对

使用道具 举报

本版积分规则

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-11-21 14:39

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表