宅男宅女们----四楼上片片 - 未名空间MITBBS历史存档

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

Redian新闻

>未名空间

>pets - 心有所宠

宅男宅女们----四楼上片片

宅男宅女们----四楼上片片# pets - 心有所宠

g*r2011-10-29 07:10

1 楼

给一个数组，判定是否可能是一个BST后序遍历得到的
这题大家啥思路？

H*72011-10-29 07:10

2 楼

All Posters Coupon: 20% off $15 or More Including Clearance: 6 posters for $
14 + Free Shipping
All Posters.com Coupons & Deals Buy Now ►
AllPosters.com offers an additional 20% off on top of their already-reduced
Clearance Prices when you spend $15 or more and apply coupon code DEGASV at
checkout. Some of the Posters end up being just $2.39 each when you purchase
6 or more. Shipping is free with this coupon code. Thanks shootkey

b*s2011-10-29 07:10

3 楼

外面秋光正好，姐姐我上街溜达去了！
这个时候就觉得养狗好啊，秋高气爽，正是牵狗漫步的好时候....

v*u2011-10-29 07:10

4 楼

粗略一想怎么觉得任何一个数组都可能啊?

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

: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？

d*n2011-10-29 07:10

5 楼

我要买。coupon哪里搞？
谢谢

N*t2011-10-29 07:10

6 楼

