Re: 问两道头条算法题

转行一年直杀三面，给大佬点赞

第一题最大距离这个leetcode有原题好像，很经典了，大概思路就是对于任意节点A，要么A是这个最大距离的根节点，要么最大距离的根节点在A的左子树，要么最大距离的根节点在A的右子树，答出这个应该就没问题了，可能会让你写非递归的 第二题这个不考虑复杂度的话，先按左区间排序，然后合并相邻区间，直接判断就行了，合并区间很简单，没交集就不合并，有交集就取并集 优化性能的话没仔细想，我也是个渣渣

第一题是指树两点的最大距离？leetcode原题吧，分成两个点都在左子树或右子树、一个在左一个在右递归搞一搞。 第二题也是编程之美原题 把集合里的区间排序合并(例子中合并成[1，6])，然后二分判断区间的两个点是不是在同一个区间上就好了，好像还有用并查集做的。

第二题leetcode也有原题

想知道楼主是本科还是研究生啊

这两题都是最简单的基础题吧，刷过leetcode的都能做对。 struct Node { int val; vector<Node*> children; }; int diameter(Node* root, int& res) { //res为引用值，函数调用后，res为所求最后结果 int first_len = 0, second_len = 0; //分别为所有孩子的最深子树的深度和次深子树的深度 for(Node* child: root->children) { int len = diameter(child, res); //该孩子对应的子树的最大深度 if(len > second_len) { if(len > first_len) { second_len = first_len; first_len = len; } else second_len = len; } } res = max(res, first_len + second_len); //判定过该节点的最长路径(左子树最深路径 -> 当前节点 -> 右子树最深路径)是否是全局最长路径 return max(first_len, second_len) + 1; //返回当前节点的最深路径 } typedef pair<int, int> mypair; //first: 区间端点值, second: 端点类型，左端点为0，右端点为1 struct comp { bool operator()(const mypair& lhs, const mypair& rhs) { if(lhs.first != rhs.first) return lhs.first < rhs.first; else return lhs.second < rhs.second; //左端点优先排到前面 } }; int mergeInterval(vector<int>& x, vector<int>& y, int px, int py) { vector<mypair> points; for(int i = 0; i < x.size(); i++) { points.push_back(mypair(x[i], 0)); points.push_back(mypair(y[i], 1)); } sort(points.begin(), points.end(), comp()); int start = 0; //记录最左端点值 int cnt = 0; //统计左边端点数 for(int i = 0; i < points.size(); i++) { if(points[i].second == 0) { if(cnt == 0) start = points[i].first; cnt += 1; } else { cnt -= 1; if(cnt == 0) { //左端点数和右端点数相等，这些端点对应的区间构成一个合并区间 if(start <= px && py <= points[i].first) //当前区间包含[px, py] return true; } } return false; }

二题按左端点按左端点排序 这是关键 我去面试就被问的这个 看来互联网企业考算法总是翻来覆去问啊

说实话，不难。刚转行，估计面试官还是会考虑你的基础好不好，所以多看看数据结构，做做题。对于面试，特别是头条这样爱做题的面试有帮助。

都是leetcode上题吧，见过，但不会做