网易2016实习研发笔试

系统管理员 2022-07-27 11:56 233阅读 0赞

小明陪小红去看钻石，他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们们比较了一段时间后，它们看中了两颗钻石g1和g2。现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。

给定两颗钻石的编号g1,g2，编号从1开始，同时给定关系数组vector,其中元素为一些二元组，第一个元素为一次比较中较重的钻石的编号，第二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系，若g1更重返回1，g2更重返回-1，无法判断返回0。输入数据保证合法，不会有矛盾情况出现。

思路：图搜，有向图中找g1到g2或者g2到g1的路径，找不到返回0.

class Cmp {
    public:
    	int cmp(int g1, int g2, vector<vector<int> > records, int n) {
    		// write code here
    		map<int, vector<int>>graph, graph1;
    		for (int i = 0; i<records.size(); i++)
    			graph[records[i][0]].push_back(records[i][1]);
    		graph1 = graph;
    		if (graph.find(g1) != graph.end())
    		{
    			vector<int>path;
    			path.push_back(g1);
    			while (!path.empty())
    			{
    				while (!graph[path.back()].empty())
    				{
    					int r = path.back();
    					path.push_back(graph[path.back()].back());
    					if (path.back() == g2)
    						return 1;
    					graph[r].pop_back();
    				}
    				path.pop_back();
    			}
    		}
    
    		if (graph1.find(g2) != graph1.end())
    		{
    			vector<int>path;
    			path.push_back(g2);
    			while (!path.empty())
    			{
    				while (!graph1[path.back()].empty())
    				{
    					int r = path.back();
    					path.push_back(graph1[path.back()].back());
    					if (path.back() == g1)
    						return -1;
    					graph1[r].pop_back();
    				}
    				path.pop_back();
    			}
    		}
    		return 0;
    	}
    };

有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。

给定二叉树的根节点root，请返回所求距离。

思路：这题找LCA属于，先找到最大最小的叶节点，然后把他们到LCA的距离相加即可。

struct TreeNode \{  
    int val;  
    struct TreeNode \*left;  
    struct TreeNode \*right;  
    TreeNode(int x) :  
            val(x), left(NULL), right(NULL) \{  
    \}  
\};\*/  
  
  
class Tree \{  
public:  
    int getDis(TreeNode\* root) \{  
        // write code here  
    \}  
\};

有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。

给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。

class Finder {
    public:
        int findKth(vector<int> a, int n, int K) {
            // write code here
            sort(a.begin(),a.end());
            return a[n-K]; 
        }
    };

1个小时3道题，虽然不算太难，但时间还是蛮紧张的。