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

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

    //返回结果的有效标志    
    enum Status {VALID,IN_VALID};    
    int gStatus = VALID;    
        
    int strToInt(const char* str)    
    {    
        long long result = 0;//保存结果    
        gStatus = IN_VALID; //每次调用时都初始化为IN_VALID    
        if(str != NULL)    
        {    
            const char* digit = str;    
        
            bool minus = false;    
        
            if(*digit == '+')    
                digit++;    
            else if(*digit == '-')    
            {    
                digit++;    
                minus = true;    
            }    
        
            while(*digit != '\0')    
            {    
                if(*digit >= '0' && *digit <= '9')    
                {    
                    result = result * 10 + (*digit -'0');    
                    //溢出    
                    if(result > std::numeric_limits<int>::max())    
                    {    
                        result = 0;    
                        break;    
                    }    
                    digit++;    
                }    
        
                //非法输入    
                else    
                {    
                    result = 0;    
                    break;    
                }    
            }    
        
            if(*digit == '\0')    
            {    
                gStatus = VALID;    
                if(minus)    
                    result = 0 - result;    
            }    
        }    
        
        return static_cast<int>(result);    
    }    

2.给出一棵二叉树的前序和中序遍历，输出后续遍历的结果，假设二叉树中存储的均是ASCII码。如前序：ABDHECFG，中序：HDBEAFCG，则输出后序为：HDECFGCA，改正为：HDECFGBA，再次改正HDEBFGCA。

思路：先利用前序和中序构建出二叉树，然后后序遍历输出结果

    /**  
    *返回二叉树的根节点  
    *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);    
    }