Re: [閒聊] 每日leetcode已回收
看板Marginalman作者Neuenmuller (蘇菲・諾伊恩謬拉)時間1年前 (2024/07/13 06:14)推噓1(1推 0噓 0→)留言1則, 1人參與討論串483/1552 (看更多)
1717. Maximum Score From Removing Substrings
原本我也想說這個該不會是DP吧
弄了老半天結果這個做Greedy會是最佳解
那就跟檢查括號有沒有對應的題目差不多
就一個stack然後東西放進去，match到的話就pop
class Solution {
public:
int removeSubstr(string &s, const string &p, int score) {
int totalScore = 0;
string temp;
for (char c: s) {
if (!temp.empty() && temp.back() == p[0] && c == p[1]) {
temp.pop_back();
totalScore += score;
}
else
temp.push_back(c);
}
s = temp;
return totalScore;
}
int maximumGain(string s, int x, int y) {
int score = 0;
string firstPass = (x > y)? "ab": "ba";
string secondPass = (x > y)? "ba": "ab";
score += removeSubstr(s, firstPass, max(x, y));
score += removeSubstr(s, secondPass, min(x, y));
return score;
}
};
寫完之後想到一件事
removeSubstr有side effect其實這樣寫蠻醜的
--
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.1720822476.A.118.html
推
07/13 06:16,
1年前
, 1F
07/13 06:16, 1F
討論串 (同標題文章)
完整討論串 (本文為第 483 之 1552 篇)：