梁越

我是没想到这个公司的笔试编程题这么难

0 人看过

明略科技公司的笔试两道编程题

第一题思路:首先先序遍历,找到最小最大的节点,然后是计算这两个节点的距离,先找他们的最近祖先,也就是最近公共节点,然后分别计算祖先到两个节点的距离,然后相加,难点是求祖先和求两个点之间距离

/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/

class Tree {
public:
    TreeNode* minNode;
    TreeNode* maxNode;

    TreeNode* findLCA(TreeNode* root, TreeNode* n1, TreeNode* n2){ //找两个节点的祖先
        if(!root) return nullptr;
        if(root->val==n1->val || root->val==n2->val) return root;
        TreeNode* left=findLCA(root->left, n1, n2);
        TreeNode* right=findLCA(root->right, n1, n2);
        if(left && right) return root;
        return left!=nullptr?left:right;
    }

    void dfs(TreeNode* root){ //先序遍历找最大最小
        if(!root) return;
        if(!root->left && !root->right && root->val>maxNode->val) maxNode=root;
        if(!root->left && !root->right && root->val<minNode->val) minNode=root;
        dfs(root->left);
        dfs(root->right);
    }

    int dist(TreeNode *root, TreeNode* node, int level){ //计算祖先到后代节点的距离
        if(!root) return -1;
        if(root->val==node->val) return level;
        int le=dist(root->left, node, level+1);
        if(le==-1) {
            return dist(root->right, node, level+1);
        }
        else{
            return le;
        }
    }

    int getDis(TreeNode* root) {
        // write code here
        if(!root) return 0;
        minNode=new TreeNode(INT_MAX);
        maxNode=new TreeNode(INT_MIN);
        dfs(root);
        TreeNode* lca=findLCA(root, minNode, maxNode);
        //cout<<dist(lca, minNode, 0);
        return dist(lca, minNode, 0)+dist(lca, maxNode, 0); //将两个节点到祖先的距离相加
        //return dist(root, minNode, 0)+dist(root, maxNode, 0)-2*dist(root, lca, 0);
    }
};

第二题思路:这个先排序,再遍历一边就可以,但是O(n)复杂度的排序算法,就只有基数排序了,每隔元素对应到一个桶上,然后计算相邻的桶之间的差值

class MaxDivision {
public:
    int findMaxDivision(vector<int> A, int n) {
        // write code here
        int maxval=INT_MIN, minval=INT_MAX;
        for(auto item:A){
            if(item>maxval) maxval=item;
            if(item<minval) minval=item;
        }

        vector<int> record(maxval-minval+1, 0);

        for(auto item:A) record[item-minval]=1;
        int i=0, j=1, MAX_DIFF=INT_MIN;

        int count=0, Max=0;
        for(int i=0;i<record.size();i++){
            if(record[i]==0){
                count++;
            }
            else{
                Max=max(Max, count);
                count=0;
            }
        }

        return Max+1;
    }
};