Re: [閒聊] 每日leetcode已回收
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/07/12 17:40)推噓1(1推 0噓 1→)留言2則, 2人參與討論串480/1549 (看更多)
※ 引述《Rushia (早瀬ユウカの体操服 )》之銘言：
: ※ 引述《oin1104 (是oin的說)》之銘言：
: : 題目:
: : 給你一個字串
: : 你可以消除中間的ab得到x分
: : 或是消除中間的ba得到y分
: : 問你最多能得幾分
: 思路:
: 1.貪心，如果 ab 得分比較高就先把全部ab刪掉再刪 ba，反之先刪 ba 再刪 ab，這種
: 貪心類型題目我實在不太會證明，我是觀察 ababab 和 ababa 兩個字串分別先刪ab再
: 刪ba，還有ab和ba交錯刪，都是分數高的先刪可以得到更優解。
: java code
: --------------------------------------------
: class Solution {
: public int maximumGain(String s, int x, int y) {
: Score res = new Score();
: res.remain = s;
: if (x > y) {
: helper(res, x, new char[]{'a', 'b'});
: helper(res, y, new char[]{'b', 'a'});
: } else {
: helper(res, y, new char[]{'b', 'a'});
: helper(res, x, new char[]{'a', 'b'});
: }
: return res.val;
: }
: public void helper(Score res, int val, char[] pattern) {
: StringBuilder sb = new StringBuilder();
: String s = res.remain;
: for (int i = 0; i < s.length(); i++) {
: if (s.charAt(i) == pattern[1] && !sb.isEmpty() &&
: sb.charAt(sb.length() - 1) == pattern[0]) {
: res.val += val;
: sb.deleteCharAt(sb.length() - 1);
: } else {
: sb.append(s.charAt(i));
: }
: }
: res.remain = sb.toString();
: }
: }
: class Score {
: int val;
: String remain;
: }
: --------------------------------------------
思路:
差不多 但我看溫莎的才解出來 我本來直接寫好幾種情況
之後寫到邏輯直接壞死
一堆重複的code
後面作成函式就解了
Python Code:
class Solution:
def maximumGain(self, s: str, x: int, y: int) -> int:
def count_substring(goal: list[str], weight: int):
nonlocal result,s
tmp = []
count = 0
for i in range(len(s)):
if tmp and tmp[-1] == goal[0] and s[i] == goal[1]:
tmp.pop()
count += 1
else:
tmp.append(s[i])
result += (weight * count)
s = "".join(tmp)
result = 0
if (x>y):
count_substring(["a","b"],x)
count_substring(["b","a"],y)
else:
count_substring(["b","a"],y)
count_substring(["a","b"],x)
return result
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.136.214.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720777235.A.5C0.html
推
07/12 17:47,
1年前
, 1F
07/12 17:47, 1F
→
07/12 17:48,
1年前
, 2F
07/12 17:48, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 480 之 1549 篇)：