Re: [閒聊] 每日leetcode已回收
※ 引述《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;
}
--------------------------------------------
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720772349.A.A60.html
推
07/12 16:34,
1年前
, 1F
07/12 16:34, 1F
→
07/12 16:40,
1年前
, 2F
07/12 16:40, 2F
討論串 (同標題文章)