l*****l
发帖数: 171 | 1 俺在 JOBHUNTING 做的一道题, 不知是否正确, 请大虾验证!
Design an efficient algorithm to sort elements in a stack in either
ascending/descending order, using only pop(), top(), push(), isEmpty(),
isFull(). Do not use any auxiliary stacks or arrays.
How about this? | l*****l
发帖数: 171 | 2 俺优化以下:
void sort(stack &s, int numSorted)
{
element *e1;
element *e2;
if (s.size() <= 1+numSorted) {
return;
}
e1 = s.pop();
if(e1 < s.top()) {
e2 = s.pop();
s.push(e1);
sort(s);
s.push(e2);
} else {
sort(s);
s.push(e1);
}
}
【在 l*****l 的大作中提到】
: 俺在 JOBHUNTING 做的一道题, 不知是否正确, 请大虾验证!
: Design an efficient algorithm to sort elements in a stack in either
: ascending/descending order, using only pop(), top(), push(), isEmpty(),
: isFull(). Do not use any auxiliary stacks or arrays.
: How about this?
| q*c
发帖数: 9453 | 3 这个是 meaningless...用的内存比全部新开 array 多，
效率低下， 不知道这题目为啥。而且 sort(stack)
函数也没定义， 不知道咋运行。
这个题目一定要多余的内存，否则罪底下那个元素无法出来。
【在 l*****l 的大作中提到】
: 俺优化以下:
: void sort(stack &s, int numSorted)
: {
: element *e1;
: element *e2;
: if (s.size() <= 1+numSorted) {
: return;
: }
: e1 = s.pop();
: if(e1 < s.top()) {
| c*****t
发帖数: 1879 | 4 the only minor problem i see is that size () is not provided.
【在 l*****l 的大作中提到】
: 俺在 JOBHUNTING 做的一道题, 不知是否正确, 请大虾验证!
: Design an efficient algorithm to sort elements in a stack in either
: ascending/descending order, using only pop(), top(), push(), isEmpty(),
: isFull(). Do not use any auxiliary stacks or arrays.
: How about this?
| l*****l
发帖数: 171 | 5 I think I can use isEmpty()/isFull():)
【在 c*****t 的大作中提到】
: the only minor problem i see is that size () is not provided.
| P*****f
发帖数: 2272 | 6 多余内存在递归的程序stack上
所以这个题有点好玩:不能用辅助栈，但是可以用程序调用的栈
嘿嘿
这个是 meaningless...用的内存比全部新开 array 多，
效率低下， 不知道这题目为啥。而且 sort(stack)
函数也没定义， 不知道咋运行。
这个题目一定要多余的内存，否则罪底下那个元素无法出来。
【在 q*c 的大作中提到】
: 这个是 meaningless...用的内存比全部新开 array 多，
: 效率低下， 不知道这题目为啥。而且 sort(stack)
: 函数也没定义， 不知道咋运行。
: 这个题目一定要多余的内存，否则罪底下那个元素无法出来。
| l*****l
发帖数: 171 | 7 这个也就是面世题, 没有实际意义. 如果有N个数, 要做N层RECURSION.
N必须很小才行.
【在 P*****f 的大作中提到】
: 多余内存在递归的程序stack上
: 所以这个题有点好玩:不能用辅助栈，但是可以用程序调用的栈
: 嘿嘿
:
: 这个是 meaningless...用的内存比全部新开 array 多，
: 效率低下， 不知道这题目为啥。而且 sort(stack)
: 函数也没定义， 不知道咋运行。
: 这个题目一定要多余的内存，否则罪底下那个元素无法出来。
| s*******d
发帖数: 59 | |
|
