校园招聘

小米科技

北京小米科技有限责任公司

所属行业:互联网/电子商务 企业性质:私营/民营企业 企业规模:1000人以上

小米编程笔试题

时间:2016-11-30 编辑:光辉

  今天在园子里面看到有人评论辩论小米笔试题的解法,好吧,我不知道小米已经笔试了,

  本身看了一下,试着用线段树解决,没想到把握得还不敷稳定啊.....

  终极还是解决了

  /*******************************************

  *Problem:

  * 一条直线有n个线段,知道首尾坐标,

  * 求线段总长度,重叠项目组按一次算

  * struct s{int start;int end;}

  *Author: Lei

  *Bolg: http://www.cnblogs.com/-Lei/

  ********************************************/

  #include

  using namespace std;

  const int MAX_NODE_NUMBER=20;

  struct Segment

  {

  int start;

  int end;

  };

  Segment segments ;

  struct TreeNode

  {

  int left;

  int right;

  int cover;

  };

  //线段树

  TreeNode tree ;

  void Update(int root,int left,int right)

  {

  int mid;

  if(tree .cover==0)

  {

  mid=(tree .left+tree .right)/2;

  if(left==tree .left  right==tree .right)

  tree .cover=1;

  else if(right = mid)

  Update(root*2+1,left,right);

  else

  {

  Update(root*2,left,mid);

  Update(root*2+1,mid,right);

  }

  }

  }

  int Count(int root)

  {

  if(tree .right-tree .left==1)

  return 0;

  else if(tree .cover==1)

  return tree .right-tree .left;

  else

  return Count(root*2)+Count(root*2+1);

  }

  void InitTree(int root,int left,int right)

  {

  tree .cover=0;

  tree .left=left;

  tree .right=right;

  if(tree .right-tree .left==1)

  return ;

  int mid=(left+right)/2;

  InitTree(root*2,left,mid);

  InitTree(root*2+1,mid,right);

  }

  int main()

  {

  InitTree(1,1,15);

  Update(1,1,4);

  Update(1,3,5);

  Update(1,2,6);

  Update(1,2,3);

  Update(1,12,13);

  Update(1,8,13);

  cout<<"Total segment length= "

  system("PAUSE");

  return 0;

  }

您需要登录后才可以回帖登录|注册
发布

互联网/电子商务

私营/民营企业

1000人以上

http://www.xiaomi.com/

公司地址

北京市 - 北京市 - 海淀区清河中街68号 华润五彩城写字楼

扫码关注官方微信

及时获取"最新"校招信息