情境模擬題 隔板的放置方法數 Ways to Divide a Long Corridor_Leetcode #2147

Annie Spratt on Unsplash

題目敘述

題目會給我們一個corridor陣列，裡面代表盆栽和座位的分布，P代表Plant盆栽，S代表Seat座位。要求我們依照佈置規則放置隔板，計算總共有幾個合法的隔板分割方法數?

規則:

每兩個座位視為一組，每兩組之間的盆栽所產生的空位，皆可放置一片隔板。

每一組分割內必須恰好包含兩個座位，不多也不少。

最後回傳答案之前，記得對10⁹ + 7做除法取餘數。

詳細的題目可在這裡看到

測試範例

Example 1:

Input: corridor = "SSPPSPS"
Output: 3
Explanation: There are 3 different ways to divide the corridor.
The black bars in the above image indicate the two room dividers already installed.
Note that in each of the ways, each section has exactly two seats.

Example 2:

Input: corridor = "PPSPSP"
Output: 1
Explanation: There is only 1 way to divide the corridor, by not installing any additional dividers.
Installing any would create some section that does not have exactly two seats.

Example 3:

Input: corridor = "S"
Output: 0
Explanation: There is no way to divide the corridor because there will always be a section that does not have exactly two seats.

約束條件

Constraints:

• n == corridor.length
• 1 <= n <= 10^5
• corridor[i] is either 'S' or 'P'.

演算法

Seat Seat Plant ... Plant Seat Seat
         ^     ^   ^     ^
         
^ : 合法的隔板位置，也是合法的分割位置

依照規則進行模擬，每一組內一定恰好包含兩個座位。

每一組座位之間的盆栽所產生的空位，皆是合法的分割位置。

舉例來說，如果輸入是SSPPPSS，

那麼中間的空格數 = 5 - 1 = 4

= 3個盆栽所產生的空位 = 合法的分割位置總數

= 合法的分割數目

最後，依照排列組合的乘法原理，把每一組座位之間的分割方法數相乘，

再對10⁹ + 7做除法取餘數，就是最終答案。

程式碼

class Solution:
　def numberOfWays(self, corridor: str) -> int:
　　
　　# total seat count
　　seatCount = 0

　　# lastest seat seen before on the left hand side
　　lastSeen = -1

　　# valid partition
　　split = 1

　　for i, seat in enumerate(corridor):

　　　if seat == 'P':
　　　　continue

　　　seatCount += 1

　　　# Try to divide on every two seats
　　　if seatCount >= 2 and seatCount % 2 == 1:
　　　　split *= (i - lastSeen )
　　　　split %= (10**9 + 7)
　　　
　　　# update last seen position of seat
　　　lastSeen = i
　　
　　if seatCount >= 2 and seatCount % 2 == 0:
　　　# Valid partition exists only when there are even number of seats
　　　return split
　　
　　return 0

複雜度分析

時間複雜度:

O( n ) 依次從左到右的線性掃描，長度為O(n) 和原本的輸入陣列一樣長。

空間複雜度:

O( 1 ) 使用到的是固定大小的臨時變數，尺寸皆為O(1)。

關鍵知識點

關鍵在於經過範例、規則找出規律，任意兩組之間的盆栽空位皆是合法的分割位置。

最後，依照題意，依據乘法原理相乘，即可得所有合法分割的方法數。

Reference:

[1] Python O(n) by greedy partition [w/ Comment] - Number of Ways to Divide a Long Corridor - LeetCode