f********a
发帖数: 165 | 1 看到别人的面经：
坐标系第一象限上加射线，接下来所有输入的数据都是不相等的整数，不用考虑任何
edge case。 想要这两个操作：1. insertX（x）， insertY（y），比如insertX， 就
是现有的图上面加上x这条射线，象限会被插入的这些射线分成网格，每个格叫一个区
域。 2. find（x，y）， 就是给个坐标，返回这个坐标所在的区域。可以返回区域的
id，区域的id自己定。用二叉树。
x,y是两个不同二叉树？Node里面存range? | y******s
发帖数: 92 | 2 一点不成熟的想法：
1. 用一个类似二叉树的结构，每一个node有四个变量{(x_l, x_r}, {y_b, y_u})，根
部为{(0, infi}, (0, infi)}
2. insert的时候，比如insterX(x)，验证current node有没有child,如果有进入child
；没有，在此node分出两个child，一个为{(x_l, x), (y_b, y_u)}，另一个为{(x, x_
r), (y_b, y_u)}
3. 查找时候，验证current node有没有child，如果有进入child；没有验证是否x_l <
x < x_r和y_b < y < y_u | t*****3
发帖数: 112 | 3 x、y两个线段树，insertX（x）， insertY（y）分别是对应树的插入操作，给定一个
坐标用find(x,y)找到两个叶子节点对应的区间
【在 f********a 的大作中提到】
: 看到别人的面经：
: 坐标系第一象限上加射线，接下来所有输入的数据都是不相等的整数，不用考虑任何
: edge case。 想要这两个操作：1. insertX（x）， insertY（y），比如insertX， 就
: 是现有的图上面加上x这条射线，象限会被插入的这些射线分成网格，每个格叫一个区
: 域。 2. find（x，y）， 就是给个坐标，返回这个坐标所在的区域。可以返回区域的
: id，区域的id自己定。用二叉树。
: x,y是两个不同二叉树？Node里面存range?
| b******i
发帖数: 914 | 4 这题你自己也说了，x, y两个不同的二叉树，node里面存range，
其实就是x, y是两个不同的线段树，要实现线段树的插入和查找的操作。
要注意的地方就是id，比如每个线段树可以用一个递增的id，每次插入增加nodes的时
候就分配新的id。最后返回区域的id就是这两个id, idx, idy综合起来的id。比如如果
各自的id都是int，可以返回一个long id = ( (long)idx << 32) | (long)idy;
【在 f********a 的大作中提到】
: 看到别人的面经：
: 坐标系第一象限上加射线，接下来所有输入的数据都是不相等的整数，不用考虑任何
: edge case。 想要这两个操作：1. insertX（x）， insertY（y），比如insertX， 就
: 是现有的图上面加上x这条射线，象限会被插入的这些射线分成网格，每个格叫一个区
: 域。 2. find（x，y）， 就是给个坐标，返回这个坐标所在的区域。可以返回区域的
: id，区域的id自己定。用二叉树。
: x,y是两个不同二叉树？Node里面存range?
| j****1
发帖数: 99 | 5 Great idea, thanks for sharing!
【在 b******i 的大作中提到】
: 这题你自己也说了，x, y两个不同的二叉树，node里面存range，
: 其实就是x, y是两个不同的线段树，要实现线段树的插入和查找的操作。
: 要注意的地方就是id，比如每个线段树可以用一个递增的id，每次插入增加nodes的时
: 候就分配新的id。最后返回区域的id就是这两个id, idx, idy综合起来的id。比如如果
: 各自的id都是int，可以返回一个long id = ( (long)idx << 32) | (long)idy;
|
|
