{"id":2792,"date":"2018-04-29T13:40:07","date_gmt":"2018-04-29T20:40:07","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2792"},"modified":"2018-04-29T13:40:47","modified_gmt":"2018-04-29T20:40:47","slug":"leetcode-825-friends-of-appropriate-ages","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-825-friends-of-appropriate-ages\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 825. Friends Of Appropriate Ages"},"content":{"rendered":"

Problem<\/h1>\n
\n
\n

Some people will make friend requests. The\u00a0list of their ages is given and\u00a0ages[i]<\/code>\u00a0is the age of the\u00a0ith person.<\/p>\n

Person A will NOT friend request person B (B != A) if any of the following conditions are true:<\/p>\n

    \n
  • age[B]\u00a0<= 0.5 * age[A]\u00a0+ 7<\/code><\/li>\n
  • age[B]\u00a0> age[A]<\/code><\/li>\n
  • age[B]\u00a0> 100 &&\u00a0age[A]\u00a0< 100<\/code><\/li>\n<\/ul>\n

    Otherwise, A will friend request B.<\/p>\n

    Note that if\u00a0A requests B, B does not necessarily request A.\u00a0 Also, people will not friend request themselves.<\/p>\n

    How many total friend requests are made?<\/p>\n

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

    Input: <\/strong>[16,16]\r\nOutput: <\/strong>2\r\nExplanation: <\/strong>2 people friend request each other.\r\n<\/pre>\n
    Example 2:<\/strong><\/p>\n
    Input: <\/strong>[16,17,18]\r\nOutput: <\/strong>2\r\nExplanation: <\/strong>Friend requests are made 17 -> 16, 18 -> 17.<\/pre>\n
    Example 3:<\/strong><\/p>\n
    Input: <\/strong>[20,30,100,110,120]\r\nOutput: <\/strong>\r\nExplanation: <\/strong>Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.\r\n<\/pre>\n
    Notes:<\/p>\n
      \n
    • 1 <= ages.length\u00a0<= 20000<\/code>.<\/li>\n
    • 1 <= ages[i] <= 120<\/code>.<\/li>\n<\/ul>\n<\/div>\n<\/div>\n
      Solution: Hashtable<\/strong><\/h1>\n
      Count how many people at each age i.<\/p>\n
      Time complexity: O(n)<\/p>\n
      Space complexity: O(120)<\/p>\n
      C++<\/p>\n
      \/\/ Author: Huahua\r\n\/\/ Running time: 39 ms\r\nclass Solution {\r\npublic:\r\n  int numFriendRequests(vector<int>& ages) {\r\n    const int kMaxAge = 120;\r\n    vector<int> counts(kMaxAge + 1, 0);\r\n    for (const int age : ages)\r\n      ++counts[age];\r\n    int ans = 0;\r\n    for (int A = 1; A <= kMaxAge; ++A) {            \r\n      for (int B = 0.5 * A + 7 + 1; B <= A; ++B)\r\n        ans += counts[A] * (counts[B] - (A == B));\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n
       <\/p>\n","protected":false},"excerpt":{"rendered":"
      Problem Some people will make friend requests. The\u00a0list of their ages is given and\u00a0ages[i]\u00a0is the age of the\u00a0ith person. Person A will NOT friend request…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70],"tags":[82,177],"class_list":["post-2792","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2792","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=2792"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2792\/revisions"}],"predecessor-version":[{"id":2794,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2792\/revisions\/2794"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2792"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2792"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2792"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}