dfs+备忘录解决方案在leetcode上的应用

我试图在竞赛中解决这个问题(现在完成了) on LeetCode .

在一组n个人(标记为0、1、2、…、n-1)中,每个人都有 不同数额的钱,不同程度的安静。

为了方便起见,我们将标签为X的人称为“人” X”。

我们会说,如果X人确实有更多的 比Y人有钱。请注意,富人可能只是有效的 观察。

另外,如果x有安静的q,我们就说安静[x]=q。

现在,返回answer,如果y是最不安静的人,那么answer[x]=y (即,最小值为quiet[y]的人y),其中 绝对比X人有钱的人。

例1:

输入:Richer=[[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]],安静= [3,2,5,4,6,1,7,0]输出:[5,5,2,5,4,5,6,7]说明:答案[0]= 5。人5比3有钱,3比1有钱,1比0有钱。唯一比较安静的人 安静的[X]是7号人物,但不清楚他们是否比 人0。

答案[7]=7。在所有的人当中 比第7个人(可能是第3、4、5、6或7个人)多的钱, 最安静的人(安静程度较低[x])是第7个人。

其他答案可以用类似的推理来填充。

输入中没有周期。

这看起来像一个直接的dfs问题,我们跟踪 quietness 路径中的节点。

我的解决办法是

class Solution {
 public:
  int doDFS(unordered_map<int, bool>& visited,
            unordered_map<int, vector<int> > graph, vector<int>& quiet,
            vector<int>& answer, int current) {
    if (visited.find(current) != visited.end()) {
      return answer[current];
    }
    int current_min = current;
    for (int i = 0; i < graph[current].size(); ++i) {
      int min_y = doDFS(visited, graph, quiet, answer, graph[current][i]);
      if (quiet[current_min] > quiet[min_y]) {
        current_min = min_y;
      }
    }
    answer[current] = current_min;
    visited[current] = true;
    return answer[current];
  }
  vector<int> loudAndRich(vector<vector<int> >& richer, vector<int>& quiet) {
    // vector<vector<int>> graph(quiet.size(), vector<int>());
    unordered_map<int, vector<int> > graph;
    vector<int> answer(quiet.size());
    unordered_map<int, bool> visited;
    for (int i = 0; i < richer.size(); ++i) {
      // cout << richer[i][1] << ' ' << richer[i][0] << endl;
      if (graph.find(richer[i][1]) == graph.end()) {
        graph.insert({richer[i][1], vector<int>{richer[i][0]}});
      } else {
        graph[richer[i][1]].push_back(richer[i][0]);
      }
    }
    for (int i = 0; i < quiet.size(); ++i) {
      if (visited.find(i) == visited.end()) {
        doDFS(visited, graph, quiet, answer, i);
      }
    }

    return answer;
  }
};

但我不能接受这一点它被超时为更大的投入。 此解决方案的运行时为 O(N) 因为我们只访问每个节点一次。

有人能帮我解释一下为什么这会超时吗?