匿名1487
(匿名1487)
7 November 2019 23:13
1
这个是朋友用我的账号发的
遇到了一道leetcode 没有的题目 面经也没有看过
所以想问下难度, 以及到现在都没接到通知,是不是凉凉了
就是 给一个array reorder it to max sum of the distance between adjacent elements
一开始很复杂
后来根据提示 优化了 time compleixty O(nlogn) space O(1)
看大部分电面 基本都是两道题medium的 要不一道 hard
结果他最后只做出来这一道,(应该medium的)
所以想问下大家 这道题的难度 以及希望大么
匿名1487
(匿名1487)
7 November 2019 23:23
4
是new grad的,请问您怎么看啊
基本把最近tag题目 和面经都做了
结果一看到这题 就懵了。。
加上面试官是个印度人,您觉得希望还大么。。
唉
匿名1487
(匿名1487)
7 November 2019 23:36
7
应该是做出来了?
test case 过了 最后 也让出了几个
一开始是 用pq store all the interval 然后根据poll 的再做下一步处理
但是time complexity 太大了
后来是类似一个array 【5,22,1,11,8,9】
先sort 【1,5,8, 9, 11,22】然后using two pointer
一个是 left right
一开始最大的distance 是 between 1 22
所以 算出他们的
然后 对于 22 来说另一个 最大的distance 是 the smallest element larger than 1, 5
对于 1来说 另一个最大的是 the largest element less than 11
这么处理的
匿名1487
(匿名1487)
8 November 2019 00:07
10
我自己吧 不过中间要切换direction 我遇到了bug 结果debug 好久 就做了一道 唉
现在觉得 希望渺茫 唉
匿名1487
(匿名1487)
8 November 2019 00:08
11
您觉得希望大么
这道题能算什么level的啊
谢谢!!
Xavier
(Xavier)
8 November 2019 00:08
12
这题其实思路说出来的话也就不那么难了
狗家就是难想思路
做过跟没做过确实差很多
运气不够好吧
匿名1487
(匿名1487)
8 November 2019 00:17
16
我也觉得是medium的,不知道怎么回事,点回复结果弄错了
我朋友都遇到tag 面经的了,结果我当时一看题目真的懵了
难受了半天 算了move on吧
谢谢您的回复!!
x老师解释一下你有什么好的idea解这条题目
我能想到的方法是:
排序 n*log(n)
两种可能
A.放最小的,然后最大的,然后放次小的,放次大的 。。。。
B. 放最大的,放最小的,放次大的,。。。。
比较一下最后两种情况
不知道这种方法对不对? 有什么数据结构时候解这个题目?谢谢
Xavier
(Xavier)
8 November 2019 18:29
18
我觉得就 greedy 吧
比如 【1,5,8, 9, 11,22】
先选了 【1,22】,剩下 【5,8, 9, 11】
然后在两头,即5和11中选。至于放在【1,22】哪边,用Math.abs 算下4种组合选最大的即可。
agree, greedy
你这个可以算出来,但是复杂度就指数级了,n大一点,组合的摆放方式就太多了
但是我的这个方法,我没法证明是对的,看起来好像是对的