浏览 3763 次
锁定老帖子 主题:Nortel一道笔试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2006-11-10
这道题目是同学基本表述出来的,大意是从一堆人中找出明星,明星的条件是其他人都认识他,但他不认识其他人。题目的一个限制是效率要在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,他的内容是已经给定的。 声明:ITeye文章版权属于作者,受法律保护。没有作者书面许可不得转载。
推荐链接
|
|
返回顶楼 | |
发表时间:2006-11-15
算法效率最重要
|
|
返回顶楼 | |