Nortel一道笔试题

  我没有参加Software Engineer的考试，错投了Product Test Engineer，搞得面试的时候没什么优势，不然说不定也有二面的机会给我。

   这道题目是同学基本表述出来的，大意是从一堆人中找出明星，明星的条件是其他人都认识他，但他不认识其他人。题目的一个限制是效率要在O（n2）之下。短短时间之内，好象基本没有同学搞定。今天早上，花了将近一个小时的时间把这个问题解决了。其间想到很多概念，回溯，分治好象不可行哈，呵呵还是挺有意思的。

   由此而看，就是一个行列式，可以定义如下，二阶数组a[n][n]；

  

int query(int[4][4] a,int size);

   int main(){
     int a[4][4]={{1,1,0,1},{0,1,0,0},{0,1,1,0},{0,1,1,1}};
     cput<<query(a,4);
   }
   //这里需要的一个前提就是行列式必须是符合题目要求的
   int query(int[4][4] a,int size){
     int i=0;
     for(int j=i+1;j<n;j++)
   //对称位置不等才符合要求，且要求是明星潜质才行哦（a[j][i]==0）
       if(a[i][j]!=a[j][i]&&a[j][i]==0)
         i=j;
     return i;
   }

  
   涉及到的主要思想就是避免不必要的扫描啦，从前往后扫描，前面的不符合要求就直接往后跳，写的时候还记起kmp，开始的时候还以为需要象八皇后那样需要回溯呢，后发现no，他的内容是已经给定的。

评论

1 楼 ouspec 2006-11-15  

算法效率最重要