DFS + Memoized решение, получающее TLE на LeetCode - PullRequest
Новая
       56

DFS + Memoized решение, получающее TLE на LeetCode

0 голосов
/ 10 июня 2018

Я пытался решить эту проблему в конкурсе (теперь завершено) на LeetCode .

В группе из N человек (с меткой 0, 1, 2,..., N-1), у каждого человека есть разные суммы денег и разные уровни тишины.

Для удобства мы назовем человека с меткой x, просто "person x".

Мы скажем, что богаче [i] = [x, y], если у человека x определенно больше денег, чем у человека y.Обратите внимание, что богаче может быть только подмножество достоверных наблюдений.

Кроме того, мы скажем спокойно [x] = q, если у человека х есть спокойствие q.

Теперь вернем ответ, где ответ[x] = y, если y - наименее тихий человек (то есть человек y с наименьшим значением спокойного [y]), среди всех людей, у которых определенно больше или меньше денег, чем у человека x.

Пример 1:

Ввод: richer = [[1,0], [2,1], [3,1], [3,7], [4,3], [5,3], [6,3]], quiet = [3,2,5,4,6,1,7,0] Вывод: [5,5,2,5,4,5,6,7] Объяснение: ответ [0] = 5. У человека 5 больше денег, чем у 3, у которого больше денег, чем у 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), поскольку мы посещаем каждый узел только один раз.

Может ли кто-нибудь помочь мне с объяснением того, почему истекает время ожидания?

1 Ответ

0 голосов
/ 10 июня 2018

Измените unordered_map<int, vector<int> > graph на unordered_map<int, vector<int> > &graph, вы делаете копию для каждого звонка, который вам звонит.С этим изменением оно принимается.

...