g*******y
发帖数: 1930 | 1 1. sort stack using only pop(), top(), push(), isEmpty(),isFull(). Do not
use any auxiliary stacks or arrays.
感觉不用辅助空间做不到啊，这题是真的有很巧妙的方法？还是玩玩文字游戏--比如用
linked list然后宣称它不是stack也不是array...
2. Given a set of coin denominators, find the minimum number of coins to
give a certain amount of change
贪心和DP,回溯法应该都能做的，无非就是状态空间搜索，但是我想到的都是伪多项式
的算法，感觉这道题应该能利用某些数论的知识在多项式时间解决? | k*k
发帖数: 49 | 2 1. sort stack using only pop(), top(), push(), isEmpty(),isFull(). Do not
use any auxiliary stacks or arrays.
use the function call stack for temporary storage... O(n^2) i guess.
你想多了。。。 :) | a*****e
发帖数: 51 | 3 1. Yes you can do it, if you can use system stack.
【在 g*******y 的大作中提到】
: 1. sort stack using only pop(), top(), push(), isEmpty(),isFull(). Do not
: use any auxiliary stacks or arrays.
: 感觉不用辅助空间做不到啊，这题是真的有很巧妙的方法？还是玩玩文字游戏--比如用
: linked list然后宣称它不是stack也不是array...
: 2. Given a set of coin denominators, find the minimum number of coins to
: give a certain amount of change
: 贪心和DP,回溯法应该都能做的，无非就是状态空间搜索，但是我想到的都是伪多项式
: 的算法，感觉这道题应该能利用某些数论的知识在多项式时间解决?
| t********e
发帖数: 25 | 4 Bubble sort recursively?
SortStack(stack s)
{
if s.notEmpty()
{
x = s.pop();
if( x < s.top() )
{ newx = s.pop() ;
s.push(x);
x = newx;
}
SortStack(s);
s.push(x);
}
}
Call this n times. |
|
