→ ZooseWu: 這個解法好優雅 11/28 12:23
推 NTHUlagka: 大師好強 看到你的解法都讓我覺得我是廢物 11/28 17:46
推 leafff: 大師 11/29 00:13
※ 引述《Neuenmuller (蘇菲・諾伊恩謬拉)》之銘言：
: Code 2(參考了Leetcode上solution裡Lee大師的做法):
: class Solution {
: public:
: int numberOfWays(string corridor) {
: long output = 1, count = 0;
: for (int i = 0, j = 0; i < corridor.size(); i++) {
: if (corridor[i] == 'S') {
: count++;
: if (count > 2 && count % 2 == 1) {
: output *= (i - j);
: output %= 1'000'000'007;
: }
: j = i;
: }
: }
: if (!count || count % 2 != 0) return 0;
: return output;
: }
: };
: 用count % 2來數有幾組椅子，count不歸零
: 第一個是用這個來找一組椅子跟下一組椅子比較簡單
: 第二個是如果遇到沒有椅子或是只有奇數個椅子的edge case都可以用count解決
: 另外我原本解裡面的頭尾問題也不用解決
: 這就是大師跟我的差距 :(
lee 的另一個做法我也很喜歡 DP狀態轉移
a, b, c 分別代表目前圈到的區域有0, 1, 2個座位的情況下
方法數有多少
如果遇到座位
0 個座位的情況會變成 1 個座位
1 個座位的情況就變成 2 個座位
2 個座位等於這個區域要強制結束開始畫新區域 而新區域由新座位開始所以也是 1
所以遇到座位時 a, b, c = 0, a+c, b
遇到盆栽的情況就可以考慮要不要畫新區域了
0 或 1 個座位的情況不行 因為還沒圈到 2 個座位
2 個座位的情況就可以選擇要把盆栽圈到目前的區域 或是開始一個新區域
而這個新區域就只有一個盆栽 所以是 0 個座位
也就是 a, b, c = a+c, b, c
最後的話就是看那些合法的狀態 也就是目前的區域要有 2 個座位( 0 個不行)
所以直接回傳 c 就好
Python code:
class Solution:
def numberOfWays(self, corridor: str) -> int:
mod = 10**9+7
a, b, c = 1, 0, 0
for ch in corridor:
if ch == 'S':
a, b, c = 0, a+c, b
else:
a += c
return c % mod
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.165.35.201 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1701145329.A.1FA.html