📣 VIP通行证夏日特惠 限时立减$68
楼主: UpDownDOTA
跳转到指定楼层
上一主题 下一主题
收起左侧

Yelp电面跪经,感觉被烙印黑了

🔗
physheng 2016-10-27 05:36:18 | 只看该作者
全局:
delly224 发表于 2016-10-27 05:05
楼主您好,我想的是sort之后遍历,请问map怎么做?

我觉得如果只是要求数字连续而位置可以不连续,那么可以存进hashmap以后,对每个数,看看这个数是不是sequence的最小数,如果是的话就往上找。
回复

使用道具 举报

🔗
delly224 2016-10-27 05:41:22 | 只看该作者
全局:
physheng 发表于 2016-10-27 05:36
我觉得如果只是要求数字连续而位置可以不连续,那么可以存进hashmap以后,对每个数,看看这个数是不是sequ ...

没听懂,能举个例子吗
回复

使用道具 举报

🔗
physheng 2016-10-27 05:59:40 | 只看该作者
全局:
delly224 发表于 2016-10-27 05:41
没听懂,能举个例子吗

比如上面的例子,我们要从48,或者99开始找,因为98和47不在hashmap里面。
回复

使用道具 举报

全局:
这个题dp做n^2 贪心做 nlogn 如果非要o(n)的话 可以做一个双端队列 和一个(value, index)的structure 然后按照value的大小从两端push进去 然后deque遍历一遍 把index错位的删掉 然后求长度
回复

使用道具 举报

🔗
yhatl 2016-10-27 09:15:05 | 只看该作者
全局:
LC128                                                                        
回复

使用道具 举报

🔗
 楼主| UpDownDOTA 2016-10-27 10:06:43 | 只看该作者
全局:
做法是hashmap存数字,然后遍历一遍,对于X,如果X-1不在hashmap里面,那就一个个加一往上找,就是极大值。复杂度是O(n)。

楼主当时强行装逼要写一个single traversal一边建hashmap一边处理的,其实是可以写的但是容易出问题还不好理解,然后就装逼失败了= =
回复

使用道具 举报

🔗
hohohw 2016-11-2 09:05:40 | 只看该作者
全局:
可以考慮用treemap, keyset() 輸出便會自動照順序 log(n)
回复

使用道具 举报

🔗
hohohw 2016-11-2 09:08:17 | 只看该作者
全局:
UpDownDOTA 发表于 2016-10-27 10:06
做法是hashmap存数字,然后遍历一遍,对于X,如果X-1不在hashmap里面,那就一个个加一往上找,就是极大值。 ...

如果 n = 1 , 1024
你卻要跑到1024
這方法應該是O( max(n) )
回复

使用道具 举报

🔗
zjuzqj 2016-11-2 16:32:35 | 只看该作者
全局:
这不是并查集做么
回复

使用道具 举报

🔗
 楼主| UpDownDOTA 2016-11-3 04:29:46 | 只看该作者
全局:
hohohw 发表于 2016-11-1 20:08
如果 n = 1 , 1024
你卻要跑到1024
這方法應該是O( max(n) )

找不到2,就停了。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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