j********e
发帖数: 1192 | 1 1. 一个Interval的数组，例如(1, 3), (2, 4), (2, 5),返回所有Interval
都overlap的Interval。例如(2,3)在这个例子中。
2. 一颗tree（不是BT，可以n个child), write to a file, and read.
O(logN) additional memory.
Follow up question，不写额外的数据到文件怎么办（例如不能写节点编号) |
w****x
发帖数: 2483 | 2 1. 好像大部分interval的题都是数开始点和结束点, 不分起始点和结束点对所有点排
序, 然后过一遍, 前n个点因该都是起始点
2. 对每个数节点编号, serialize的时候记录当前的编号, 父节点编号, BFS |
p*****2
发帖数: 21240 | 3
第一题没那么麻烦。直接merge就行了。没有overlap就退出返回空
【在 w****x 的大作中提到】
: 1. 好像大部分interval的题都是数开始点和结束点, 不分起始点和结束点对所有点排
: 序, 然后过一遍, 前n个点因该都是起始点
: 2. 对每个数节点编号, serialize的时候记录当前的编号, 父节点编号, BFS
|
j********e
发帖数: 1192 | 4 对第二题，follow up问题是，不能增加编号（不增加文件大小）怎么做
【在 w****x 的大作中提到】
: 1. 好像大部分interval的题都是数开始点和结束点, 不分起始点和结束点对所有点排
: 序, 然后过一遍, 前n个点因该都是起始点
: 2. 对每个数节点编号, serialize的时候记录当前的编号, 父节点编号, BFS
|
p*****2
发帖数: 21240 | 5
第二题DFS就行了吧？
【在 j********e 的大作中提到】
: 对第二题，follow up问题是，不能增加编号（不增加文件大小）怎么做
|
w****x
发帖数: 2483 | 6
没错 ， 有个锤子看到什么都是钉子了
【在 p*****2 的大作中提到】
:
: 第二题DFS就行了吧？
|
w****x
发帖数: 2483 | 7
你总得有额外数据表示结构吧，二叉树也有左右指针啊， 要不这样：
1{2,3{4,5,6}, {7,8{9,10}}}
【在 j********e 的大作中提到】
: 对第二题，follow up问题是，不能增加编号（不增加文件大小）怎么做
|
p*********y
发帖数: 3 | 8 二爷你看scan一遍起点找最大终点找最小是不是就可以了，如果最大起点大于最小终点
输出空
【在 p*****2 的大作中提到】
:
: 第二题DFS就行了吧？
|
j********e
发帖数: 1192 | 9 哦对了，可以写入一个byte，表示是否有左右子节点。
更新: 是写入一个k，表示k个children。
【在 w****x 的大作中提到】
:
: 你总得有额外数据表示结构吧，二叉树也有左右指针啊， 要不这样：
: 1{2,3{4,5,6}, {7,8{9,10}}}
|
j********e
发帖数: 1192 | 10 Bingo
【在 p*****2 的大作中提到】
:
: 第二题DFS就行了吧？
|
|
|
w****x
发帖数: 2483 | 11
不是非2叉树吗，直接说答案吧
【在 j********e 的大作中提到】
: Bingo
|
p*****2
发帖数: 21240 | 12
我觉得可以呀。
【在 p*********y 的大作中提到】
: 二爷你看scan一遍起点找最大终点找最小是不是就可以了，如果最大起点大于最小终点
: 输出空
|
p*****2
发帖数: 21240 | 13
我想就是preorder DFS, 孩子之后加个特殊符号就行了吧。
【在 w****x 的大作中提到】
:
: 不是非2叉树吗，直接说答案吧
|
j********e
发帖数: 1192 | 14 我上面说错了，可以加一个变量表示几个child。
我给的答案和peking2的一样，就是DFS。Write就比较容易了，多写一个int
表示几个children。
读的时候，用了个queue，读到某个节点时，如果它有k个children，那么
queue里最后k个就是它的children了。queue的最大长度应该是O(logN*K),
(最多K个children)
【在 w****x 的大作中提到】
:
: 不是非2叉树吗，直接说答案吧
|
p*****2
发帖数: 21240 | 15
读的时候应该用DFS也可以。
【在 j********e 的大作中提到】
: 我上面说错了，可以加一个变量表示几个child。
: 我给的答案和peking2的一样，就是DFS。Write就比较容易了，多写一个int
: 表示几个children。
: 读的时候，用了个queue，读到某个节点时，如果它有k个children，那么
: queue里最后k个就是它的children了。queue的最大长度应该是O(logN*K),
: (最多K个children)
|
w****x
发帖数: 2483 | 16
比起记录parent编号由啥优势吗,都是一个节点一个额外int啊
【在 j********e 的大作中提到】
: 我上面说错了，可以加一个变量表示几个child。
: 我给的答案和peking2的一样，就是DFS。Write就比较容易了，多写一个int
: 表示几个children。
: 读的时候，用了个queue，读到某个节点时，如果它有k个children，那么
: queue里最后k个就是它的children了。queue的最大长度应该是O(logN*K),
: (最多K个children)
|
w****x
发帖数: 2483 | 17
恩,不需要用queue
【在 p*****2 的大作中提到】
:
: 读的时候应该用DFS也可以。
|
j********e
发帖数: 1192 | 18 如果记录parent编号，文件大小上没区别。
不过重建树的时候，你怎么根据parent编号找parent？
我只想到用个数组(O(N)顺序记录节点，否则从树里面去找还挺麻烦的吧？
【在 w****x 的大作中提到】
:
: 恩,不需要用queue
|
w****o
发帖数: 2260 | 19 第2题中的 n 是事先知道的吗？是不是每个node的n都是一样的? 还是说有的node有4个
children,有的node有8个children?
【在 j********e 的大作中提到】
: 如果记录parent编号，文件大小上没区别。
: 不过重建树的时候，你怎么根据parent编号找parent？
: 我只想到用个数组(O(N)顺序记录节点，否则从树里面去找还挺麻烦的吧？
|
j********e
发帖数: 1192 | 20 n不一样，tree node里可以存
【在 w****o 的大作中提到】
: 第2题中的 n 是事先知道的吗？是不是每个node的n都是一样的? 还是说有的node有4个
: children,有的node有8个children?
|
w****x
发帖数: 2483 | 21 /*
Serialize/DeSerialize a tree
*/
struct NODE
{
int nVal;
vector vec;
NODE(int n) : nVal(n) {}
};
void _inner_serial(NODE* pNode, char*& p)
{
if (NULL == pNode)
return;
*p++ = pNode->vec.size();
*p++ = pNode->nVal;
for (vector::iterator it = pNode->vec.begin();
it != pNode->vec.end(); it++)
_inner_serial(*it, p);
}
const char* Serialize(NODE* pRoot, char mem[])
{
if (NULL == mem || NULL == pRoot)
return NULL;
char* p = mem;
_inner_serial(pRoot, p);
return mem;
}
NODE* _inner_deserial(const char*& p)
{
int n = *p++;
NODE* pRet = new NODE(*p++);
for (int i = 0; i < n; i++)
pRet->vec.push_back(_inner_deserial(p));
return pRet;
}
NODE* DeSerialize(const char mem[])
{
if (NULL == mem)
return NULL;
const char* p = mem;
return _inner_deserial(p);
} |
x*******1
发帖数: 28835 | 22 BFS tab key separate child |
