Re: [閒聊] 每日LeetCode
看板Marginalman作者Neuenmuller (蘇菲・諾伊恩謬拉)時間6月前 (2023/11/28 11:40)推噓0(0推 0噓 0→)留言0則, 0人參與討論串554/719 (看更多)
2147. Number of Ways to Divide a Long Corridor
一個string input, S代表椅子，P代表盆栽。
現在一個走道頭尾已經有一個隔板，
如果要再放隔板讓每個空間都一定要有兩個椅子
求總共有幾種放法，答案要mod 1e9+7
範例：
input = "SSPPSPS"
output = 3
放法如下:
"SS|PPSPS"
"SSP|PSPS"
"SSPP|SPS"
如果湊不齊兩張椅子答案就0。
-----
Approach 1:
遍歷一遍，遇到兩張椅子就把兩張椅子+中間盆栽變成一個新的東西(我code裡面把這個叫
做X)。之後再重新遍歷一次，這次數盆栽然後算幾種放法。
另外出於懶惰，第一次寫直接沒想太多直接給一個新的string來暫存重新弄得corridor
所以我的解的空間跟時間複雜度都是O(n)
Code 1: https://pastebin.com/1rN2sKD8
(寫的有點長貼pastebin)
不過這東西直接inplace做也行，而且也不需要把兩張椅子合體
多幾個index來數位置在哪就好
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解決
另外我原本解裡面的頭尾問題也不用解決
這就是大師跟我的差距 :(
--
neuenmuller@atelier:home$ touch plachta
touch: cannot touch 'plachta': Permission denied
neuenmuller@atelier:home$ sudo touch plachta
[sudo] password for neuenmuller:
neuenmuller is not in the sudoers file. This incident will be reported.
neuenmuller@atelier:home$
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 97.99.29.95 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1701142811.A.ECB.html
※ 編輯: Neuenmuller (97.99.29.95 美國), 11/28/2023 11:43:02
討論串 (同標題文章)