題目連結:
題目意譯:
你被給定一個索引值從 0 開始數的字串 street。street 中每個字元只會是 'H'(代表著一間房子)或是 '.'(代表著一個空格)。
你可以在空格上放置桶子去蒐集降落到與此格相鄰的房子之雨水。如果索引值 i - 1 或(且)索引值 i + 1 的位置有放置水桶,則索引值 i 的房子之雨水將會被蒐集。對於單一個水桶,如果其相鄰於兩間房子,則將會從兩間房子同時蒐集雨水。
回傳最少所需之桶子使得對於每間房子都至少有一個桶子來蒐集其雨水。如果不可能,則回傳 -1。
限制:
1 ≦ street.length ≦ 105
street[i] 只會是 'H' 或是 '.'。
範例測資:
範例 1:
輸入: street = "H..H"
輸出: 2
解釋:
我們可以在索引值 1 和 2 放置桶子。
"H..H" -> "HBBH" ('B' 代表著放置的桶子)。
索引值 0 的房子之右側有桶子,而索引值 3 的房子之左側有桶子。
因此,對於每間房子都至少有一個桶子來蒐集其雨水。
範例 2:
輸入: street = ".H.H."
輸出: 1
解釋:
我們可以在索引值 2 放置一個桶子。
".H.H." -> ".HBH." ('B' 代表著放置的桶子)。
索引值 1 的房子之右側有桶子,而索引值 3 的房子之左側有桶子。
因此,對於每間房子都至少有一個桶子來蒐集其雨水。
範例 3:
輸入: street = ".HHH."
輸出: -1
解釋:
沒有空格可以放置桶子去蒐集索引值 2 的房子之雨水。
因此,不可能蒐集到每間房子的雨水。
解題思維:
基本上與
這題雷同。只是本題只需求最少所需之桶子數,不需輸出放置之方法。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。