H*M
发帖数: 1268 | 1 职业杯上拷来的
觉得不错。不是那么难，但是也很巧妙。
given a file with heirarchial input like below.. create xml representation..
a.b.c=1
a.b.d=4
a.e=6
input can be assumed to be sorted and is heirarchial in nature.
output should look like
146
asked general algorithm and approach. |
k***e
发帖数: 556 | 2 这个 知道shared prefix length貌似就可以了啊
看看那道边界是黑的最大矩形的题目
..
【在 H*M 的大作中提到】
: 职业杯上拷来的
: 觉得不错。不是那么难，但是也很巧妙。
: given a file with heirarchial input like below.. create xml representation..
: a.b.c=1
: a.b.d=4
: a.e=6
: input can be assumed to be sorted and is heirarchial in nature.
: output should look like
: 146
: asked general algorithm and approach.
|
k***e
发帖数: 556 | 3 难道你是说given an array of sorted strings, find the shared prefix of all
adjacent pairs efficiently? Then, that is tricky. I think I read some
algorithm before
【在 k***e 的大作中提到】
: 这个 知道shared prefix length貌似就可以了啊
: 看看那道边界是黑的最大矩形的题目
:
: ..
|
H*M
发帖数: 1268 | 4 求一个边界是1的最大的内部全是0的矩形？
这个貌似讨论过啊?
【在 k***e 的大作中提到】
: 这个 知道shared prefix length貌似就可以了啊
: 看看那道边界是黑的最大矩形的题目
:
: ..
|
k***e
发帖数: 556 | 5 no, that is a different problem.
i don't care the rectangle is all 0 or 1, I just want its boundaries to be
all 1
【在 H*M 的大作中提到】
: 求一个边界是1的最大的内部全是0的矩形？
: 这个貌似讨论过啊?
|
H*M
发帖数: 1268 | 6 原题在哪啊？？
【在 k***e 的大作中提到】
: no, that is a different problem.
: i don't care the rectangle is all 0 or 1, I just want its boundaries to be
: all 1
|
b****j
发帖数: 78 | 7 can be done in less than 20 lines of python:
import sys
last = []
for line in sys.stdin:
node, data = map(str.strip, line.split('='))
nodes = map(str.strip, node.split('.'))
for i, (s1, s2) in enumerate(map(None, last, nodes)):
if s1 != s2:
if s1:
sys.stdout.write('' % '>
if s2:
sys.stdout.write('<%s>' % '><'.join(nodes[i:]))
break
sys.stdout.write(data)
last = last[:i] + nodes[i:]
if last:
print '' % '>
【在 H*M 的大作中提到】
: 职业杯上拷来的
: 觉得不错。不是那么难，但是也很巧妙。
: given a file with heirarchial input like below.. create xml representation..
: a.b.c=1
: a.b.d=4
: a.e=6
: input can be assumed to be sorted and is heirarchial in nature.
: output should look like
: 146
: asked general algorithm and approach.
|
m*****f
发帖数: 1243 | 8 职业杯上就有
【在 H*M 的大作中提到】
: 原题在哪啊？？
|
r**u
发帖数: 1567 | 9 你可以build a tree。然后postfix traverse tree，第一次走到这个节点printf
，当左右子树都遍历过了，就printf<\x>。当然，leaf节点要printf number。
a
/ \
b e
/ \ 6
c d
1 4
..
【在 H*M 的大作中提到】
: 职业杯上拷来的
: 觉得不错。不是那么难，但是也很巧妙。
: given a file with heirarchial input like below.. create xml representation..
: a.b.c=1
: a.b.d=4
: a.e=6
: input can be assumed to be sorted and is heirarchial in nature.
: output should look like
: 146
: asked general algorithm and approach.
|
c*****o
发帖数: 178 | 10 这个方法好，就是有一点，每个node可能不止左右两个子树，应该可以有若干个子树。
所以应该是从左到右把这个node的所有子树都遍历一遍。
【在 r**u 的大作中提到】
: 你可以build a tree。然后postfix traverse tree，第一次走到这个节点printf
: ，当左右子树都遍历过了，就printf<\x>。当然，leaf节点要printf number。
: a
: / \
: b e
: / \ 6
: c d
: 1 4
:
: ..
|
H*M
发帖数: 1268 | 11 职业杯上的题是这样的:
Imagine you have a square matrix, where each cell is filled with either blac
k or white. Design an algorithm to find the maximum subsquare such that all
four borders are filled with black pixels.
不过按他的算法,我觉得是O(n^4)而不是O(n^2):
1. iterate each full column ->n
2. iterate each sub column -> n^2
3. check if it can form a sqaure ->n
total O(n^4)
第三步可以用2n个interval tree记录每行每列的连续0的起始index,这样第三步就省到
lgn,总共可以O(n^3.lgn).
【在 m*****f 的大作中提到】
: 职业杯上就有
|
P**********0
发帖数: 412 | 12 是inorder traversal 吗？
【在 c*****o 的大作中提到】
: 这个方法好，就是有一点，每个node可能不止左右两个子树，应该可以有若干个子树。
: 所以应该是从左到右把这个node的所有子树都遍历一遍。
|
c*****o
发帖数: 178 | 13 先node，再children nodes。这个是preoder吧？不好意思，我这些专业的术语不太会
说。inorder应该是left-root-right。如果不是Binary tree,不知道还有没有inoder。
【在 P**********0 的大作中提到】
: 是inorder traversal 吗？
|
