百度笔试题

最新推荐文章于 2019-03-03 21:41:20 发布

ituling

最新推荐文章于 2019-03-03 21:41:20 发布

阅读量569

点赞数

本文链接：https://blog.csdn.net/ituling/article/details/52601179

版权

虽然是面经，写一个就挂一个，而且特别想去百度，比较在北京，阿里辜负了我的心意。但是，为了总结，也不怕诅咒了。
百度面试题：前2题和简单，就不赘述了。
第三题：
一个树，数组存储，在一些节点上有苹果，小猴子可以从任意节点上开始，沿着任意的路径去寻找苹果，前提是一个节点只能经过一次，寻找出可以发现苹果最大的路径，返回可以找到的苹果个数。
思路： 1 首先构造这个数，这个是多叉树，用数组存储。 2. 递归的搜索路径

当时时间不够了，没写完整，所以感觉百度悬了，现在post出代码来，假如有错误，可以帮我修订，或者直接去github上给我pull requst。

#include<iostream>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<functional>
using namespace std;
struct TreeNode{
	vector<TreeNode*> clild;
	int val;
	int app;
	TreeNode(int v, int a):val(v),app(a){}
};
void findMax(vector<int>res, int &first, int &second){
	if(res.size() == 0)return ;
	if(res.size() == 1){
		first = res[0];
		return ;
	}
	first = max(res[0],res[1]);
	second = min(res[0],res[1]);
	for(int i = 2; i < res.size();i ++){
		if(res[i] > first){
			second = first;
			first = res[i];

		}else if(res[i] <= first && res[i] > second){
			second = res[i];
		}
		
	}
}

class Solution {
private:
    int maxval;
    int maxHelper(TreeNode *root){
        if(root == NULL)return 0;
		vector<TreeNode*> child = root->clild;
		vector<int>res;
		for(int i = 0; i < child.size(); i++){
			int v = maxHelper(child[i]);
			res.push_back(v);
		}
		int first = 0;
		int second = 0;
		findMax(res,first,second);
        maxval = std::max(maxval,first+second+root->app);
        return first+root->app;
	}
	TreeNode* count(int N, int K, int * app, int T[][2]){
		set<int> s;
		for(int i = 0; i < K; i++){
			s.insert(app[i]);
		}
		vector<TreeNode *> nodes;
		for(int i = 0; i < N ; i++){
			int a = 0;
			if(s.find(i+1) != s.end()){
				a = 1;
			}else{
				a = 0;
			}
			TreeNode * node = new TreeNode(i+1,a);
			nodes.push_back(node);
		}
		for(int i = 0; i < N -1; i++){
			int fisrt = T[i][0];
			int second = T[i][1];
			nodes[ fisrt-1]-> clild.push_back(nodes[second-1]);
		}
		return nodes[0];
	}
public:
    int maxPathSum(int N, int K, int * app, int T[][2]) {
        maxval = INT_MIN;
        maxHelper(count(N,K,app,T));
        return maxval;
    }

};

点击进入 github地址