Re: [閒聊] 每日LeetCode

看板Marginalman作者Rushia (みけねこ的鼻屎)時間1年前 (2022/10/03 11:26)推噓5(5推 0噓 1→)

留言6則, 6人參與討論串26/719 (看更多)

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