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 | |
|