Re: [閒聊] 每日leetcode已回收
看板Marginalman作者sustainer123 (caster )時間1年前 (2024/07/31 07:35)推噓2(2推 0噓 1→)留言3則, 3人參與討論串597/1554 (看更多)
※ 引述《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
推
07/31 07:41,
1年前
, 1F
07/31 07:41, 1F
→
07/31 07:44,
1年前
, 2F
07/31 07:44, 2F
推
07/31 08:22,
1年前
, 3F
07/31 08:22, 3F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 597 之 1554 篇)：