leetcode277--Find the Celebrity--locked

leetcode277--Find the Celebrity--locked

题目

题目的意思是说有n个人,其中最多只有一个是名人,名人指的是,其他所有的人都认识他,但是他不认识其他的任何一个人, 目的就是写一个算法找到这个名人,并返回其id,如果没有就返回-1. 其中有一个接口函数是bool knows(a,b), 意思是a认不认识b,希望尽可能少地调用这个函数。

法一

这个应该最容易想到,就是一个一个地去试

class Solution{
public:
    
    int findCelebrity(int n){
        vector<bool> candidate(n, true);  //默认的每个都是true
        for(int i=0;i<n;i++){
            for(j=0;j<n;j++){
                if(candidate[i] && i != j){
                    if(knows(i,j) || !knows(j,i)){
                        candidate[i] = false;
                        break;
                    }else{
                        candidate[j] = false;
                    }

                }
            }
            if (candidate[i]) return i;   
        }
        
        return -1;
    }

};

法二

class Solution{
public:
    int findCelebrity(int n){
        int res=0;
        for(int i=0;i<n;++i){
            if(knows(res,i)) res=i;
    
        }
        
        //check res 
        for(int i=0;i<n;i++){

            if(res != i && (knows(res,i)) || !knows(i,res)) return -1;
        }
        return res;

    }


}



这种方法的意思是,把名人初始化为0,因为名人是所有人都认得他,所以见到认识的就更新一下res,第一个for结束的时候的res的状态是这样的, res前面的一定不是名人,因为要么是别人不认识他,或者他认识别人,所以都不是名人。 而res之后的也一定不是名人,因为res不认识他们,所以唯一有可能是名人的就是res.

最后的还可以改成

def findCelebrity(self, n):
    res = 0
    for i in xrange(n):
        if knows(res, i): res = i
    for i in xrange(res):
        if knows(res, i) or not knows(i, res): return -1
    for i in xrange(res + 1, n):
        if not knows(i, res): return -1
    return res

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