2007-08-14

两道笔试题

关键字: C++
昨天一朋友找工作, 碰到两道算法笔试题, 都是当于链表操作的.

原题具体的还原不过来了, 不过大致是:

1. 有一单链表, 找出最后第m个节点.

 昨天看到问题时,想到了小学应用题:

汽车过山洞, 假如这个汽车开着开着, 等到车头刚要出山洞, 车尾离山洞出口也有一段距离嘛...

这样, 这个题方法出来了

cpp 代码
 
  1. Node* FindLastNode(Node* root, int m) {  
  2.     Node* head = root;  
  3.     Node* tail = root;  
  4.   
  5.     // 开始时,大概是这样  
  6.     //           |---------------------|  这个是山洞  
  7.     //           >>               这个是车车? 哦, 是小蛇, 身体盘在一起...  
  8.       
  9.     // 然后往前爬  
  10.     for (int i = 0; i < m; ++i) {  
  11.         head = head->next;  
  12.     }  
  13.   
  14.     // 此时  
  15.     //           |---------------------|  这个是山洞  
  16.     //           >-------->  
  17.   
  18.     // 一起前进吧  
  19.     while (head->next) {  
  20.         head = head->next;  
  21.         tail = tail->next;  
  22.     }  
  23.   
  24.     // 此时  
  25.     //           |---------------------|  这个是山洞  
  26.     //                        >-------->  
  27.   
  28.     return tail;  
  29. }  

当然,特殊情况要考虑, 不过那....


2.  有一单链表, 判断是否存在环

 
有环? 走着走着, 却突然发现, 怎么也走不完, 可是这要走到什么时候? 此法不通

可是怎么也想不出好办法. 只有一个笨方法:

看看现在走的路, 是不是已走过...

cpp 代码
 
  1. bool HasCircle(Node* root) {  
  2.     Node* cur = root;  
  3.     while (cur->next) { // 1 号走到一个站， 等  
  4.         // 派出2号，开始走， 看是否更快地和1号相遇  
  5.         for (Node* other = root; other->next != cur; other = other->next) {  
  6.             if (cur->next == other) {     
  7.                 return true;    // 2号提前赶到， 1 号走冤枉路了  
  8.             }  
  9.         }  
  10.         cur = cur->next;      
  11.     }  
  12.     return false;  
  13. }  


对于2, 不知道有没有更好的办法?
评论
jjcang 2007-08-17
第2题应该把走过的node记录下来，查找快点。 
bool hasCycle(node* p){
set<node*> passed;

while( p->next){
p= p->next;
if( passed.find(p) != passed.end()) return true;
passed.insert(p);
}
return false;

特殊情况没有考虑。
bcccs 2007-08-15
第2题，在单链表的情况下应该是只有这个方法了吧。时间复杂度也不高，
抛出异常的爱 2007-08-15 
one = root
two = root 
two.next; （刚刚忘记先走出去一步了）
    while (one.next) {// 1号，走一站
        two.next; // 2号，走1站，（比one快一步）
         if(two==one) return true;// 看是否与1号相遇 
        two.next;//2号，再走一站，（比one快二步）
          if(tw0==one)return true;
   
     }  
return false;

上学时一个例题？？？大约是这么写的，几乎没写过C
bencode
  • 浏览: 30618 次
  • 性别: Icon_minigender_1
  • 来自: 浙江台州
  • 详细资料
搜索本博客
存档
最新评论