C语言重构【1578】避免重复字母的最小删除成本

朴灿烈づ我的快乐病毒、 2022-10-29 12:28 149阅读 0赞

### 文章目录 ###

*   *   *   *  所有题目源代码：\[Git地址\](https://github.com/ch98road/leetcode)
             *  题目
             *  方案：
             *   *  复杂度计算

#### 所有题目源代码：[Git地址][Git] ####

#### 题目 ####

给你一个字符串 s 和一个整数数组 cost ，其中 cost[i] 是从 s 中删除字符 i 的代价。
    
    返回使字符串任意相邻两个字母不相同的最小删除成本。
    
    请注意，删除一个字符后，删除其他字符的成本不会改变。
    
     
    
    示例 1：
    
    输入：s = "abaac", cost = [1,2,3,4,5]
    输出：3
    解释：删除字母 "a" 的成本为 3，然后得到 "abac"（字符串中相邻两个字母不相同）。
    示例 2：
    
    输入：s = "abc", cost = [1,2,3]
    输出：0
    解释：无需删除任何字母，因为字符串中不存在相邻两个字母相同的情况。
    示例 3：
    
    输入：s = "aabaa", cost = [1,2,3,4,1]
    输出：2
    解释：删除第一个和最后一个字母，得到字符串 ("aba") 。
     
    
    提示：
    
    s.length == cost.length
    1 <= s.length, cost.length <= 10^5
    1 <= cost[i] <= 10^4
    s 中只含有小写英文字母

#### 方案： ####

*  贪心思想
    
     *  原本sum是这样的sum+= min(cost\[i\],cost\[i-1\])，但是考虑到连续三个以上相同且大小为1>2<3,这种情况就会删除两次2，故需分类讨论下，需要注意的是cost最终怎么变不重要，重要的是sum的值对了就行。

class Solution
    { 
    public:
        int minCost(string s, vector<int> &cost)
        { 
            int len = cost.size();
            int sum = 0;
            for (int i = 1; i < len; i++)
            { 
                if (s[i] == s[i - 1])
                { 
                    if (cost[i] < cost[i - 1])
                    { 
                        sum += cost[i];
                        cost[i] = cost[i - 1];
                    }
                    else
                    { 
                        sum += cost[i - 1];
                    }
                }
            }
            return sum;
        }
    };

##### 复杂度计算 #####

*  时间复杂度：O(n)
 *  空间复杂度：O(1)

[Git]: https://github.com/ch98road/leetcode