昔我往矣

笔试之代码惊魂

2012年03月18日

上次去参加绿盟的笔试,在网上找了以前的笔试题目,据说重复度很高。于是,下载下来仔细的研究了一番,其中有一道不限语言编写二叉树的深搜算法。心想这一题绝对不能放过,又考虑到太久没有写过代码了,于是就麻烦张飞学长写了一个深搜和广深的程序,自己好好研究,终于是把深搜算法弄明白了。

深搜采用的是递归算法,广搜使用了队列(这个就不是太看得明白了)。
张飞学长的源代码如下:

#include <iostream>
#include <queue>
using namespace std;

struct TreeNode{
    TreeNode(){
        data = 0;
        lChild = rChild = NULL;
    }
    int data;
    TreeNode *lChild, *rChild;
};

/*
 * 先序构建二叉树,输入的值为负数代表该节点为空
 */
void BuildTree(TreeNode *&root){
    int data;
    cin >>data;
    if(data >= 0){
        root = new TreeNode();
        root->data = data;
        BuildTree(root->lChild);
        BuildTree(root->rChild);
    }
}

/*
 * 深度优先遍历(先序遍历)
 */
void DeepFirst(TreeNode *root){
    if(root){
        cout <<root->data <<" ";
        DeepFirst(root->lChild);
        DeepFirst(root->rChild);
    }
}

/*
 * 广度优先遍历(使用队列)
 */
void BroadFirst(TreeNode *root){
    queue<TreeNode *> q;
    q.push(root);
    TreeNode *f = q.front();
    if(f){
        cout <<f->data <<" ";
    }
    while(!q.empty()){
        if(f->lChild){
            cout <<f->lChild->data <<" ";
            q.push(f->lChild);
        }
        if(f->rChild){
            cout <<f->rChild->data <<" ";
            q.push(f->rChild);
        }
        q.pop();
        f = q.front();
    }
}

int main(){
    freopen("in","r",stdin);
    TreeNode *root;
    BuildTree(root);
    DeepFirst(root);
    cout <<endl;
    BroadFirst(root);
    cout <<endl;

    return 0;
}

到了考场之后发现大家都是有备而来,都是网上的往年试题。试卷发下来的时候都傻眼了,没一道原题!倒是编程题变化不是很大,一个n*m的“田”字区域,从左下角到右上角最短路径的走发有多少种(貌似高中的排列组合题)。在草稿子画了半天终于想明白了也可以使用递归。
思路:类似于上楼梯的题,Tom要走一个N级台阶的楼梯,他一次可以走2级,也可以走1级,问有多少种走法。设走到N级台阶的走法为F(N),则F(N)=F(N-1)+F(N-2)。同理,以坐标来描述这个n*m的区域,左下角为(0,0),右上角为(n,m)。到(n,m)一共有两种办法,从(n-1,m)或(n,m-1)到达。那么同理也可以知道(n,m-1)和(n-1,m)的走法。余下的使用递归就很容易解决了!
代码如下:

#include <iostream>
using namespace std;

int t=0;

void count(int x,int y)
{
    if(x==0||y==0)
    {
        t++;
    }
    else
    {
        count(x-1,y);
        count(x,y-1);
    }
}

int main()
{
    int x,y;
    cin>>x>>y;
    count(x,y);
    cout<<t<<endl;
    return 0;
}

但是在考场上一兴奋,定义t的时候变成了const int t=0;回来才发现这个问题,肠子都悔青了(谁有后悔药卖我两颗)。不过,能徒手写出这段代码,也实属不易啊!另外还有就是可能函数的类型定义有问题!
总结:搞计算机的,无论做的是哪个方向,编程始终是基础中的基础,如果没有扎实的基础,很难再技术上有所造诣。更何况,基本上所有的互联网企业招聘时候都会有编程题,所以,不会写程序,甚至连互联网企业的大门都进不去。诸位,共勉之!

已有 4 条评论 »

添加新评论 »