牛客网-3 网易编程题（1拓扑&2二叉树的公共最近祖先&3快排找第K大数）

小明陪小红去看钻石，他们从一堆钻石中随机抽取两颗并比较她们的重量。这些钻石的重量各不相同。在他们们比较了一段时间后，它们看中了两颗钻石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[9999];
        for(int i = 1; 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 = 0; 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 = 0; i <= n; i ++){
            g[i].clear();
        }
        for(int i = 0; i < (int)records.size(); i ++){
            int u = records[i][0], v = records[i][1];
            g[u].push_back(v);
        }
         
        if(g1 == g2){
            return -999;
        }
        bool g1A = canArr(g1, g2, n), g2A = canArr(g2, g1, n);
        if(g1A){
            return 1;
        }else if(g2A){
            return -1;
        }else{
            return 0;
        }
    }
private:
    vector<int>g[9999];
};

　　dfs会TorSegment Error。以后能用ＢＦＳ还是首选宽度优先搜索吧！

有一棵二叉树，树上每个点标有权值，权值各不相同，请设计一个算法算出权值最大的叶节点到权值最小的叶节点的距离。二叉树每条边的距离为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[2000];
 
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 = 0;
    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 = 0, dis1 = 0, dis2 = 0;
    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 = 0, 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 + 1 == k) return a[m];
            else if(m - l + 1 > k){
                return findKthQSort(a, l, m - 1, k);//出现在前半段，因为算上第m个数依然>k个 所以要去掉第m个数，否则会死循环
            }else{
                return findKthQSort(a, m + 1, r, k - (m - l + 1)); //这个很重要，如果前面已经包含了(m - l + 1)个大的数，那么第k大的数将变成第k - (m - l + 1)大的数，且出现在后半段中
            }

    }

    int findKth(vector<int> a, int n, int K) {
        // write code here
        return findKthQSort(a, 0, n - 1, K);
    }