A*****i
发帖数: 3587 | 1 今天刚被一个游戏公司虐了
原题如下：
三个methods: addRange(), queryRange(), deleteRange();
addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
个例子：
addRange(10, 200);
addRange(250, 500);
然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
deleteRange很简单只要delete掉相应的range就可以
弄了很久总觉得不能优化……遂放弃 |
f*****e
发帖数: 2992 | 2 不是leetcode题么？周六面试比较奇葩。
【在 A*****i 的大作中提到】
: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以
|
A*****i
发帖数: 3587 | 3 想知道有没有最优解……
leetcode上现在有解了？
【在 f*****e 的大作中提到】
: 不是leetcode题么？周六面试比较奇葩。
|
e***a
发帖数: 1661 | 4 what is the name of this company? |
A*****i
发帖数: 3587 | 5 machine zone
游戏公司用来练手的，没想到丫也从leetcode上出题啊
真没节操 |
y***n
发帖数: 1594 | |
x******r
发帖数: 367 | 7 这是leetcode哪个题？
好像没见过。
【在 A*****i 的大作中提到】
: machine zone
: 游戏公司用来练手的，没想到丫也从leetcode上出题啊
: 真没节操
|
p*****2
发帖数: 21240 | |
A*****i
发帖数: 3587 | 9 我擦我就是想不出更牛逼的办法了才来问的
没复杂度要求但是说目标数组是M级别的所以需要优化时间和空间……
【在 p*****2 的大作中提到】
: 大牛这题怎么解的？他们有复杂度要求吗？
|
p*****2
发帖数: 21240 | 10
O(n)的话比较容易，M级别感觉O(n)也够了，不然就上interval tree?
【在 A*****i 的大作中提到】
: 我擦我就是想不出更牛逼的办法了才来问的
: 没复杂度要求但是说目标数组是M级别的所以需要优化时间和空间……
|
|
|
A*****i
发帖数: 3587 | 11 我觉得O（N）太容易了，弄个大点儿的数组就成，但是我觉得人家的要求应该在O(1)左右
我开始写个O(N)的发现太容易了，觉得人家给我俩小时不能就弄个这吧……结果琢磨到
点儿了还没想出更好的
【在 p*****2 的大作中提到】
:
: O(n)的话比较容易，M级别感觉O(n)也够了，不然就上interval tree?
|
p*****2
发帖数: 21240 | 12
左右
O(N) bug free也不容易。O(1)不可能吧，最多就是优化到logN吧。
【在 A*****i 的大作中提到】
: 我觉得O（N）太容易了，弄个大点儿的数组就成，但是我觉得人家的要求应该在O(1)左右
: 我开始写个O(N)的发现太容易了，觉得人家给我俩小时不能就弄个这吧……结果琢磨到
: 点儿了还没想出更好的
|
t*********h
发帖数: 941 | 13 这个按左边边界binary search一下 发现180 在10，250之间那肯定就没在range里了
log(n)
【在 A*****i 的大作中提到】
: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以
|
d******g
发帖数: 42 | 14 把rang存为pair
class Pair{
int start;
int end;
}
然后每次addRang()的时候对已经存在的pair进行融合,,,
然后query的时候就进行比较,
感觉就是lc原题啊..有点变化,时间复杂度是多少?我不知道啊...总之好于O(n) |
m********l
发帖数: 791 | 15 不是吧
右边界也要考虑啊
（180， 190） 就是返回true啊
【在 t*********h 的大作中提到】
: 这个按左边边界binary search一下 发现180 在10，250之间那肯定就没在range里了
: log(n)
|
m********l
发帖数: 791 | 16 哪道原题啊
我咋没有印象
【在 d******g 的大作中提到】
: 把rang存为pair
: class Pair{
: int start;
: int end;
: }
: 然后每次addRang()的时候对已经存在的pair进行融合,,,
: 然后query的时候就进行比较,
: 感觉就是lc原题啊..有点变化,时间复杂度是多少?我不知道啊...总之好于O(n)
|
t*********h
发帖数: 941 | 17 每次addrange之后你都要merge好 这样每次查询看一边就可以了
【在 m********l 的大作中提到】
: 不是吧
: 右边界也要考虑啊
: （180， 190） 就是返回true啊
|
A*****i
发帖数: 3587 | 18 今天刚被一个游戏公司虐了
原题如下：
三个methods: addRange(), queryRange(), deleteRange();
addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
个例子：
addRange(10, 200);
addRange(250, 500);
然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
deleteRange很简单只要delete掉相应的range就可以
弄了很久总觉得不能优化……遂放弃 |
f*****e
发帖数: 2992 | 19 不是leetcode题么？周六面试比较奇葩。
【在 A*****i 的大作中提到】
: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以
|
A*****i
发帖数: 3587 | 20 想知道有没有最优解……
leetcode上现在有解了？
【在 f*****e 的大作中提到】
: 不是leetcode题么？周六面试比较奇葩。
|
|
|
e***a
发帖数: 1661 | 21 what is the name of this company? |
A*****i
发帖数: 3587 | 22 machine zone
游戏公司用来练手的，没想到丫也从leetcode上出题啊
真没节操 |
y***n
发帖数: 1594 | |
x******r
发帖数: 367 | 24 这是leetcode哪个题？
好像没见过。
【在 A*****i 的大作中提到】
: machine zone
: 游戏公司用来练手的，没想到丫也从leetcode上出题啊
: 真没节操
|
p*****2
发帖数: 21240 | |
A*****i
发帖数: 3587 | 26 我擦我就是想不出更牛逼的办法了才来问的
没复杂度要求但是说目标数组是M级别的所以需要优化时间和空间……
【在 p*****2 的大作中提到】
: 大牛这题怎么解的？他们有复杂度要求吗？
|
p*****2
发帖数: 21240 | 27
O(n)的话比较容易，M级别感觉O(n)也够了，不然就上interval tree?
【在 A*****i 的大作中提到】
: 我擦我就是想不出更牛逼的办法了才来问的
: 没复杂度要求但是说目标数组是M级别的所以需要优化时间和空间……
|
A*****i
发帖数: 3587 | 28 我觉得O（N）太容易了，弄个大点儿的数组就成，但是我觉得人家的要求应该在O(1)左右
我开始写个O(N)的发现太容易了，觉得人家给我俩小时不能就弄个这吧……结果琢磨到
点儿了还没想出更好的
【在 p*****2 的大作中提到】
:
: O(n)的话比较容易，M级别感觉O(n)也够了，不然就上interval tree?
|
p*****2
发帖数: 21240 | 29
左右
O(N) bug free也不容易。O(1)不可能吧，最多就是优化到logN吧。
【在 A*****i 的大作中提到】
: 我觉得O（N）太容易了，弄个大点儿的数组就成，但是我觉得人家的要求应该在O(1)左右
: 我开始写个O(N)的发现太容易了，觉得人家给我俩小时不能就弄个这吧……结果琢磨到
: 点儿了还没想出更好的
|
t*********h
发帖数: 941 | 30 这个按左边边界binary search一下 发现180 在10，250之间那肯定就没在range里了
log(n)
【在 A*****i 的大作中提到】
: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以
|
|
|
d******g
发帖数: 42 | 31 把rang存为pair
class Pair{
int start;
int end;
}
然后每次addRang()的时候对已经存在的pair进行融合,,,
然后query的时候就进行比较,
感觉就是lc原题啊..有点变化,时间复杂度是多少?我不知道啊...总之好于O(n) |
m********l
发帖数: 791 | 32 不是吧
右边界也要考虑啊
（180， 190） 就是返回true啊
【在 t*********h 的大作中提到】
: 这个按左边边界binary search一下 发现180 在10，250之间那肯定就没在range里了
: log(n)
|
m********l
发帖数: 791 | 33 哪道原题啊
我咋没有印象
【在 d******g 的大作中提到】
: 把rang存为pair
: class Pair{
: int start;
: int end;
: }
: 然后每次addRang()的时候对已经存在的pair进行融合,,,
: 然后query的时候就进行比较,
: 感觉就是lc原题啊..有点变化,时间复杂度是多少?我不知道啊...总之好于O(n)
|
t*********h
发帖数: 941 | 34 每次addrange之后你都要merge好 这样每次查询看一边就可以了
【在 m********l 的大作中提到】
: 不是吧
: 右边界也要考虑啊
: （180， 190） 就是返回true啊
|
d******n
发帖数: 22 | 35 请问大神，后来又拿到onsite吗？
【在 A*****i 的大作中提到】
: 今天刚被一个游戏公司虐了
: 原题如下：
: 三个methods: addRange(), queryRange(), deleteRange();
: addRange用来给定一个范围内的数字比如addRange(10, 200)表示10到200这个区间的数
: 字被加入到range中，queryRange用来判定当前range有没有在被加进去的range里面举
: 个例子：
: addRange(10, 200);
: addRange(250, 500);
: 然后再queryRange(180, 300)的时候应该返回false，因为有201-249这一段没有被加入
: deleteRange很简单只要delete掉相应的range就可以
|
t**********h
发帖数: 2273 | 36 不是lc 题
【在 f*****e 的大作中提到】
: 不是leetcode题么？周六面试比较奇葩。
|
l*****a
发帖数: 14598 | 37 addRange不就是insert interval吗？
query 也差不多，binary search找出start/end的插入位置，就可以判断是不是在原来
区间了
【在 t**********h 的大作中提到】
: 不是lc 题
|
