jingchi 电面+onsite

Urumic 发表于 2018-2-2 07:02
请问楼主，电面那道题，construct接龙就是调换数组元素的位置让他组成接龙对吗？

对，返回正确的一种就行了。input: ["abc", "bca", "cab"], output: ["abc","cab","bca"] or ["bca", "abc", "cab"] or ...

请问楼主，是每个村庄能建若干个仓库，还是说一个村庄只能建一个？谢谢啦！

Jingchi 不是考ACM题么

Urumic 发表于 2018-2-2 07:39
请问楼主，是每个村庄能建若干个仓库，还是说一个村庄只能建一个？谢谢啦！

若干村庄之间建若干个仓库，譬如两个村庄的位置分别为0和1，只能建一个仓库。那么仓库位置就在0.5。若是三个村庄（0，1，2）建两个仓库，那么村庄位置则是0.5和2或者是0和1.5。

ReMind 发表于 2018-2-2 07:34
对，返回正确的一种就行了。input: ["abc", "bca", "cab"], output: ["abc","cab","bca"] or ["bca", "ab ...

你这个有环。topological sort不了。如果找出最长的接龙肯定不行。对吧？求教

magicsets 发表于 2018-1-27 05:50
设村庄数目为n，表示为V1, ..., Vn，且不妨设V1

兄弟， 你看了下你这个状态转移方程 我有一个问题啊？ 当你选了S(k, u) = S(k-i, u-1) + Cost(k-i+1, k) 的时候， 你不能确定第k-i个村庄离第u-1个点近还是第u个点近吧？这样算出来的答案会不会不对啊？

全是做题啊楼主

请问LZ请问第二问 具体是怎么样？就往下一直走吗？

楼主接龙那题follow up能说下思路吗？  我用dfs做的 不知道是不是超时

xbbjames1 发表于 2018-2-6 14:39
兄弟， 你看了下你这个状态转移方程 我有一个问题啊？ 当你选了S(k, u) = S(k-i, u-1) + Cost(k-i+1, k)  ...

这是个好问题，考虑动态规划算法给出的最优划分，实质上是如下问题的最优解：

将V1, ..., Vn划分成m个区间，使Wi取值为第i个区间的所有村庄位置的平均值，求cost最小的划分方案

而你的意思是说，动态规划算法给出的“最优划分”，是否会出现这样的情况：

存在两个区间S、T，其中S中的某个村庄（比起S自身的中值点）反而更靠近T的中值点。

答案是不可能有这样的情况，用反证法不妨设某些村庄离其他区间的中值点更近，那么我们做如下操作：

(1) 将这些村庄移入对应的距离最近的区间
(2) 调整受影响区间的中值重新计算cost

那么，(1)+(2)本质上是K-means算法的1D特例的一个iteration，可以证明cost一定是减小的（分别考虑(1)和(2)，都是减小cost的；或者可以看下这个ppt的Proof of monoticity那一页：http://web.engr.oregonstate.edu/ ... /clustering2-16.pdf）

这与动态规划给出的cost的最优性矛盾。▢



补充内容 (2018-2-7 14:58):
还搜到一篇文章就是讲的一模一样的状态转移方程（居然有100多引用..）：
https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5148156/#!po=95.5882

不过文章里面也没有对最优性进行证明