问: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];
}
anyShare分享到:
Tagged with:
 

2 Responses to “小球称重和O(1)栈问题(sohu2011笔试)”

  1. Anonymous says:

    第一题,第3个步骤是不是多余了?既然是不平衡,那显然就能判断出变轻还是变重了,因为除了受到污染的一个以外,重量都是相等的

    • sponge says:

      @Anonymous 不对哦,只是不平衡的话,你如何知道受污染的在哪一堆中?是重的那堆还是轻的?

Leave a Reply

Note: Commenter is allowed to use '@User+blank' to automatically notify your reply to other commenter. e.g, if ABC is one of commenter of this post, then write '@ABC '(exclude ') will automatically send your comment to ABC. Using '@all ' to notify all previous commenters. Be sure that the value of User should exactly match with commenter's name (case sensitive).