2015京东校园招聘技术类笔试题

1、

给定字符串（ASCII码0-255）数组，请在不开辟额外空间的情况下删除开始和结尾处的空格，并将中间的多个连续的空格合并成一个。例如：” i am a little boy. “，变成”i am a little boy”,语言不限，但不要用伪代码作答，函数输入输出请参考如下的函数原型：

1
2
3
C++函数原型：
void FormatString(char str[],int len){
}

#include<stdio.h>
#include <string.h>

void FormatString(char str[],int len)
{
    if (str == NULL || len <= 0) {
        return;
    }
    int i = 0;
    int j = 0;
    if (str[i] == ' ') {
        while (str[i] == ' ') {
            ++i;
        }
    }
    while (str[i] != '\0') {
        if (str[i] == ' ' && str[i + 1] == ' ' || str[i + 1] == '\0') {
            ++i;
            continue;
        }
        str[j++] = str[i++];
    }
    str[j] = '\0';
}

int main() {
    char a[] = "   i    am a      little boy.    ";
    int len = strlen(a);
    printf("%d\n",len);
    FormatString(a,len);
    printf("%d\n",strlen(a));
    printf("%s\n",a);
    return 0;
}

2、

给定一颗二叉树，以及其中的两个node（地址均非空），要求给出这两个node的一个公共父节点，使得这个父节点与两个节点的路径之和最小。描述你程序的最坏时间复杂度，并实现具体函数，函数输入输出请参考如下的函数原型：

C++函数原型：
1
2
3
4
5
6
7
strucy TreeNode{
TreeNode* left; //指向左子树
TreeNode* right; //指向右子树
TreeNode* father; //指向父亲节点
};
TreeNode* LowestCommonAncestor(TreeNode* first,TreeNode* second){
}

int nodeHeight(TreeNode* node)
{
    int height = 0;
    while(node != NULL)
    {
        height++;
        node = node->father;
    }
}
TreeNode* LowestCommonAncestor(TreeNode* first, TreeNode* second)
{
    int diff = nodeHeight(first) - nodeHeight(second);
    if(diff > 0)
    {
        while(diff > 0)
        {
            first = first->father;
            diff--;
        }
    }
    else
    {
        while(diff < 0)
        {
            second = second->father;
            diff++;
        }
    }
    while(first != second)
    {
        first = first->father;
        second = second->father;
    }
    return first;
}