题目描述你正在维护一个项目该项目有n个方法编号从0到n - 1。给你两个整数n和k以及一个二维整数数组invocations其中invocations[i] [a_i, b_i]表示方法a_i调用了方法b_i。已知如果方法k存在一个已知的 bug。那么方法k以及它直接或间接调用的任何方法都被视为可疑方法我们需要从项目中移除这些方法。只有当一组方法没有被这组之外的任何方法调用时这组方法才能被移除。返回一个数组包含移除所有可疑方法后剩下的所有方法。你可以以任意顺序返回答案。如果无法移除所有可疑方法则不移除任何方法。示例 1:输入:n 4, k 1, invocations [[1,2],[0,1],[3,2]]输出:[0,1,2,3]解释:方法 2 和方法 1 是可疑方法但它们分别直接被方法 3 和方法 0 调用。由于方法 3 和方法 0 不是可疑方法我们无法移除任何方法故返回所有方法。示例 2:输入:n 5, k 0, invocations [[1,2],[0,2],[0,1],[3,4]]输出:[3,4]解释:方法 0、方法 1 和方法 2 是可疑方法且没有被任何其他方法直接调用。我们可以移除它们。示例 3:输入:n 3, k 2, invocations [[1,2],[0,1],[2,0]]输出:[]解释:所有方法都是可疑方法。我们可以移除它们。提示1 n 10^50 k n - 10 invocations.length 2 * 10^5invocations[i] [a_i, b_i]0 a_i, b_i n - 1a_i ! b_iinvocations[i] ! invocations[j]苯人思路先找出所有可疑方法再看是否有其他方法调用可疑方法通过率 691 / 775会超时classSolution{public:vectorintremainingMethods(intn,intk,vectorvectorintinvocations){if(invocations.empty()){vectorintanswer(n);iota(answer.begin(),answer.end(),0);answer.erase(answer.begin()k);returnanswer;}vectorintsuspicious(n,0);sort(invocations.begin(),invocations.end());suspicious[k]1;vectorintredis{k};// redis记录: 未遍历过的作为调用者的可疑方法// 构造可疑方法数组suspicious// suspicious值为1即为可疑方法while(!redis.empty()){inttempredis[0];// 取出第一个未遍历过的作为调用者的可疑方法for(autox:invocations){if(x[0]temp){redis.erase(redis.begin());break;}elseif(x[0]temp){if(suspicious[x[1]]1){if(x!invocations.back())continue;}else{suspicious[x[1]]1;redis.emplace_back(x[1]);}}if(xinvocations.back()){redis.erase(redis.begin());break;}}}// 再次遍历,检查可疑方法是否被其他方法调用boolflagfalse;for(autox:invocations){if(suspicious[x[0]]0suspicious[x[1]]1){flagtrue;break;}}if(flag){vectorintanswer(n);iota(answer.begin(),answer.end(),0);returnanswer;}else{vectorintanswer;for(inti0;in;i){if(suspicious[i]!1)answer.emplace_back(i);}returnanswer;}}};优化——二分查找思路不变对实现方法进行了一些优化classSolution{public:vectorintremainingMethods(intn,intk,vectorvectorintinvocations){sort(invocations.begin(),invocations.end());vectorintsuspicious(n,0);suspicious[k]1;queueintq;q.push(k);// BFS 找出所有可疑方法while(!q.empty()){intcallerq.front();q.pop();// 使用二分查找找到第一个 caller 当前值的位置// lower_bound查找第一个不小于给定值(vectorint{caller, -1})的元素位置autoitlower_bound(invocations.begin(),invocations.end(),vectorint{caller,-1});while(it!invocations.end()(*it)[0]caller){intcallee(*it)[1];if(!suspicious[callee]){suspicious[callee]1;q.push(callee);}it;}}// 检查是否有非可疑方法调用了可疑方法boolhasExternalCallfalse;for(autoinv:invocations){if(!suspicious[inv[0]]suspicious[inv[1]]){hasExternalCalltrue;break;}}// 构造结果vectorintanswer;if(hasExternalCall){for(inti0;in;i){answer.push_back(i);}}else{for(inti0;in;i){if(!suspicious[i]){answer.push_back(i);}}}returnanswer;}};标准做法——邻接表classSolution{public:vectorintremainingMethods(intn,intk,vectorvectorintinvocations){// 构建邻接表vectorvectorintgraph(n);for(autoinv:invocations){graph[inv[0]].push_back(inv[1]);}// BFS 标记可疑方法vectorintsuspicious(n,0);queueintq;q.push(k);suspicious[k]1;while(!q.empty()){intcurrq.front();q.pop();for(intnext:graph[curr]){if(!suspicious[next]){suspicious[next]1;q.push(next);}}}// 检查是否有外部调用boolhasExternalCallfalse;for(autoinv:invocations){if(!suspicious[inv[0]]suspicious[inv[1]]){hasExternalCalltrue;break;}}// 构造答案vectorintanswer;if(hasExternalCall){for(inti0;in;i)answer.push_back(i);}else{for(inti0;in;i){if(!suspicious[i])answer.push_back(i);}}returnanswer;}};
)
