向大家请教一个ebay付款问题，非常感谢！ - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>PhotoGear - 摄影器材

向大家请教一个ebay付款问题，非常感谢！

向大家请教一个ebay付款问题，非常感谢！# PhotoGear - 摄影器材

h*e2010-04-20 07:04

1 楼

一道常见的面试题是print binary tree level by level。
现在有一道反过来的题目，就是给定每一层的结点，构造出
BST来。例如给出以下的vector >：
5
4 8
2 7 9
3 10
要求构造出相应的BST:
5
4 8
2 7 9
3 10
我的想法是可以把输入看作是一个一维的vector，一个个结点
地插入，这样可以得到相应的BST，复杂度是O(NlogN)吧。
问题是这种做法没有利用给出的结点已经分好层的特点，每次都从
根节点开始，似乎不是最有效的。
请问还有更好的办法吗？

r*f2010-04-20 07:04

2 楼

如果在ebay里， make best offer后，卖家也同意了，那还能不能pay的时候调用微软
cashback呢？
我bing出8％的图像后，搜索item number 再点 pay 后，出现了“1 item(s) cannot
be paid because either unpaid
item case(s) were closed or transaction was canceled.” 并且页面右下角无微
软cashback金额，只有一个ebucks的
金额。
谢谢各位高人指点！
谢谢啊

p*22010-04-20 07:04

3 楼

recursion

S*t2010-04-20 07:04

4 楼

不能。bing cashback 只适用 BUY IT NOW
BAOZI

cannot

【在 r*****f 的大作中提到】

: 如果在ebay里， make best offer后，卖家也同意了，那还能不能pay的时候调用微软
: cashback呢？
: 我bing出8％的图像后，搜索item number 再点 pay 后，出现了“1 item(s) cannot
: be paid because either unpaid
: item case(s) were closed or transaction was canceled.” 并且页面右下角无微
: 软cashback金额，只有一个ebucks的
: 金额。
: 谢谢各位高人指点！
: 谢谢啊

h*e2010-04-20 07:04

5 楼

二爷真的是recursion修炼到一字师的地步了。:)
Recursion怎么个做法？

【在 p*****2 的大作中提到】

: recursion

t*32010-04-20 07:04

6 楼

let seller list it again with new price

cannot

【在 r*****f 的大作中提到】

n*n2010-04-20 07:04

7 楼

merge sorted的list啊

【在 h****e 的大作中提到】

: 一道常见的面试题是print binary tree level by level。
: 现在有一道反过来的题目，就是给定每一层的结点，构造出
: BST来。例如给出以下的vector >：
: 5
: 4 8
: 2 7 9
: 3 10
: 要求构造出相应的BST:
: 5
: 4 8

h*e2010-04-20 07:04

8 楼

这个，不行吧，最后生成的是2->3->4->5->...，不是树吧。

【在 n****n 的大作中提到】

: merge sorted的list啊

p*22010-04-20 07:04

9 楼

5
4 8
2 7 9
3 10
我的想法是这样。
5是root
4是left tree
8是right tree
到4的时候数值范围是 Integer.MinValue - 5
左tree的范围 Integer,MinValue - 4
右tree的范围 4-5
这样你就知道2是左tree，这样recursion就可以了。

【在 h****e 的大作中提到】

: 二爷真的是recursion修炼到一字师的地步了。:)
: Recursion怎么个做法？

h*e2010-04-20 07:04

10 楼

这样你是不是需要maintain每一层的所有的结点呢？可能空间要求就
上去了吧。
我的做法如下。这样写的好处是面试时可以写得出来，但是就是不知道
复杂度是不是最优了：
// it is also easy to write an iterative insertion function
void insert_node(Node*& root, int v) {
if (root==0) {
root = new Node(v);
return;
}
if (root->data>v) {
insert_node(root->left, v);
} else {
insert_node(root->right, v);
}
}

Node* construct_tree(vector > nodes)
{
Node* root = 0;
for (int i=0; iconst vector& numbers = nodes[i];
for (int j=0; jinsert_node(root, numbers[j]);
}
}
return root;

}

【在 p*****2 的大作中提到】

:
: 5
: 4 8
: 2 7 9
: 3 10
: 我的想法是这样。
: 5是root
: 4是left tree
: 8是right tree
: 到4的时候数值范围是 Integer.MinValue - 5

p*22010-04-20 07:04

11 楼

怎么maintain？你是说stack的空间？如果不用recursion, BFS也可以。但是时间肯定
不能超过O(n)吧。

【在 h****e 的大作中提到】

: 这样你是不是需要maintain每一层的所有的结点呢？可能空间要求就
: 上去了吧。
: 我的做法如下。这样写的好处是面试时可以写得出来，但是就是不知道
: 复杂度是不是最优了：
: // it is also easy to write an iterative insertion function
: void insert_node(Node*& root, int v) {
: if (root==0) {
: root = new Node(v);
: return;
: }

h*e2010-04-20 07:04

12 楼

二爷有时间的话发一段code吧，我不理解如何在知道4,8以及它们的
子树的取值范围以后处理2,7,9的。

【在 p*****2 的大作中提到】

:
: 怎么maintain？你是说stack的空间？如果不用recursion, BFS也可以。但是时间肯定
: 不能超过O(n)吧。

w*x2010-04-20 07:04

13 楼

top down recursion, recursion下来的函数要传递range

p*22010-04-20 07:04

14 楼

写了一个BFS的。
class Node
{
int value;
Node left;
Node right;
public Node(int v)
{
value = v;
}
}
class Ele
{
int min;
int max;
Node ref;
public Ele(int _min, int _max, Node _ref)
{
min = _min;
max = _max;
ref = _ref;
}
}
Node convert(ArrayList> tree)
{
Queue queue = new LinkedList();
Node root = new Node(tree.get(0).get(0));
queue.add(new Ele(Integer.MIN_VALUE, Integer.MAX_VALUE, root));
int level = 1;
int count = 1;
int i = 0;
while (!queue.isEmpty() && level < tree.size())
{
ArrayList al = tree.get(level);
Ele ele = queue.poll();
if (i < al.size() && al.get(i) >= ele.min
&& al.get(i) <= ele.ref.value)
{
Node left = new Node(al.get(i));
ele.ref.left = left;
queue.add(new Ele(ele.min, ele.ref.value, left));
i++;
}
if (i < al.size() && al.get(i) <= ele.max
&& al.get(i) > ele.ref.value)
{
Node right = new Node(al.get(i));
ele.ref.right = right;
queue.add(new Ele(ele.ref.value, ele.max, right));
i++;
}
count--;
if (count == 0)
{
level++;
count = queue.size();
i = 0;
}
}
return root;
}