狗家onsite

yyyusa · 2017-10-23 15:03:21

加油站那题不是很明白？了。加油站的位置是数字还是坐标？

yyyusa · 2017-10-23 15:05:33

第二题应该是二分查找加上分治吧？复杂度nlogn

Alvin_Bao · 2017-10-23 15:24:12

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Alvin_Bao · 2017-10-23 15:41:24

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Alvin_Bao · 2017-10-23 15:51:11

yyyusa 发表于 2017-10-23 15:05
第二题应该是二分查找加上分治吧？复杂度nlogn

这个题二分的话应该怎么搞呢？dp可以有n^2的算法，nlogn怎么搞的呢？

reliveinfire · 2017-10-23 16:04:14

请问 move 要怎么保持subproblem dp的结果?
是想说把跟第二个一样的元素移除当作move

但是似乎dp[i][j], 就会变成分段这边要怎么处理呢?

yyyusa · 2017-10-23 16:07:20

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

Alvin_Bao · 2017-10-23 16:14:02

yyyusa 发表于 2017-10-23 16:07
也不是二分，就是分治法。平均情况下应该是nlogn，最坏情况n^2
每次把数组分成两半，使得左半边的所有数 ...

你是说用partition分区吗？可以举个例子吗？

baudelaire · 2017-10-23 17:16:50

请问楼主是几年经验呢怎么会有两轮系统设计

baudelaire · 2017-10-23 18:04:31

Alvin_Bao 发表于 2017-10-23 15:51
这个题二分的话应该怎么搞呢？dp可以有n^2的算法，nlogn怎么搞的呢？

层主能详细说说怎么dp吗？我没懂这题题意，分割是从一个点分成两部分麽？这样如果分成两部分岂不是第一部分的元素比第二部分都要小