Re: [閒聊] 每日leetcode

[Neuenmuller (蘇菲・諾伊恩謬拉)]

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
推 Smallsh: 大師