j**l
发帖数: 2911 | 1 写一个stack, Push, Pop和GetMin都是O(1)时间
如果在白板上写出如下的代码，能达到面试官的基本要求么？
#define MAX_STACK_SIZE 1000
class Stack
{
int Data[MAX_STACK_SIZE];
int Link[MAX_STACK_SIZE];
int top;
public:
Stack() { top = -1; }
void Push(int x);
int Pop();
int GetMin();
};
void Stack::Push(int x)
{
if ((top + 1) == MAX_STACK_SIZE)
{
printf("Push failed, the stack is full.\n");
return;
}
int min_link = 0;
if (top > -1)
{
min_link = Link[top];
if |
y**i
发帖数: 1112 | 2 贴一个我的，正好前几天也写了一个：
template
class Stack
{
T* val;
T* min;
int max_size;
int top;
public:
class Underflow { };
class Overflow { };
Stack() : max_size(1000), top(0) { val = new int[max_size]; min = new
int[max_size]; }
Stack(int s) : max_size(s), top(0) { val = new int[max_size]; min = new
int[max_size]; }
~Stack() { delete[] val; delete[] min; }
void Push(T t);
T Pop();
T GetMin();
};
template void Stack::Push(T t)
{
if (top |
T*****9
发帖数: 2484 | 3 这是传说中的C/C++么。。。
【在 j**l 的大作中提到】
: 写一个stack, Push, Pop和GetMin都是O(1)时间
: 如果在白板上写出如下的代码，能达到面试官的基本要求么？
: #define MAX_STACK_SIZE 1000
: class Stack
: {
: int Data[MAX_STACK_SIZE];
: int Link[MAX_STACK_SIZE];
: int top;
: public:
: Stack() { top = -1; }
|
j**l
发帖数: 2911 | 4 看去不错，不过你的top，实际上是指向栈顶元素的上一个位置吧，这种用法不太符合
一般人的习惯。
另外用模板比较好，但为了方便应该可以用int写，然后再和面试官说可以用模板来支
持各种类型吧？
用异常也比较好。
白板的空间有限，时间也有限，如果写得太全太细，肯定会遇到费马的难处：这里边缘
太小，写不下。
是不是可以像我贴的代码那样尽量简化问题写，比如用int代替模板，用printf代替异
常，然后再和面试官提到模板和异常的技术？
【在 y**i 的大作中提到】
: 贴一个我的，正好前几天也写了一个：
: template
: class Stack
: {
: T* val;
: T* min;
: int max_size;
: int top;
: public:
: class Underflow { };
|
j**l
发帖数: 2911 | 5 你的方法是直接保存min的值，而不是序号，虽然免去了间接访问，但是空间可能要多
用一些吧？比如T的类型是double, 则min数组用的类型也是double，如果用序号的话就
可以固定min数组的类型为int了
【在 y**i 的大作中提到】
: 贴一个我的，正好前几天也写了一个：
: template
: class Stack
: {
: T* val;
: T* min;
: int max_size;
: int top;
: public:
: class Underflow { };
|
j**l
发帖数: 2911 | 6 请教下，这种混合的写法是面试的大忌么？
【在 T*****9 的大作中提到】
: 这是传说中的C/C++么。。。
|
g**********1
发帖数: 1113 | 7 Do not use any magic number.
【在 y**i 的大作中提到】
: 贴一个我的，正好前几天也写了一个：
: template
: class Stack
: {
: T* val;
: T* min;
: int max_size;
: int top;
: public:
: class Underflow { };
|
r****o
发帖数: 1950 | 8 what is magic number? 常数么?
\\
【在 g**********1 的大作中提到】
: Do not use any magic number.
|
g**********1
发帖数: 1113 | 9 Do not use template. Many problems may happen. |
T*****9
发帖数: 2484 | 10 恩
1000这种最好用define
【在 r****o 的大作中提到】
: what is magic number? 常数么?
: \\
|
d****g
发帖数: 33 | 11 感觉用链表+异常处理可能会好一点。数组模式不具备扩展性。
如果恶心一点，直接用deque。当然这样子不能给面试人员深刻印象。 |
