g*******r
发帖数: 44 | 1 给一个数组，判定是否可能是一个BST后序遍历得到的
这题大家啥思路？ |
v*****u
发帖数: 1796 | 2 粗略一想怎么觉得任何一个数组都可能啊?
【在 g*******r 的大作中提到】
: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？
|
l*********8
发帖数: 4642 | 3 试试 8 3 7
【在 v*****u 的大作中提到】
: 粗略一想怎么觉得任何一个数组都可能啊?
|
d**e
发帖数: 6098 | 4 这样行不行？
1. array[n-1]为root
2. 遍历数组，看能不能找到两个subarray, 第一个root
3. 如果2为false返回false，否则去4
4. 对两个subarray递归操作1,2,3
【在 g*******r 的大作中提到】
: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？
|
l*********8
发帖数: 4642 | 5 这样是可以的，只是简单实现的话，时间复杂度是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
|
l*****a
发帖数: 14598 | 6 O(nlogn)吧，跟quick sort一样
let me think how to implement O(n)
【在 l*********8 的大作中提到】
: 这样是可以的，只是简单实现的话，时间复杂度是O(n^2).
: 这道题目应该在 O(n)
|
l*********8
发帖数: 4642 | 7 能不能说说O(nlogn)的算法?
【在 l*****a 的大作中提到】
: O(nlogn)吧，跟quick sort一样
: let me think how to implement O(n)
|
l*****a
发帖数: 14598 | 8 我说done的算法似乎就是。跟二分/quick sort思路一样吧
倒是你的O(n)，看起来需要其他data structure support,不那么容易
【在 l*********8 的大作中提到】
: 能不能说说O(nlogn)的算法?
|
l*********8
发帖数: 4642 | 9 你说的对，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*********8
发帖数: 4642 | 10 说说我的想法：
从末尾向前扫描，试图建立一棵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*****a
发帖数: 14598 | 11 我同意你扫描一遍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*********8
发帖数: 4642 | 12 这个方法类似二叉树遍历， 二叉树遍历也有路径回溯，但还是O(n)的算法。
【在 l*****a 的大作中提到】
: 我同意你扫描一遍inout array就可以完成
: 问题是对于其中某个/些值，有可能需要在当前路径上回溯来判断需要插在哪个位置
: 所以我不认为这是O(n)
:
: max_
: 是[
: parent
|
f*****e
发帖数: 2992 | 13 满足两个条件即可：
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*****2
发帖数: 21240 | 14 post order, 最后一个值是root
从开始扫，比root小的是左树，后边的就是右树了，应该都比root的值大。
recursion就可以了吧？这是最straightforward的思路了。 |
g*******r
发帖数: 44 | 15 我也是这个思路啊，但这个是O(n*n)的worst case,再想有没有O(n)的好的解法。
【在 p*****2 的大作中提到】
: post order, 最后一个值是root
: 从开始扫，比root小的是左树，后边的就是右树了，应该都比root的值大。
: recursion就可以了吧？这是最straightforward的思路了。
|
l*********8
发帖数: 4642 | 16 我的思路就是O(n)的。
【在 g*******r 的大作中提到】
: 我也是这个思路啊，但这个是O(n*n)的worst case,再想有没有O(n)的好的解法。
|
l*********8
发帖数: 4642 | 17 贴个代码吧：
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*****2
发帖数: 21240 | 18
我感觉可以从右往前找。应该O(n)了吧？
【在 g*******r 的大作中提到】
: 我也是这个思路啊，但这个是O(n*n)的worst case,再想有没有O(n)的好的解法。
|
f*****e
发帖数: 2992 | 19 不错，我的也是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*********8
发帖数: 4642 | 20 请问你的算法、程序是怎么样的？
【在 f*****e 的大作中提到】
: 不错，我的也是O(N)，不过没有你这个直观。
|
|
|
l*********8
发帖数: 4642 | 21 恩，好像你的start一直都是0.
【在 p*****2 的大作中提到】
:
: 我感觉可以从右往前找。应该O(n)了吧？
|
p*****2
发帖数: 21240 | 22
你那个逻辑抽象的很好。我的思路跟你差不多，不过code复杂多了。其实就是你那个
code最好。
【在 l*********8 的大作中提到】
: 恩，好像你的start一直都是0.
|
p*****2
发帖数: 21240 | 23 这题又一次显示了longway的最简洁code 的超能力。 |
l*********8
发帖数: 4642 | 24 谢谢二爷夸奖
但我写得慢啊。 对于没见过的题，要在二十多分钟乃至更短的时间里思考算法并写出
程序，我能凑出一个来就不错了，别谈简洁了。 我多多练习吧
【在 p*****2 的大作中提到】
: 这题又一次显示了longway的最简洁code 的超能力。
|
e****e
发帖数: 418 | 25 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*****2
发帖数: 21240 | 26
不要谦虚了。我觉得你做到你这一步，已经不是时间的问题了，完全是实力的体现。追
求精益求精的精神也十分罕见。
你说的面试20分钟写好bug free的code一般是做过这题，或者做过类似的题。这也是为
什么要搞题海战术了。如果一道比较难的新题，除了那些ACMer，一般可能都不会做的
很顺利。能把code写完整，没有什么bug就已经很不错了。
【在 l*********8 的大作中提到】
: 谢谢二爷夸奖
: 但我写得慢啊。 对于没见过的题，要在二十多分钟乃至更短的时间里思考算法并写出
: 程序，我能凑出一个来就不错了，别谈简洁了。 我多多练习吧
|
l*********8
发帖数: 4642 | 27 谢谢二爷鼓励！
我要多做题目，题海战术。
【在 p*****2 的大作中提到】
:
: 不要谦虚了。我觉得你做到你这一步，已经不是时间的问题了，完全是实力的体现。追
: 求精益求精的精神也十分罕见。
: 你说的面试20分钟写好bug free的code一般是做过这题，或者做过类似的题。这也是为
: 什么要搞题海战术了。如果一道比较难的新题，除了那些ACMer，一般可能都不会做的
: 很顺利。能把code写完整，没有什么bug就已经很不错了。
|
l*********8
发帖数: 4642 | 28 请测试下面两个合法的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***o
发帖数: 109 | 29 来一个不递归的：
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****u
发帖数: 252 | 30 我觉得你的算法是对的. 一个小优化是找两个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*********l
发帖数: 103 | 31
http://fayaa.com/code/view/27365/
【在 g*******r 的大作中提到】
: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？
|
s*********l
发帖数: 103 | 32
引申问题：
给一个从1到N的排列，可能是一个BST后序遍历的概率是多少?
【在 g*******r 的大作中提到】
: 给一个数组，判定是否可能是一个BST后序遍历得到的
: 这题大家啥思路？
|
k****r
发帖数: 807 | 33 厉害啊，
要是我在面试时遇到这个题，我就会
1,建立树，
2,in order读树，
3,判断是不是递增。
不会想到您这个方法。
【在 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*********8
发帖数: 4642 | 34 编程序算？还是写出数学解析表达式（不是递推式）？
【在 s*********l 的大作中提到】
:
: 引申问题：
: 给一个从1到N的排列，可能是一个BST后序遍历的概率是多少?
|
s*********l
发帖数: 103 | 35 有解析表达式最好，能给出递推公式就足够好，用程序模拟也可以。
【在 l*********8 的大作中提到】
: 编程序算？还是写出数学解析表达式（不是递推式）？
|
b*****n
发帖数: 143 | 36 是不是 C(n) / n!, in which C(n) is Catalan number of n.
【在 s*********l 的大作中提到】
: 有解析表达式最好，能给出递推公式就足够好，用程序模拟也可以。
|
f******p
发帖数: 4 | 37 递归可以解。如果是后序遍历结果，最后一个数x一定是根节点。前面比x小的是左子树
，比x大的是右子树，这个位置可以二分法查找。左右子树可以递归判断。复杂度是n
log n吧。 |
f*****e
发帖数: 2992 | 38 有兴趣的话，可以把longway的那个条件语句里设个static variable++试试看。
【在 f******p 的大作中提到】
: 递归可以解。如果是后序遍历结果，最后一个数x一定是根节点。前面比x小的是左子树
: ，比x大的是右子树，这个位置可以二分法查找。左右子树可以递归判断。复杂度是n
: log n吧。
|
Q*******e
发帖数: 939 | 39 贴一个实现.
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*********l
发帖数: 103 | 40
应该是对的！
【在 b*****n 的大作中提到】
: 是不是 C(n) / n!, in which C(n) is Catalan number of n.
|
|
|
l*******b
发帖数: 2586 | 41 这个太厉害了，哈哈
【在 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)
|
w****x
发帖数: 2483 | |
f*****e
发帖数: 2992 | 43 这个不能并行化吧？
【在 l*******b 的大作中提到】
: 这个太厉害了，哈哈
|
l*******b
发帖数: 2586 | 44 不能吧，后一步依赖前一步的结果
【在 f*****e 的大作中提到】
: 这个不能并行化吧？
|
z******t
发帖数: 59 | |
