→ SiranuiFlare: 大師 10/03 09:13
推 Jaka: 大師 10/03 09:20
推 Ericz7000: 大師 10/03 09:21
推 JerryChungYC: 大師 10/03 09:21
推 sustainer123: 大師 10/03 09:23
推 scmono: 大師 10/03 09:44
→ Rushia: 大師 10/03 11:34
今天的每日一題：
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
想法就是，把相鄰同色的都分成一群： rr | ggg | bb
每群只能留下一個，其他都要移除，所以會選擇留下所需時間最大的
我的作法是遇到相鄰的兩個同色氣球，就把小的那個拔掉
繼續和下一個比，如果又同色，就會再把其中比較小的拔掉
最後就會剩下最大的
會用變數 pre 去紀錄上一個氣球的 index
(因為有被拔的話上一個氣球就不是單純index-1)
如果上一顆和目前的氣球顏色一樣的話就拔掉花費小的
class Solution {
public:
int minCost(string colors, vector<int>& neededTime) {
int n = colors.length();
int ans = 0;
int pre = 0;
for (int now = 1; now < n; now++) {
if (colors[now] != colors[pre]) {
pre = now;
} else if (neededTime[now] > neededTime[pre]) {
ans += neededTime[pre];
pre = now;
} else { // neededTime[now] <= neededTime[pre]
ans += neededTime[now];
// pre = pre
}
}
return ans;
}
};
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.16.175 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664759557.A.218.html