暴风影音2014笔试算法题集锦

暴风影音2014笔试算法题汇总

1.自定义实现字符串转为整数的算法，例如把“123456”转成整数123456.(输入中可能存在符号，和数字)

/** *返回二叉树的根节点 *preOrder:前序遍历序列 *inOrder:中序遍历序列 *len:节点数目 */  Node* getBinaryTree(char* preOrder, char* inOrder, int len)  {      if(preOrder == NULL || *preOrder == '\0' || len<=0)          return NULL;        Node* root = (Node*) malloc(sizeof(Node));      if(root == NULL)          exit(EXIT_FAILURE);        //前序遍历的第一个节点就是根节点      root->data = *preOrder;        int pos = 0;//找到根节点在中序遍历中的位置，其值也代表了左子树的节点数目      while(true)      {          if(*(inOrder+pos) == root->data)              break;          pos++;      }        //通过递归找到左子树和右子树，注意子树的前序中序的下标的计算      if(pos == 0)          root->lchild = NULL;      else          root->lchild = getBinaryTree(preOrder+1, inOrder, pos);        if(len-pos-1 == 0)          root->rchild = NULL;      else          root->rchild = getBinaryTree(preOrder+pos+1, inOrder+pos+1,len-pos-1);      return root;  }    /** *后续遍历二叉树 * */  void postOrder(Node* root)  {      if(root == NULL)          return;        postOrder(root->lchild);      postOrder(root->rchild);      printf("%c", root->data);  }    /** *根据前序遍历和中序遍历输出后续遍历 * */  void printPostOrderViaPreOrderAndInorder(char* preOrder, char* inOrder)  {      Node* root = getBinaryTree(preOrder, inOrder, strlen(preOrder));      postOrder(root);  }  

3.给出了一个n*n的矩形，编程求从左上角到右下角的路径数（n > =2），限制只能向右或向下移动，不能回退。例如当n=2时，有6条路径。

一是利用数学知识，从左上角到右下角总共要走2n步，其中横向要走n步，所以总共就是C2n~n。

二是利用递归实现

/** *返回总路径数 *参数m:表示矩形的横向格子数 *参数n:表示矩形的纵向格子数 */  int getTotalPath(int m, int n)  {      //如果横向格子数为1，则类似“日”字，此时路径数为纵向格子数加1      if(m == 1)          return n + 1;      //如果纵向格子数为1，此时路径数为横向格子数加1      if(n == 1)          return m + 1;        //由于从当前点出发，只能向右或向下移动：      //向右移动，则接下来就是getTotalPath(m-1, n)的情形      //向下移动，则接下来就是getTotalPath(m, n-1)的情形      return getTotalPath(m-1, n) + getTotalPath(m, n-1);  }  

转载请注明原创链接：http://blog.csdn.net/wujunokay/article/details/12209183

查看更多 下一篇