问：101个榛子，每个重量都相等。有一天其中一个受到污染了，不知道变重还是变轻了，给一个天平，请问至少要称几次才能确定是变轻了还是变重了？
答案：

1. 先取出一个，然后将剩下的等分成两份，没份50个；
2. 将两份放到天平，如果重量相等，则说明被选出的那一个是受到污染的，将受到污染的同其他的任意一个比较，就能够得出答案。
3. 如果天平不平衡，将重的一边再分成两份，每份25个，放到天平上，如果平衡，则说明受污染的在另外50个中，而另一份比较轻，所以受污染的比较轻。相反，如果不平衡，则说明受污染的在当前的50个中，则说明受污染的变重了。

所以，本题答案是2次。

第二个题目：设计一个栈，pop()和push()操作的时间复杂度都是O(1)，并且能在O(1)时间内获得栈中最小元素。

答案：用两个栈来解决这个问题，一个是正常的栈stack1，push时压入，pop时弹出。另外一个栈stack2用来存放最小的元素，每次push操作的时候，如果stack2为空，则将元素压入stack2；如果不为空，则比较stack2栈顶元素和压入元素，如果小于要压入的元素，则不操作；如果大于，则压入该元素。执行pop时，比较stack1和stack2的栈顶元素是否相等，如果相等，则都出栈，不相等，则只有stack1出栈。这样就可以时刻保持stack2的栈顶元素是stack1所有元素中最小的元素，并且如果stack1中最小元素被pop掉，stack2仍然能保证给出最小元素。用C语言描述如下：

int stack1[MAX];
int stack2[MAX];
int top1, top2;//分别是两个栈的栈顶指针
 
void push(int a){
    if(top1 >= MAX){
        printf("Stack Full!\n");
        return;
    }
    stack1[top1] = a;
    top1 ++;
    if(top2 == 0){ //如果stack2为空，则压入stack2
        stack2[top2] = a;
        top2 ++;
     }
    else if(a <= stack2[top2-1]){
        stack2[top2] = a;
        top2 ++;
    }
     return ;
}
 
int pop(){
    if(top1 <= 0 ){
        printf("Empty Stack!!\n");
        return -1;
    }
    if(stack1[top1] == stack2[top2]) //如果两个栈顶元素相等
        top2 --;
    return stack1[--top1];
}
 
int getmin(){
    return stack2[top2 - 1];
}