暴风影音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);  
}  

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

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

一是利用数学知识，从左上角到右下角总共要走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