推 PogChampLUL: 你板人均coding大師 10/03 09:39
推 Ericz7000: 大家都會coding 10/03 09:41
推 Jaka: 大師 10/03 09:42
推 JerryChungYC: 大師 10/03 12:22
※ 引述《fxfxxxfxx (愛麗絲)》之銘言：
: 今天的每日一題：
: 1578. Minimum Time to Make Rope Colorful
: 愛麗絲有一排有顏色的氣球，要移除一些氣球讓相鄰的氣球都不同色
: 每個氣球會有相應所需的移除時間，回傳所需要的最短時間
: 輸入：
: colors： 代表氣球的顏色，例如 "rrggbbb"
: neededTime: 代表該氣球所需的移除時間，例如 [1,2,3,4,5,6,7]
: 在這個例子會需要移除成 ".r.g..b"，總共要花 1 + 3 + 5 + 6 = 15
感覺是很簡單的greedy 作法也差不多
連續相同顏色的氣球只有移除時間最長的有資格留著
其他都加到output裡
class Solution:
def minCost(self, colors: str, neededTime: List[int]) -> int:
n = len(colors)
currcolor, currmax = colors[0], neededTime[0]
res = 0
for i in range(1, n):
if currcolor != colors[i]:
currcolor = colors[i]
currmax = neededTime[i]
else:
res += min(currmax, neededTime[i])
currmax = max(currmax, neededTime[i])
return res
--
沒人在乎
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.199.166 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664761038.A.4B3.html