{"id":5138,"date":"2019-05-04T10:25:32","date_gmt":"2019-05-04T17:25:32","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=5138"},"modified":"2019-05-04T10:37:27","modified_gmt":"2019-05-04T17:37:27","slug":"leetcode-851-loud-and-rich","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-851-loud-and-rich\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 851. Loud and Rich"},"content":{"rendered":"\n

In a group of N people (labelled 0, 1, 2, ..., N-1<\/code>), each person has different amounts of money, and different levels of quietness.<\/p>\n\n\n\n

For convenience, we’ll call the person with label x<\/code>, simply “person x<\/code>“.<\/p>\n\n\n\n

We’ll say that richer[i] = [x, y]<\/code> if person x<\/code> definitely has more money than person y<\/code>.  Note that richer<\/code> may only be a subset of valid observations.<\/p>\n\n\n\n

Also, we’ll say quiet[x] = q<\/code> if person x has quietness q<\/code>.<\/p>\n\n\n\n

Now, return answer<\/code>, where answer[x] = y<\/code> if y<\/code> is the least quiet person (that is, the person y<\/code> with the smallest value of quiet[y]<\/code>), among all people who definitely have equal to or more money than person x<\/code>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

Input: <\/strong>richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]\nOutput: <\/strong>[5,5,2,5,4,5,6,7]\nExplanation: <\/strong>\nanswer[0] = 5.\nPerson 5 has more money than 3, which has more money than 1, which has more money than 0.\nThe only person who is quieter (has lower quiet[x]) is person 7, but\nit isn't clear if they have more money than person 0.\n\nanswer[7] = 7.\nAmong all people that definitely have equal to or more money than person 7\n(which could be persons 3, 4, 5, 6, or 7), the person who is the quietest (has lower quiet[x])\nis person 7.\n\nThe other answers can be filled out with similar reasoning.\n<\/pre>\n\n\n\n
Note:<\/strong><\/p>\n\n\n\n
  1. 1 <= quiet.length = N <= 500<\/code><\/li>
  2. 0 <= quiet[i] < N<\/code>, all quiet[i]<\/code> are different.<\/li>
  3. 0 <= richer.length <= N * (N-1) \/ 2<\/code><\/li>
  4. 0 <= richer[i][j] < N<\/code><\/li>
  5. richer[i][0] != richer[i][1]<\/code><\/li>
  6. richer[i]<\/code>‘s are all different.<\/li>
  7. The observations in richer<\/code> are all logically consistent.<\/li><\/ol>\n\n\n\n
    Solution: DFS + Memoization<\/strong><\/p>\n\n\n\n
    For person i , remember the quietest person who is richer than person i.<\/p>\n\n\n\n
    Time complexity: O(n^2)
    Space complexity: O(n)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua, running time: 108 ms, 31.6 MB\nclass Solution {\npublic:\n  vector loudAndRich(vector>& richer, vector& quiet) {\n    const int n = quiet.size();\n    vector> g(n);\n    for (const auto& r : richer)\n      g[r[1]].push_back(r[0]);\n    vector ans(n, -1);\n    function dfs = [&](int i) {\n      if (ans[i] != -1) return;\n      ans[i] = i;\n      for (int j : g[i]) {\n        dfs(j);\n        if (quiet[ans[j]] < quiet[ans[i]])\n          ans[i] = ans[j];\n      }      \n    };\n    for (int i = 0; i < n; ++i) dfs(i);\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    In a group of N people (labelled 0, 1, 2, …, N-1), each person has different amounts of money, and different levels of quietness. For convenience,…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[33,77],"class_list":["post-5138","post","type-post","status-publish","format-standard","hentry","category-graph","tag-dfs","tag-graph","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5138","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5138"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5138\/revisions"}],"predecessor-version":[{"id":5141,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5138\/revisions\/5141"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5138"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5138"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5138"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}