在家养病中 =((((((

l*82011-10-29 07:10

7 楼

试试 8 3 7

【在 v*****u 的大作中提到】

: 粗略一想怎么觉得任何一个数组都可能啊?

H*72011-10-29 07:10

8 楼

code DEGASV

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

: 我要买。coupon哪里搞？
: 谢谢

i*i2011-10-29 07:10

9 楼

外面大雪纷飞，我穿成皮球，准备出门party去了

d*e2011-10-29 07:10

10 楼

这样行不行？
1. array[n-1]为root
2. 遍历数组，看能不能找到两个subarray, 第一个root
3. 如果2为false返回false，否则去4
4. 对两个subarray递归操作1,2,3

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

: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？

t*e2011-10-29 07:10

11 楼

谢谢谢谢，这就去看看。

$
reduced
at
purchase

【在 H******7 的大作中提到】

: All Posters Coupon: 20% off $15 or More Including Clearance: 6 posters for $
: 14 + Free Shipping
: All Posters.com Coupons & Deals Buy Now ►
: AllPosters.com offers an additional 20% off on top of their already-reduced
: Clearance Prices when you spend $15 or more and apply coupon code DEGASV at
: checkout. Some of the Posters end up being just $2.39 each when you purchase
: 6 or more. Shipping is free with this coupon code. Thanks shootkey

b*s2011-10-29 07:10

12 楼

拍拍，穿够暖，多睡觉，快点好----最后两张送给你
前两张是今天在街头拍的老虎狗，叫Maxx。这美国叫Maxx的宠物不要太多。
好乖的，主人在里面看电视聊天，他就趴在门口。因为太多人pet他了，主人
于是贴了他的名字在台阶上，这狗就有自己固定的位置了！老虎狗的脾气真好啊，象个
大阿福！

【在 N******t 的大作中提到】

: 在家养病中 =((((((

l*82011-10-29 07:10

13 楼

这样是可以的，只是简单实现的话，时间复杂度是O(n^2).
这道题目应该在 O(n)

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

: 这样行不行？
: 1. array[n-1]为root
: 2. 遍历数组，看能不能找到两个subarray, 第一个root
: 3. 如果2为false返回false，否则去4
: 4. 对两个subarray递归操作1,2,3

k*n2011-10-29 07:10

14 楼

不错。。

N*t2011-10-29 07:10

15 楼

awwwwwwwwwwww 看到小猫就好了一半了
这只狗，血红的眼睛和血盆大口。。。orz

【在 b******s 的大作中提到】

: 拍拍，穿够暖，多睡觉，快点好----最后两张送给你
: 前两张是今天在街头拍的老虎狗，叫Maxx。这美国叫Maxx的宠物不要太多。
: 好乖的，主人在里面看电视聊天，他就趴在门口。因为太多人pet他了，主人
: 于是贴了他的名字在台阶上，这狗就有自己固定的位置了！老虎狗的脾气真好啊，象个
: 大阿福！

l*a2011-10-29 07:10

16 楼

O(nlogn)吧，跟quick sort一样
let me think how to implement O(n)

【在 l*********8 的大作中提到】

: 这样是可以的，只是简单实现的话，时间复杂度是O(n^2).
: 这道题目应该在 O(n)

l*82011-10-29 07:10

17 楼

能不能说说O(nlogn)的算法?

【在 l*****a 的大作中提到】

: O(nlogn)吧，跟quick sort一样
: let me think how to implement O(n)

l*a2011-10-29 07:10

18 楼

我说done的算法似乎就是。跟二分/quick sort思路一样吧
倒是你的O(n)，看起来需要其他data structure support,不那么容易

【在 l*********8 的大作中提到】

: 能不能说说O(nlogn)的算法?

l*82011-10-29 07:10

19 楼

你说的对，done的算法，平均时间复杂度是O(nlogn)
不过，跟基本的quick sort一样，最差时间复杂度也O(n^2).
比如 1 2 3 4 5 6 7 8
我之前只想了这个例子，就误以为算法时间复杂度是O(n^2)了：）

【在 l*****a 的大作中提到】

: 我说done的算法似乎就是。跟二分/quick sort思路一样吧
: 倒是你的O(n)，看起来需要其他data structure support,不那么容易

l*82011-10-29 07:10

20 楼

说说我的想法：
从末尾向前扫描，试图建立一棵BST （不一定要真正建立树结构）
当前节点A[idx]是当前子树的根，同时也维护当前子树的合法数值范围[min_val, max_
val]. 初始数值范围是 [INT_MIN, INT_MAX]。进入A[idx]的右子树，数值范围就是[
A[idx], old max_val]; 左子树范围是[old min_val, A[idx]]
对于A[idx-1],
如果比A[idx]大，就放到试图放到右子树里面，如果不能满足数值范围, 就返回parent
节点再试。
如果 <= A[idx]，就放到试图放到左子树里面，如果不能, 就返回parent节点再试。
这样一遍扫描数组, 如果所有数值都能合法放进BST，就返回true, 否则false。

l*a2011-10-29 07:10

21 楼

我同意你扫描一遍inout array就可以完成
问题是对于其中某个/些值，有可能需要在当前路径上回溯来判断需要插在哪个位置
所以我不认为这是O(n)

max_
是[
parent

【在 l*********8 的大作中提到】

: 说说我的想法：
: 从末尾向前扫描，试图建立一棵BST （不一定要真正建立树结构）
: 当前节点A[idx]是当前子树的根，同时也维护当前子树的合法数值范围[min_val, max_
: val]. 初始数值范围是 [INT_MIN, INT_MAX]。进入A[idx]的右子树，数值范围就是[
: A[idx], old max_val]; 左子树范围是[old min_val, A[idx]]
: 对于A[idx-1],
: 如果比A[idx]大，就放到试图放到右子树里面，如果不能满足数值范围, 就返回parent
: 节点再试。
: 如果 <= A[idx]，就放到试图放到左子树里面，如果不能, 就返回parent节点再试。
: 这样一遍扫描数组, 如果所有数值都能合法放进BST，就返回true, 否则false。

l*82011-10-29 07:10

22 楼

这个方法类似二叉树遍历，二叉树遍历也有路径回溯，但还是O(n)的算法。

【在 l*****a 的大作中提到】

: 我同意你扫描一遍inout array就可以完成
: 问题是对于其中某个/些值，有可能需要在当前路径上回溯来判断需要插在哪个位置
: 所以我不认为这是O(n)
:
: max_
: 是[
: parent

f*e2011-10-29 07:10

23 楼

满足两个条件即可：
1.每个上升序列的第二个元素大于该元素左边所有的元素
2.对于每两个下降序列D1,D2,要么D1和D2互不重叠，要么D1 contains D2，or D2 cont
ains D1，i.e (min(D1), max(D1))包含在D2的某个interval中或相反。

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

: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？

p*22011-10-29 07:10

24 楼

post order, 最后一个值是root
从开始扫，比root小的是左树，后边的就是右树了，应该都比root的值大。
recursion就可以了吧？这是最straightforward的思路了。

g*r2011-10-29 07:10

25 楼

我也是这个思路啊，但这个是O(n*n)的worst case,再想有没有O(n)的好的解法。

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

: post order, 最后一个值是root
: 从开始扫，比root小的是左树，后边的就是右树了，应该都比root的值大。
: recursion就可以了吧？这是最straightforward的思路了。

l*82011-10-29 07:10

26 楼

我的思路就是O(n)的。

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

: 我也是这个思路啊，但这个是O(n*n)的worst case,再想有没有O(n)的好的解法。

l*82011-10-29 07:10

27 楼

贴个代码吧：
int scanPostOrder(int *A, int idx, int minVal, int maxVal)
{
if (idx < 0 || A[idx] < minVal || A[idx] > maxVal)
return idx; //如果不能满足数值范围,或者已经扫描完毕，就返回到父节点
int val = A[idx];
idx = scanPostOrder(A, idx-1, val, maxVal); // 右子树
return scanPostOrder(A, idx, minVal, val); // 左子树
}
bool checkPostOrder(int *A, int n)
{
return scanPostOrder(A, n-1, INT_MIN, INT_MAX) < 0;
}

【在 l*********8 的大作中提到】

: 我的思路就是O(n)的。

p*22011-10-29 07:10

28 楼

我感觉可以从右往前找。应该O(n)了吧？

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

: 我也是这个思路啊，但这个是O(n*n)的worst case,再想有没有O(n)的好的解法。

f*e2011-10-29 07:10

29 楼

不错，我的也是O(N)，不过没有你这个直观。

【在 l*********8 的大作中提到】

: 贴个代码吧：
: int scanPostOrder(int *A, int idx, int minVal, int maxVal)
: {
: if (idx < 0 || A[idx] < minVal || A[idx] > maxVal)
: return idx; //如果不能满足数值范围,或者已经扫描完毕，就返回到父节点
: int val = A[idx];
: idx = scanPostOrder(A, idx-1, val, maxVal); // 右子树
: return scanPostOrder(A, idx, minVal, val); // 左子树
: }
: bool checkPostOrder(int *A, int n)

l*82011-10-29 07:10

30 楼

请问你的算法、程序是怎么样的？

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

: 不错，我的也是O(N)，不过没有你这个直观。

l*82011-10-29 07:10

31 楼

恩，好像你的start一直都是0.

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

:
: 我感觉可以从右往前找。应该O(n)了吧？

p*22011-10-29 07:10

32 楼

你那个逻辑抽象的很好。我的思路跟你差不多，不过code复杂多了。其实就是你那个
code最好。

【在 l*********8 的大作中提到】

: 恩，好像你的start一直都是0.

p*22011-10-29 07:10

33 楼

这题又一次显示了longway的最简洁code 的超能力。

l*82011-10-29 07:10

34 楼

谢谢二爷夸奖
但我写得慢啊。对于没见过的题，要在二十多分钟乃至更短的时间里思考算法并写出
程序，我能凑出一个来就不错了，别谈简洁了。我多多练习吧

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

: 这题又一次显示了longway的最简洁code 的超能力。

e*e2011-10-29 07:10

35 楼

My code, da niu zhi dian. Thanks.
public boolean checkPostorder(int[] A) {
return checkPostorderCore( A, 0, A.length-1);
}
boolean checkPostorderCore(int[] A, int s, int e) {
if ( s == e || s + 1 == e )
return true;
int value = A[e];
int i = s;
for ( ; i < e; i++ ) {
if ( A[i] > value )
break;
}
if ( i == e || i == s )
return false;
i--;
return checkPostorderCore(A, s, i) && checkPostorderCore(A, i+1, e-1);
}

p*22011-10-29 07:10

36 楼

不要谦虚了。我觉得你做到你这一步，已经不是时间的问题了，完全是实力的体现。追
求精益求精的精神也十分罕见。
你说的面试20分钟写好bug free的code一般是做过这题，或者做过类似的题。这也是为
什么要搞题海战术了。如果一道比较难的新题，除了那些ACMer，一般可能都不会做的
很顺利。能把code写完整，没有什么bug就已经很不错了。

【在 l*********8 的大作中提到】

: 谢谢二爷夸奖
: 但我写得慢啊。对于没见过的题，要在二十多分钟乃至更短的时间里思考算法并写出
: 程序，我能凑出一个来就不错了，别谈简洁了。我多多练习吧

l*82011-10-29 07:10

37 楼

谢谢二爷鼓励！
我要多做题目，题海战术。

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

:
: 不要谦虚了。我觉得你做到你这一步，已经不是时间的问题了，完全是实力的体现。追
: 求精益求精的精神也十分罕见。
: 你说的面试20分钟写好bug free的code一般是做过这题，或者做过类似的题。这也是为
: 什么要搞题海战术了。如果一道比较难的新题，除了那些ACMer，一般可能都不会做的
: 很顺利。能把code写完整，没有什么bug就已经很不错了。

l*82011-10-29 07:10

38 楼

请测试下面两个合法的post order系列：
1 2 3 4
4 3 2 1

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

: My code, da niu zhi dian. Thanks.
: public boolean checkPostorder(int[] A) {
: return checkPostorderCore( A, 0, A.length-1);
: }
: boolean checkPostorderCore(int[] A, int s, int e) {
: if ( s == e || s + 1 == e )
: return true;
: int value = A[e];
: int i = s;
: for ( ; i < e; i++ ) {

w*o2011-10-29 07:10

39 楼

来一个不递归的：
boolean validate(int[] A) {
//int[] A = {4,3,2,1};

Stack s = new Stack();
int max = Integer.MAX_VALUE;
for(int i = A.length - 1; i >= 0; i--) {
int x = A[i];
if(x > max) {
return false;
}
while(!s.empty() && x < s.peek()) {
max = s.pop();
}
s.push(x);
}
return true;
}

g*u2011-10-29 07:10

40 楼

我觉得你的算法是对的. 一个小优化是找两个subarray的分界点可以用二分查找. 但是
在递归过程中必须维护当前子树的值的上下界,一旦越界就报错. 我觉得不值得这么折
腾.
还有一个办法就是反向读数组, 然后重建BST. 每读一个数都应该可以找到二叉树中唯
一插入的位置, 如果找不到的话就报错. 但是找插入位置的过程的复杂度至少是树的高
度,也就是O(log N), 所以总体还是O(N logN), 实现的复杂度就差多了.

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

: 这样行不行？
: 1. array[n-1]为root
: 2. 遍历数组，看能不能找到两个subarray, 第一个root
: 3. 如果2为false返回false，否则去4
: 4. 对两个subarray递归操作1,2,3

s*l2011-10-29 07:10

41 楼

http://fayaa.com/code/view/27365/

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

: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？

s*l2011-10-29 07:10

42 楼

引申问题：
给一个从1到N的排列，可能是一个BST后序遍历的概率是多少?

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

: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？

k*r2011-10-29 07:10

43 楼

厉害啊，
要是我在面试时遇到这个题，我就会
1,建立树，
2,in order读树，
3,判断是不是递增。
不会想到您这个方法。

【在 l*********8 的大作中提到】

l*82011-10-29 07:10

44 楼

编程序算？还是写出数学解析表达式（不是递推式）？

【在 s*********l 的大作中提到】

:
: 引申问题：
: 给一个从1到N的排列，可能是一个BST后序遍历的概率是多少?

s*l2011-10-29 07:10

45 楼

有解析表达式最好，能给出递推公式就足够好，用程序模拟也可以。

【在 l*********8 的大作中提到】

: 编程序算？还是写出数学解析表达式（不是递推式）？

b*n2011-10-29 07:10

46 楼

是不是 C(n) / n!, in which C(n) is Catalan number of n.

【在 s*********l 的大作中提到】

: 有解析表达式最好，能给出递推公式就足够好，用程序模拟也可以。

f*p2011-10-29 07:10

47 楼

递归可以解。如果是后序遍历结果，最后一个数x一定是根节点。前面比x小的是左子树
，比x大的是右子树，这个位置可以二分法查找。左右子树可以递归判断。复杂度是n
log n吧。

f*e2011-10-29 07:10

48 楼

有兴趣的话，可以把longway的那个条件语句里设个static variable++试试看。

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

: 递归可以解。如果是后序遍历结果，最后一个数x一定是根节点。前面比x小的是左子树
: ，比x大的是右子树，这个位置可以二分法查找。左右子树可以递归判断。复杂度是n
: log n吧。

Q*e2011-10-29 07:10

49 楼

贴一个实现.
int
validate_postorder(int nums[], int start, int end)
{
int i, j;
if (start >= end) return 1;
i = start;
while (i < end && nums[i] < nums[end]) i++;
i--;
j = end - 1;
while (j >= start && nums[j] > nums[end]) j--;
j++;
if (i + 1 < j) {
return (0);
} else {
return (validate_postorder(nums, start, i) &&
validate_postorder(nums, j, end-1)) ;
}
}

s*l2011-10-29 07:10

50 楼

应该是对的！

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

: 是不是 C(n) / n!, in which C(n) is Catalan number of n.