1.
小明陪小红去看钻石，他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们们比较了一段时间后，它们看中了两颗钻石g1和g2。现在请你根据之前比较的信息判断这两颗钻石的哪颗更重。
给定两颗钻石的编号g1,g2，编号从1开始，同时给定关系数组vector,其中元素为一些二元组，第一个元素为一次比较中较重的钻石的编号，第二个元素为较轻的钻石的编号。最后给定之前的比较次数n。请返回这两颗钻石的关系，若g1更重返回1，g2更重返回-1，无法判断返回0。输入数据保证合法，不会有矛盾情况出现。
测试样例：
2,3,[[1,2],[2,4],[1,3],[4,3]],4
返回: 1
思路：比较图上两点的拓扑关系。可以使用拓扑排序，一种更简单的方法是，直接check两点的可达性。
class Cmp {
public:
const int INF = 0x3f3f3f3f; bool canArr(int cur, int g2, int n)
{
queue<int>que;
que.push(cur);
bool vis[];
for(int i = ; i <= n; i ++){
vis[i] = false;
}
vis[cur] = true;
while(!que.empty()){
cur = que.front();
que.pop();
if(cur == g2) return true;
for(int i = ; i < (int)g[cur].size(); i ++){
int nx = g[cur][i];
if(!vis[nx]){
vis[nx] = true;
que.push(nx);
}
}
}
return false;
} int cmp(int g1, int g2, vector<vector<int> > records, int n) {
// write code here
for(int i = ; i <= n; i ++){
g[i].clear();
}
for(int i = ; i < (int)records.size(); i ++){
int u = records[i][], v = records[i][];
g[u].push_back(v);
} if(g1 == g2){
return -;
}
bool g1A = canArr(g1, g2, n), g2A = canArr(g2, g1, n);
if(g1A){
return ;
}else if(g2A){
return -;
}else{
return ;
}
}
private:
vector<int>g[];
};
dfs会TorSegment Error。 以后能用ＢＦＳ还是首选宽度优先搜索吧！
2.
有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为1，一个节点经过多少条边到达另一个节点为这两个节点之间的距离。
给定二叉树的根节点root，请返回所求距离。
思路：求的是叶节点。一开始没看清楚求成了任意两个节点。 仔细想想 ，只用找到两个点的最近公共祖先节点，然后将距离相加就好了！
求最近公共祖先节点需要用到 parent来记录每个节点的父节点。然后就变成了两个链表 最后汇聚到同一个点（祖先）。找到这个点就好了。需要先将两个链表的长度统一成较小的这样方便找到公共点。
/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/class Tree {
public:
const int INF = 0x3f3f3f3f;TreeNode* parents[];void travelNodes(TreeNode* root, TreeNode* last)
{
if(root){
if(minNode -> val > root -> val && !root -> left && !root -> right){
minNode = root;
}if(maxNode -> val < root -> val && !root -> left && !root -> right){
maxNode = root;
}
parents[root -> val] = last;
travelNodes(root -> left, root);
travelNodes(root -> right, root);
}
}int height(TreeNode *rt)
{
int len = ;
while(parents[rt -> val]){
len ++;
rt = parents[rt -> val];
}
return len;
}int disToCANone(TreeNode *comAscNode, TreeNode* n1, TreeNode* n2)
{
queue<TreeNode *>que;
que.push(comAscNode);
int steps = , dis1 = , dis2 = ;
while(!que.empty()){
int cnt = que.size();
while(cnt --){
TreeNode* cur = que.front();
que.pop();
if(cur == n1){
dis1 = steps;
}if(cur == n2){
dis2 = steps;
}
if(cur -> left)
que.push(cur -> left);
if(cur -> right)
que.push(cur -> right);
}
steps ++;
}
return dis1 + dis2;
}TreeNode *getComAscNode(TreeNode * minNode, TreeNode *maxNode)
{
int len1 = height(minNode);
int len2 = height(maxNode);
for(;len1 > min(len1, len2); len1 --)
minNode = parents[minNode -> val];
for(;len2 > min(len1, len2); len2 --)
maxNode = parents[maxNode -> val];
while(minNode != maxNode){
minNode = parents[minNode -> val];
maxNode = parents[maxNode -> val];
}
return minNode;
}
int getDis(TreeNode* root)
{
minNode = new TreeNode(INF);
maxNode = new TreeNode(-INF);
travelNodes(root, NULL);
TreeNode *comAscNode = getComAscNode(minNode, maxNode);
return disToCANone(comAscNode, minNode, maxNode);}
TreeNode* minNode, *maxNode;};
上面这种方法有局限性，如果树中节点的value必须不同才可以。下面优化成 任意树，使用map来存parent。这道题是 LeetCode
https://leetcode.com/problems/lowest-common-ancestor-of-a-binary-tree/#/description 仅仅是求LCA的。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
void calcPath(TreeNode* root){
queue<TreeNode*>que;
que.push(root);
while(!que.empty()){
TreeNode *p = que.front();
que.pop();
if(p -> left){
parent[p -> left] = p;
que.push(p -> left);
}if(p -> right){
parent[p -> right] = p;
que.push(p -> right);
}
}
} TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == NULL) return NULL;
vector<TreeNode*>pathP;
vector<TreeNode*>pathQ;
calcPath(root); // 求每个节点的parent
// 得到p and q到根节点的路径
TreeNode *tp = p, *tq = q;
pathP.push_back(p);
while(parent[tp]){
pathP.push_back(parent[tp]);
tp = parent[tp];
}
pathQ.push_back(q);
while(parent[tq]){
pathQ.push_back(parent[tq]);
tq = parent[tq];
}
// 将路径反序
reverse(pathP.begin(), pathP.end());
reverse(pathQ.begin(), pathQ.end()); // 从rt出发找到最近祖先
int i = , len = min(pathP.size(), pathQ.size());
TreeNode *ans = NULL;
while(i < len){
if(pathP[i] == pathQ[i]){
ans = pathP[i];
}else{
break;
}
i ++;
}
return ans;
}
map<TreeNode*, TreeNode*>parent;
};
3。
有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(K在1到n之间)，请返回第K大的数，保证答案存在。
测试样例：
[1,3,5,2,2],5,3
返回：2
Ans：
//快拍的partition，记住key = a[l], 先从后向前找，这样保证每次循环交换两次，key依然在a[i]的位置上。
int partition(vector<int>&a, int l, int r)
{
int key = a[l];
while(l < r){
while(l < r && a[r] <= key) r --;
swap(a[l], a[r]);
while(l < r && a[l] >= key) l ++;
swap(a[l], a[r]);
}
return l;
} int findKthQSort(vector<int>&a, int l, int r, int k)
{ int m = partition(a, l, r);
if(m - l + == k) return a[m];
else if(m - l + > k){
return findKthQSort(a, l, m - , k);//出现在前半段，因为算上第m个数依然>k个 所以要去掉第m个数，否则会死循环
}else{
return findKthQSort(a, m + , r, k - (m - l + )); //这个很重要，如果前面已经包含了(m - l + 1)个大的数，那么第k大的数将变成第k - (m - l + 1)大的数，且出现在后半段中
} } int findKth(vector<int> a, int n, int K) {
// write code here
return findKthQSort(a, , n - , K);
}
