作者DJYOMIYAHINA (通通打死)
看板Marginalman
標題Re: [閒聊] 每日leetcode
時間Fri Jul 12 23:33:02 2024
一開始想用DP
幹發現怎麼都D不太出來:(
後來發現好像不管先碰ab或先碰ba,最後總共碰的次數都會一樣
(不會因為某個地方選擇碰ba不碰ab,造成後面總共碰的對數少了幾對)
總而言之就變成說
若y>x,就先全碰ba,最後再來處理ab
反之就先全碰ab,最後再來處理ba
大概是這樣
寫得醜醜:(
def maximumGain(self, s: str, x: int, y: int) -> int:
stk = []
score = 0
for c in s:
if x >= y:
if stk and stk[-1] == 'a' and c == 'b':
stk.pop()
score += x
else:
stk.append(c)
else:
if stk and stk[-1] == 'b' and c == 'a':
stk.pop()
score += y
else:
stk.append(c)
stk2 = []
for c in stk:
if stk2 and stk2[-1] == 'a' and c == 'b':
stk2.pop()
score += x
elif stk2 and stk2[-1] == 'b' and c == 'a':
stk2.pop()
score += y
else:
stk2.append(c)
return score
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1720798384.A.EB7.html
推 Sadolapapa: 大師 07/12 23:39