列表

详情

1578. 使绳子变成彩色的最短时间

Alice 把 n 个气球排列在一根绳子上。给你一个下标从 0 开始的字符串 colors ，其中 colors[i] 是第 i 个气球的颜色。

Alice 想要把绳子装扮成 彩色 ，且她不希望两个连续的气球涂着相同的颜色，所以她喊来 Bob 帮忙。Bob 可以从绳子上移除一些气球使绳子变成 彩色 。给你一个下标从 0 开始的整数数组 neededTime ，其中 neededTime[i] 是 Bob 从绳子上移除第 i 个气球需要的时间（以秒为单位）。

返回 Bob 使绳子变成 彩色 需要的 最少时间 。

 

示例 1：

输入：colors = "abaac", neededTime = [1,2,3,4,5]
输出：3
解释：在上图中，'a' 是蓝色，'b' 是红色且 'c' 是绿色。
Bob 可以移除下标 2 的蓝色气球。这将花费 3 秒。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 3 。

示例 2：

输入：colors = "abc", neededTime = [1,2,3]
输出：0
解释：绳子已经是彩色的，Bob 不需要从绳子上移除任何气球。

示例 3：

输入：colors = "aabaa", neededTime = [1,2,3,4,1]
输出：2
解释：Bob 会移除下标 0 和下标 4 处的气球。这两个气球各需要 1 秒来移除。
移除后，不存在两个连续的气球涂着相同的颜色。总时间 = 1 + 1 = 2 。

 

提示：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: int minCost(string colors, vector<int>& neededTime) { } };

golang 解法, 执行用时: 152 ms, 内存消耗: 8.5 MB, 提交时间: 2022-12-05 16:00:24 

func minCost(colors string, neededTime []int) int {
    n := len(colors)
    sum := 0
    for i := 0; i < n-1; i++ {
        if colors[i] == colors[i+1] {
            sum += min(neededTime[i], neededTime[i+1])
            if neededTime[i] > neededTime[i+1] {
                neededTime[i], neededTime[i+1] = neededTime[i+1], neededTime[i]
            }
        }
    }
    return sum
}

func min(x, y int) int { if x > y { return y }; return x }

cpp 解法, 执行用时: 124 ms, 内存消耗: 93.1 MB, 提交时间: 2022-12-05 15:57:00 

// 遍历，找到相同的字母，取成本小的，并将没有消费的成本放在下一次比较的字符成本中。
class Solution {
public:
    int minCost(string s, vector<int>& cost) {
        int n = s.size();
        int sum = 0;
        for(int i = 0;i<n-1;i++)
        {
            if(s[i] == s[i+1])
            {
                sum+= min(cost[i],cost[i+1]); 
                if(cost[i]>cost[i+1])swap(cost[i],cost[i+1]);
            }
        }
        return sum;
    }
};

java 解法, 执行用时: 8 ms, 内存消耗: 49.9 MB, 提交时间: 2022-12-05 15:56:16 

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int i = 0, len = colors.length();
        int ret = 0;
        while (i < len) {
            char ch = colors.charAt(i);
            int maxValue = 0;
            int sum = 0;

            while (i < len && colors.charAt(i) == ch) {
                maxValue = Math.max(maxValue, neededTime[i]);
                sum += neededTime[i];
                i++;
            }
            ret += sum - maxValue;
        }
        return ret;
    }
}

python3 解法, 执行用时: 272 ms, 内存消耗: 23.4 MB, 提交时间: 2022-12-05 15:56:01 

class Solution:
    def minCost(self, colors: str, neededTime: List[int]) -> int:
        i = 0
        length = len(colors)
        ret = 0

        while i < length:
            ch = colors[i]
            maxValue = 0
            total = 0

            while i < length and colors[i] == ch:
                maxValue = max(maxValue, neededTime[i])
                total += neededTime[i]
                i += 1
            
            ret += total - maxValue
        
        return ret

上一题

© 2024 leetcode.cn