搜索
体验新版
<
一亩三分地»论坛 › 专业技术 › 刷题 › 给一堆点和点之间的连线，判断多少正方形
12下一页
返回列表 发新帖
查看: 3033| 回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

[高频题] 给一堆点和点之间的连线，判断多少正方形

刷题 高频题
🔗
umialpha | 只看该作者 |倒序浏览
全局：

注册一亩三分地论坛，查看更多干货！

您需要 登录 才可以下载或查看附件。没有帐号？注册账号

x
本帖最后由 14417335 于 2019-3-26 20:39 编辑


您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客，您好！
本帖隐藏的内容需要积分高于 120 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies



补充内容 (2019-3-27 12:50):
这题没有想象的那么容易，因为可以用多个线段组成一条边，比如长度为1和长度为2如果首位相连，可以组成长度为3的线段。

评分

参与人数 2大米 +16 收起 理由
rikoizz + 1 很有用的信息！
14417335 + 15 很有用！希望能尽量详细，会有更高奖励

查看全部评分


上一篇：BAT机器学习面试10道题，求大米
下一篇：只用C++，java刷题可以吗

相关帖子
回复

使用道具 举报

推荐
chenyijia055 2019-5-29 04:58:42 | 只看该作者
全局：
dlwlrma 发表于 2019-5-29 03:50
是这个意思。虽然空间大，但query快。如果为了省空间，也可以用segment tree来query range sum. 如果这个 ...

我觉得这个bitmap的解法不是考点，因为在某篇面经里面好像专门强调了平面空间是无限大的。我对segment tree/indexed tree的理解并不很深，就我最基本的理解这两种树都不是为了省了空间的， 尤其的segment tree他的空间复杂度更高，会达到2n, 这两种树的优点只是在频繁的query和update的情况下, 都是logn。 我不知道disjoined interval 的segment tree/indexed tree要怎么建，怎么query。 一般的情况都是对连续的array建树。但这样的话空间复杂度并不能降下来。最直接的解法，大概就是给每个x,y 建立一个list of disjoint intervals, 代表哪个区间被覆盖了, 存在两个hashmap里面。每次插入线段就是insert interval O(n), 判断被覆盖没就是binary search logn。 这样空间能省下来。 由于这题并不会频繁的加线减线 update，所以segement tree的优势并不明显，建立树本身也要花O(n)的时间。 如果有大神能写一个disjoined interval 的segment tree/indexed tree, 我还是希望能观摩一下。
回复

使用道具 举报

推荐
dlwlrma 2019-5-25 14:08:16 | 只看该作者
全局：
您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客，您好！
本帖隐藏的内容需要积分高于 200 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies
Coderust: Hacking the Coding Interview
回复

使用道具 举报

推荐
chenyijia055 2019-5-28 11:53:33 | 只看该作者
全局：
dlwlrma 发表于 2019-5-25 14:08
**** 本内容被作者隐藏 ****

我不知道我理解你的意思没，你的accumulative sum相当于一个 accumulative 的bitmap, 每一个index都对应坐标系里的一个点,  有就是1， 没有就是0， 然后再把之前的加起来， 你quary的时候，比如说看1-4有没有线, 就去看 index是4 的prefix sum-index是1 的prefix sum, 看是不是4-1=3, 如果是就是覆盖了，不是就没覆盖。 有点像一个没有空间优化版本的 binary index tree. 如果是这样的话，因为平面是无限的，空间复杂度会相当高吧。 如果有两个点的坐标相差很大，哪怕中间是空的你也需要记录之间每一个点的accumulative sum?
回复

使用道具 举报

🔗
337845818 2019-3-26 21:32:54 | 只看该作者
全局：
给的都是vector呗, 起点终点那种.  长度不一致不考虑, 一致长度做cross product.
回复

使用道具 举报

🔗
 楼主| umialpha 2019-3-27 12:49:09 | 只看该作者
全局：
337845818 发表于 2019-3-26 21:32
给的都是vector呗, 起点终点那种.  长度不一致不考虑, 一致长度做cross product.

不仅仅这么简单，比如长度1,2 可以和长度为3的组成两条边。
回复

使用道具 举报

🔗
337845818 2019-3-28 02:58:17 | 只看该作者
全局：
umialpha 发表于 2019-3-27 12:49
不仅仅这么简单，比如长度1,2 可以和长度为3的组成两条边。

还是把所有顶点都存下来, 然后用对角线的点去确认吧..
回复

使用道具 举报

🔗
bazingaa 2019-3-30 00:35:22 | 只看该作者
本楼：
全局：
思考一下！！
回复

使用道具 举报

🔗
rikoizz 2019-5-26 15:19:20 | 只看该作者
全局：
线段都是水平或者垂直的吗，线段的数量是多少呢？
回复

使用道具 举报

🔗
dlwlrma 2019-5-29 03:50:34 | 只看该作者
全局：
chenyijia055 发表于 2019-5-28 11:53
我不知道我理解你的意思没，你的accumulative sum相当于一个 accumulative 的bitmap, 每一个index都对应 ...

是这个意思。虽然空间大，但query快。如果为了省空间，也可以用segment tree来query range sum. 如果这个方法不好，还有别的方法来判断线段有没有被覆盖吗？
回复

使用道具 举报

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

本版积分规则

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