题解 | #算法交流群#

题目描述
牛牛有一个算法交流群，它是这个群的群主，也是这个群实力最强的人。

算法交流群里一共有n个人，每个人都有一个等级ai表示它能解决难度小于等于ai的算法问题。

除了牛牛以外，群里的每个编号为i的人都在群里有一个等级比他高的朋友编号为pi。群友 i 会解决那些他产生和接收的等级小于等于ai的问题，并把解决不了的问题全部交给pi。

保证牛牛的编号为1。保证牛牛的等级全场唯一且全场最高。如果牛牛解决不了他接收的问题，他将不管这些问题。

这天群里的每个人都产生了一个问题，牛牛知道了每个人产生问题等级ki，他想知道群里的每个人在这天解决了多少问题。

方法一：暴力解法

求解思路
对于本题目的求解，我们可以把牛牛看作树的根节点，其余群友看作树的枝叶，如果某一位群友不能解决问题，那么就顺着这个群友向上寻找等级比他高的人，也即寻找该节点的父节点。并且同时我们用一个数组来记录问题最终是被哪个群友解决的，基于上述思路，我们便可以得到本问题的答案。

图片说明

解题代码

class Solution:
    def solve(self , n , a , p , k ):
        myres = [0]*n # 返回数组
        dic ={} # 存储每个人i遇到等级v时候最终对应的解决人是谁
        for i,v in enumerate(k): # 遍历
            if a[i]>=v: # 如果能力值大于问题等级
                dic[(i,v)] = i
                myres[i]+=1
            else:
                t = i
                while t!=0 and a[i]<v:
                    t = p[t-1] -1
                    if (t,v) in dic:
                        myres[dic[(t,v)]]+=1
                        break
                    if a[t]>=v: # 如果 t的能力值大于问题等级则加入字典
                        dic[(i,v)]=t
                        myres[t]+=1
                        break
        return myres # 返回结果即可

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用辅助数组dic[N]来记录求解问题的人，引入额外的内存地址空间，因此空间复杂度为 $O(N)$

方法二：优化解法

求解思路
对于本题的解法，我们可以对其做出优化。因为牛牛的等级为最高，我们给牛牛一个权值1，其在[0,1]权值中为最大。我们发现从根到结点的路径上，点的权值与点到根的距离有关，距离越远其相应的权值越小，并且满足二分性质。根据上述思路，我们使用类二分的方法对本题进行解决。

图片说明

解题代码

class Solution {
public:
    int f[100005][20];
    vector<int> g[100005];
    void dfs(int u)
    {   //定义搜索方式
        for(int i = 0; i < 19; ++i) f[u][i+1] = f[f[u][i]][i];
        for(int i = 0; i < g[u].size(); ++i) dfs(g[u][i]);
    }
    vector<int> solve(int n, vector<int>& a, vector<int>& p, vector<int>& k)
    {
        vector<int> myans(n, 0);
        for(int i = 0; i <= n; ++i)
            g[i].clear();
        memset(f, 0, sizeof f); // 声明记录解题人的数组
        for(int i = 0; i < n-1; ++i) f[i+2][0] = p[i],g[p[i]].push_back(i+2) ;
        dfs(1);
        if(k[0] <= a[0]) myans[0]++;
        for(int i = 1; i < n; ++i)
        {
            if(k[i] <= a[i]) // 如果满足条件，则myans++
            {
                myans[i]++; 
                continue;
            }
            int u = i+1;
            for(int j = 18; j >= 0; --j) // 使用二分法的思路进行求解
            {
                if(f[u][j] == 0) continue;
                int t = f[u][j];
                if(k[i] > a[t-1]) u = t;
            }
            u = f[u][0];
            if(u == 0) continue;
            else myans[u-1]++;
        }
        return myans; // 返回结果即可
    }
};

复杂度分析
时间复杂度：一层循环，因此时间复杂度为 $O(N)$
空间复杂度：使用常数级内存地址空间，因此空间复杂度为 $O(1)$