一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1783|回复: 9
收起左侧

F, G, L, U, A 店面

[复制链接] |试试Instant~ |关注本帖
vbnmmnbv 发表于 2017-9-17 02:06:19 | 显示全部楼层 |阅读模式

2017(7-9月) 码农类 博士 全职@Google - 网上海投 - 技术电面 |Other在职跳槽

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

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

x
F: 伞一思G: 尔尔爸; 给一个tree node,  return in order successor
L: 而丝丝, 可以有dup;  一个ordered list, 找到正确插入位置
U: 一个int list, return start 到 end 里 的最小数, 可以pre-processing.鐣欏璁哄潧-涓浜-涓夊垎鍦
A: 两个list, 输出不相同element的list. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴

评分

3

查看全部评分

lcq123 发表于 2017-9-17 06:12:45 | 显示全部楼层
请问A家那道题楼主是怎么做的?谢谢!
回复 支持 反对

使用道具 举报

 楼主| vbnmmnbv 发表于 2017-9-17 11:14:26 | 显示全部楼层
lcq123 发表于 2017-9-17 06:12
请问A家那道题楼主是怎么做的?谢谢!

我就先保存到两个set, 然后traverse set1找不在set2的元素, 再traverse set2 找不在set1的元素, 加起来
回复 支持 反对

使用道具 举报

lcq123 发表于 2017-9-17 11:50:12 | 显示全部楼层
vbnmmnbv 发表于 2017-9-17 11:14. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我就先保存到两个set, 然后traverse set1找不在set2的元素, 再traverse set2 找不在set1的元素, 加起来 ...

哦哦,好的,谢谢楼主!!!
回复 支持 反对

使用道具 举报

kevintong 发表于 2017-9-23 20:56:48 | 显示全部楼层
请教楼主Uber的题怎么做啊?
回复 支持 反对

使用道具 举报

 楼主| vbnmmnbv 发表于 2017-9-26 00:37:13 | 显示全部楼层
kevintong 发表于 2017-9-23 20:56
请教楼主Uber的题怎么做啊?

可以用dp做, 后来知道好像也可以用什么segment tree.
回复 支持 反对

使用道具 举报

kevintong 发表于 2017-9-26 10:19:38 | 显示全部楼层
segment tree不是很说得通啊,因为要存i,i+1每个区间的min,这和直接使用数组没什么区别呀。. 1point 3acres 璁哄潧
. 1point3acres.com/bbs
dp什么思路呢?时间复杂度能优化到多少呀?感谢楼主了!
回复 支持 反对

使用道具 举报

 楼主| vbnmmnbv 发表于 2017-9-27 14:10:47 | 显示全部楼层
kevintong 发表于 2017-9-26 10:19. 1point 3acres 璁哄潧
segment tree不是很说得通啊,因为要存i,i+1每个区间的min,这和直接使用数组没什么区别呀。

dp什么思路 ...

我是计算一个二维数组,存i 到 j的最小值,  二维数组的建立过程用到dp,这个应该是平方的吧。 然后query 就是O(1)了。
. 1point3acres.com/bbs
segment tree我不了解,但是估计可以做的比平方好?
回复 支持 反对

使用道具 举报

kevintong 发表于 2017-9-27 21:41:07 | 显示全部楼层
vbnmmnbv 发表于 2017-9-27 14:10
我是计算一个二维数组,存i 到 j的最小值,  二维数组的建立过程用到dp,这个应该是平方的吧。 然后query ...

恩恩,DP这样很有道理。我觉得线段树不好做,不是很说得通
回复 支持 反对

使用道具 举报

 楼主| vbnmmnbv 发表于 2017-9-28 10:48:49 | 显示全部楼层
kevintong 发表于 2017-9-27 21:41
恩恩,DP这样很有道理。我觉得线段树不好做,不是很说得通

你看这个不行吗?
. 鍥磋鎴戜滑@1point 3 acres
http://www.geeksforgeeks.org/seg ... ange-minimum-query/
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-21 22:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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