我是没想到这个公司的笔试编程题这么难
2023-02-18 16:41:48 时间
明略科技公司的笔试两道编程题
第一题思路:首先先序遍历,找到最小最大的节点,然后是计算这两个节点的距离,先找他们的最近祖先,也就是最近公共节点,然后分别计算祖先到两个节点的距离,然后相加,难点是求祖先和求两个点之间距离
/*
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;
}
};
相关文章
- From CVE-2017-0263 To Windows Menu Management Component
- “测试”怎么“玩”?
- 测试之路--随手记:WebSocket
- 浅谈测试如何建立自己的质量体系
- 测试之路 pytest接口自动化框架-插件补充及pytest装饰器扩展
- 测试之路 pytest接口自动化框架-fixture与conftest
- 程序员进阶系列(1)
- 测试之路--随手记:接口自动化的应用
- 从零开始开发一个小游戏有什么难点
- npm 发包实践教程之 gRPC 怎么使用?(1)
- 企点聊营销 | 杜绝自嗨,营销也要“高情商”!
- 测试之路 pytest接口自动化框架-yaml数据
- 办好一场数字化体验的大会,你可以试试看这样做
- 测试之路 pytest接口自动化框架-yaml数据驱动
- 阅读源码入门实践系列之 element ui(1)
- 测试之路 pytest接口自动化框架扩展-思路梳理+成果展示
- 使用 WebRTC 构建简单的视频聊天室(1)
- 测试之路 pytest接口自动化框架扩展-GUI窗口
- 测试之路 pytest接口自动化框架扩展-集成flask
- 测试之路 pytest接口自动化框架扩展-MS数据解析