推 a1234555: 我彷彿看到溫莎 10/03 11:27
※ 編輯: Rushia (1.160.85.207 臺灣), 10/03/2022 11:29:07
推 Jaka: 大師 10/03 11:29
推 an94mod0: 幹嘛換帳號 10/03 11:30
→ Rushia: 程序問題 10/03 11:30
推 JerryChungYC: 大師 10/03 12:31
推 pandix: 大師 10/03 12:49
1578. Minimum Time to Make Rope Colorful
Alice有一個綁滿各種顏色氣球的繩子，因為他想要繩子的顏色看起來更多彩，所以
兩個相同顏色的氣球不能放在一起要移除，若移除每個氣球要耗費不同時間求出讓
繩子是多彩要耗費的最小時間。
思路：
1.貪婪演算法，對相同顏色的氣球序列的最大成本進行貪婪（盡可能不拿成本最高的
氣球），每次成本都累加較小的氣球成本
2.pre用來判斷上一個走訪的氣球之顏色
3.remain保留較大的氣球成本（剩下的），利用一個布林first來判斷remain的初始值
並把remain和當前的比
Java Code：
class Solution {
public int minCost(String colors, int[] neededTime) {
int cost = 0, n = neededTime.length, remain = 0;
boolean first = true;
char pre = colors.charAt(0);
for(int i = 1; i < n; i++) {
// 如果連續兩個氣球顏色一樣
if(pre == colors.charAt(i)) {
// 依照是否是第一次比決定要和哪個比
if(first) {
cost += Math.min(neededTime[i - 1], neededTime[i]);
remain = Math.max(neededTime[i - 1], neededTime[i]);
} else {
cost += Math.min(remain, neededTime[i]);
remain = Math.max(remain, neededTime[i]);
}
first = false;
}
else {
first = true;
}
pre = colors.charAt(i);
}
return cost;
}
}
感覺寫的很醜 我漬鯊
--
https://i.imgur.com/uiFto42.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.160.85.207 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1664767594.A.DB4.html