明略科技公司的笔试两道编程题
第一题思路:首先先序遍历,找到最小最大的节点,然后是计算这两个节点的距离,先找他们的最近祖先,也就是最近公共节点,然后分别计算祖先到两个节点的距离,然后相加,难点是求祖先和求两个点之间距离
/*
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;
}
};