推 oin1104: 大師 11/28 11:27
推 Neuenmuller: 大師 11/28 11:41
推 leafff: 大師 11/29 00:17
→ leafff: 是說這題憑什麼hard啊 不就用乘法的排列組合嗎 11/29 00:17
→ ZooseWu: 不知道 leetcode有時候難度都怪怪的 11/29 11:06
2147. Number of Ways to Divide a Long Corridor
你在一個圖書館走廊
開頭跟尾端已經各放好一個屏風
走廊上有很多椅子S跟中型盆栽P排成一列
你要在中間補上屏風
每個屏風中間要剛好有兩個椅子以及不限數量的盆栽
回傳一共有幾種放法(mod 10^9+7)
Input: corridor = "SSPPSPS" Output: 3
|SS|PPSPS|
|SSP|PSPS|
|SSPP|SPS|
Input: corridor = "PPSPSP" Output: 1
|PPSPSP|
Input: corridor = "S" Output: 0
Intuition:
分成椅子已填滿跟未填滿兩種狀態
然後計算可能性乘上去
Approach:
本來要寫FSM
可是後來發現只有兩個狀態就懶了
直接用一個bool切換狀態
計算的時候會分成已填滿跟未填滿兩個狀態
未填滿的話遇到盆栽不做事
遇到座位計數+1
椅子已填滿的話就計算有幾個盆栽就會多幾種擺的可能
然後遇到座位就回到未填滿
未填滿跟填滿的時候count是不同意義
不過我懶得多用一個變數就直接塞進去了
如果是在專案內的話我會分兩個變數用提升可讀性
TS Code:
const mod = 1000000007
function numberOfWays (corridor: string): number {
let result = 1
let count = 0
let isFill = false
const unfilled = (cur: string): void => {
if (cur === 'S') {
if (count === 1) {
isFill = true
return
}
count++
}
}
const filled = (cur: string): void => {
switch (cur) {
case 'S':
result = (result * count) % mod
isFill = false
count = 1
return
case 'P':
count++
return
}
}
for (let i = 0; i < corridor.length; i++) {
isFill ? filled(corridor[i]) : unfilled(corridor[i])
}
if (!isFill && count < 2) return 0
return result
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.32.229.33 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1701142005.A.690.html