→ sustainer123: 美國工作484還很難找R 我聽兩個朋友找不到實習 07/12 06:42
→ Neuenmuller: 跟之前比好像沒有好多少 07/12 07:46
推 orangeNoob: 大師 07/12 10:23
1190. Reverse Substrings Between Each Pair of Parentheses
今天聽到客戶公司裁了快兩千人覺得應該要回來寫Leetcode了
以防萬一
原本作法跟上面幾個都八成像所以就不講了，
就一個vector的string，每次遇到')'就把最尾端的string pop出來之後
反轉塞回去vector最尾
但是後來發現有更快一點的作法
而且還是我去年寫的，我好像越變越爛欸
不然就是我從哪邊抄來的，只是我忘記了
---
我們一個一個字元讀進來的時候遇到')'會把括號範圍內的字元都翻轉一次
其實我們只需要紀錄每個'('的位置就好，遇到')'就把前一個上括號位置到最後面
做一次reverse
這樣的話可以少掉複製的成本然後變快一點，大概
class Solution {
public:
string reverseParentheses(string s) {
string output;
vector<int> temp;
for (char c: s) {
if (c == '(') {
temp.push_back(output.size());
}
else if (c == ')') {
reverse(output.begin() + temp.back(), output.end());
temp.pop_back();
}
else {
output.push_back(c);
}
}
return output;
}
};
--
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), 來自: 72.190.48.202 (美國)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720736682.A.67D.html