无我

让内心永远燃烧着伟大的光明的精神之火!
灵活的思考,严谨的实现
豪迈的气魄、顽强的意志和周全的思考

华为2008校园招聘北京笔试最后编程题


这里附上我的华为2008校园招聘北京笔试最后编程题答案:

第一题:猫吃老鼠,就是猴子选大王的改版,循环链表解决:

#include <iostream>
using namespace std;

struct node
{
 int date;
 struct node* next;
};
typedef  struct node Node;

int main(int argc, char* argv[])
{
 int count,begin,i;
 do{
  cout<<"请输入总数和起始位置:"<<endl;
  cin>>count>>begin;
 }while(count<=0 || begin<=0 || begin>count);
 
 i = count;
 Node *head =  new Node,*last,*pre;
 head->date = count;
 head->next = NULL;
 last = head;
 if(begin+1 == count)  pre = head;
 while (--i != 0)
 {
  Node* temp = new Node;
  temp->date = i;
  temp->next = NULL;
  if(i == begin+1) pre = temp;
  last->next = temp;
  last = temp;
 }
 last->next = head;
 if(begin == count)  pre = last;
 
 i = count - 1;
 while (--i != 0)
 {
  Node* temp = pre->next;
  pre->next = pre->next->next;
  delete temp;
  pre = pre->next;
 }
 cout<<pre->date<<endl;
 return 0;
}

第二题:求未知链表的中间位置算法:

struct node* findmid(struct node* head)
{
 struct node *one = head,*two = head;
 while(two != NULL)
 {  
  two = two->next;
  if(two != NULL)
  {
   two = two->next;
   one = one->next;
  }
 }
 return one;
}

posted on 2007-11-24 15:02 Tim 阅读(5714) 评论(7)  编辑 收藏 引用 所属分类: C/C++语言

评论

# re: 华为2008校园招聘北京笔试最后编程题 2007-11-24 19:46 winsty

第一题有不用模拟的办法 太麻烦了
见我的网站:
[url]http://acm.zjuwinsty.cn/post/25.html[/url]
第二题的写法很强大...
我的想法是O(n)先遍历一次链表 记录下来有多少个
然后 再从头走n/2个
可能更易读一点  回复  更多评论   

# re: 华为2008校园招聘北京笔试最后编程题[未登录] 2007-11-27 23:33 RomanGol

约瑟夫问题(猴子选大王)有数学公式的,见Knuth的《具体数学》  回复  更多评论   

# re: 华为2008校园招聘北京笔试最后编程题 2007-11-30 21:28 zlf

fuck!太简单了  回复  更多评论   

# re: 华为2008校园招聘北京笔试最后编程题 2007-12-27 22:17 秦歌

可以一试呀!  回复  更多评论   

# re: 华为2008校园招聘北京笔试最后编程题 2008-11-22 19:42 Hover

第二题用的方法确实很另类, 但是在算法复杂度上没有先遍历一次,记录节点个数的方法好.  回复  更多评论   

# re: 华为2008校园招聘北京笔试最后编程题 2008-12-26 15:31 北京论坛

记录节点个数的方法好  回复  更多评论   

# re: 华为2008校园招聘北京笔试最后编程题 2009-05-07 23:20 LCW123

日!这种题也拿的出手哦!!!!!!!!!!!!!!!  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2007年11月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

导航

统计

公告

本博客原创文章,欢迎转载和交流。不过请注明以下信息:
作者:TimWu
邮箱:timfly@yeah.net
来源:www.cppblog.com/Tim
感谢您对我的支持!

留言簿(9)

随笔分类(173)

IT

Life

搜索

积分与排名

最新随笔

最新评论

阅读排行榜