推 JIWP: 我好崇拜你 07/31 07:41
→ sustainer123: 你是大師 07/31 07:44
推 SecondRun: 995 07/31 08:22
※ 引述《DJYOMIYAHINA (通通打死)》之銘言：
: 思路:
: for loop 下去
: 每個index的cost都會是
: 刪掉前面所有的'b'跟後面所有的'a'
: 所需要的次數
: 就取所有cost的最小值就可
: def minimumDeletions(self, s: str) -> int:`
: a_cnt = s.count('a')
: a_cnt_cur, b_cnt_cur = 0, 0
: ans = len(s)
: for i,c in enumerate(s):
: if c == 'a':
: a_cnt_cur += 1
: ans = min(ans, b_cnt_cur + (a_cnt - a_cnt_cur))
: else:
: ans = min(ans, b_cnt_cur + (a_cnt - a_cnt_cur))
: b_cnt_cur += 1
: return ans
思路:
整個s走一遍
遇到stack[-1]是b且後面是a
stack就pop()
然後result += 1
其他情況就把c放進stack
Python Code:
class Solution:
def minimumDeletions(self, s: str) -> int:
stack = []
result = 0
for c in s:
if c == "a":
if stack and stack[-1] == "b":
result += 1
stack.pop()
else:
stack.append(c)
return result
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.194.160.111 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1722382544.A.4C8.html