{"id":8814,"date":"2021-11-27T09:04:46","date_gmt":"2021-11-27T17:04:46","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=8814"},"modified":"2021-11-28T23:14:18","modified_gmt":"2021-11-29T07:14:18","slug":"leetcode-2086-minimum-number-of-buckets-required-to-collect-rainwater-from-houses","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/greedy\/leetcode-2086-minimum-number-of-buckets-required-to-collect-rainwater-from-houses\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2086. Minimum Number of Buckets Required to Collect Rainwater from Houses"},"content":{"rendered":"\n

You are given a 0-index<\/strong>ed<\/strong> string street<\/code>. Each character in street<\/code> is either 'H'<\/code> representing a house or '.'<\/code> representing an empty space.<\/p>\n\n\n\n

You can place buckets on the empty spaces<\/strong> to collect rainwater that falls from the adjacent houses. The rainwater from a house at index i<\/code> is collected if a bucket is placed at index i - 1<\/code> and\/or<\/strong> index i + 1<\/code>. A single bucket, if placed adjacent to two houses, can collect the rainwater from both<\/strong> houses.<\/p>\n\n\n\n

Return the minimum <\/strong>number of buckets needed so that for every<\/strong> house, there is at least<\/strong> one bucket collecting rainwater from it, or <\/em>-1<\/code> if it is impossible.<\/em><\/p>\n\n\n\n

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

Input:<\/strong> street = \"H..H\"\nOutput:<\/strong> 2\nExplanation:<\/strong>\nWe can put buckets at index 1 and index 2.\n\"H..H\" -> \"HBBH\" ('B' denotes where a bucket is placed).\nThe house at index 0 has a bucket to its right, and the house at index 3 has a bucket to its left.\nThus, for every house, there is at least one bucket collecting rainwater from it.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
Input:<\/strong> street = \".H.H.\"\nOutput:<\/strong> 1\nExplanation:<\/strong>\nWe can put a bucket at index 2.\n\".H.H.\" -> \".HBH.\" ('B' denotes where a bucket is placed).\nThe house at index 1 has a bucket to its right, and the house at index 3 has a bucket to its left.\nThus, for every house, there is at least one bucket collecting rainwater from it.\n<\/pre>\n\n\n\n
Example 3:<\/strong><\/p>\n\n\n\n
Input:<\/strong> street = \".HHH.\"\nOutput:<\/strong> -1\nExplanation:<\/strong>\nThere is no empty space to place a bucket to collect the rainwater from the house at index 2.\nThus, it is impossible to collect the rainwater from all the houses.\n<\/pre>\n\n\n\n
Example 4:<\/strong><\/p>\n\n\n\n
Input:<\/strong> street = \"H\"\nOutput:<\/strong> -1\nExplanation:<\/strong>\nThere is no empty space to place a bucket.\nThus, it is impossible to collect the rainwater from the house.\n<\/pre>\n\n\n\n
Example 5:<\/strong><\/p>\n\n\n\n
Input:<\/strong> street = \".\"\nOutput:<\/strong> 0\nExplanation:<\/strong>\nThere is no house to collect water from.\nThus, 0 buckets are needed.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 1 <= street.length <= 105<\/sup><\/code><\/li>
  • street[i]<\/code> is either'H'<\/code> or '.'<\/code>.<\/li><\/ul>\n\n\n\n
    Solution: Greedy<\/strong><\/h2>\n\n\n\n
    Try to put a bucket after a house if possible, otherwise put it before the house, or impossible.<\/p>\n\n\n\n
    Time complexity: O(n)
    Space complexity: O(1)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  int minimumBuckets(string street) {\n    const int n = street.size();\n    int ans = 0;\n    for (int i = 0; i < n; ++i)\n      if (street[i] == 'H')\n        if (i - 1 >= 0 and street[i - 1] == 'B')\n          continue;\n        else if (i + 1 < n and street[i + 1] == '.')\n          street[i + 1] = 'B', ++ans;        \n        else if (i - 1 >= 0 and street[i - 1] == '.')\n          street[i - 1] = 'B', ++ans;\n        else\n          return -1;\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    You are given a 0-indexed string street. Each character in street is either ‘H’ representing a house or ‘.’ representing an empty space. You can place buckets on the empty spaces to collect rainwater that falls…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[51],"tags":[88,177],"class_list":["post-8814","post","type-post","status-publish","format-standard","hentry","category-greedy","tag-greedy","tag-medium","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8814","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=8814"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8814\/revisions"}],"predecessor-version":[{"id":8929,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/8814\/revisions\/8929"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=8814"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=8814"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=8814"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}