Re: [閒聊] 每日leetcode已回收

看板Marginalman作者involution ( )時間1年前 (2024/07/12 15:41)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串478/1548 (看更多)

※ 引述《oin1104 (是oin的說)》之銘言： : 題目: : 給你一個字串 : 你可以消除中間的ab得到x分 : 或是消除中間的ba得到y分 : 問你最多能得幾分 : 思路: : 題目的重點就是 : 像是aba : 如果x>y就要選擇ab的組合得到x分 : 然後消除ab : 不然就是ba : 所以需要對兩種情況做stack : 然後要stack兩次 : 寫成函式之後比較簡潔了想了一下好像不需要真的建一個 stack 先假設 x >= y, 優先消 ab 的結果就會保證 stack 裡一定是 bbbaaaaaa 這種形式，所以只要紀錄 b 的數量和 a 的數量就好了來 b 就優先把 a 消掉，沒 a 才疊上去來 a 就先保留再來就是為什麼可以 greedy 取 ab 假如看到一個任意的 'ab' 兩個一定至少一個會被消掉，否則最後把這個 ab 消掉就更高分了矛盾如果不直接消這個 ab，那要嘛 a 和左邊的其他 b 消要嘛 b 和右邊的其他 a 消兩種都不如直接消 ab，因為留下來的字串相同而消 ab 分數更高隨便寫的醜 code, 能過就好 int maximumGain(string s, int x, int y) { s += 'c'; char a = 'a', b = 'b'; if (x < y) { swap(a, b); swap(x, y); } // x >= y, choose ab int b_cnt = 0, a_cnt = 0, ans = 0; for (char c : s) { if (c == a) { a_cnt += 1; } else if (c == b) { if (a_cnt) { ans += x; a_cnt -= 1; } else { b_cnt += 1; } } else { ans += y * min(b_cnt, a_cnt); a_cnt = 0; b_cnt = 0; } } return ans; } -- https://i.imgur.com/Dqgtk4P.gif