Re: [閒聊] 每日leetcode

[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;
}
--------------------------------------------

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 122.100.73.13 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720772349.A.A60.html
推 oin1104: 大師
→ DJYOMIYAHINA: 別捲了