数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++程序：查找移除连续重复字符的最小成本？
假设我们有一个包含小写字母的字符串，并且我们还有一个包含非负值的列表，称为成本，字符串和列表具有相同的长度。我们可以删除字符 s[i] 并花费 costs[i] 的成本，然后 s[i] 和 costs[i] 都将被移除。我们必须找到删除所有连续重复字符的最小成本。
因此，如果输入类似于 s = "xxyyx" nums = [2, 3, 10, 4, 6]，则输出将为 6，因为我们可以删除 s[0] 和 s[3]，总成本为 2 + 4 = 6。
要解决此问题，我们将遵循以下步骤
定义一个栈 st
cost := 0
for 初始化 i := 0，当 i < s 的大小，更新（i 增加 1），执行
如果 st 的大小不为 0 且 st 的顶部元素与 s[i] 相同，则
如果 st 的顶部元素 > nums[i]，则
cost := cost + nums[i]
否则
cost := cost + st 的顶部元素
从 st 中弹出元素
将 i 推入 st
否则
将 i 推入 st
返回 cost
让我们查看以下实现以更好地理解
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int solve(string s, vector<int>& nums) {
stack<int> st;
int cost = 0;
for (int i = 0; i < s.size(); ++i) {
if (st.size() && s[st.top()] == s[i]) {
if (nums[st.top()] > nums[i]) {
cost += nums[i];
} else {
cost += nums[st.top()];
st.pop();
st.push(i);
}
} else {
st.push(i);
}
}
return cost;
}
};
int solve(string s, vector<int>& nums) {
return (new Solution())->solve(s, nums);
}
main(){
vector<int> v = {2, 3, 10, 4, 6};
string s = "xxyyx";
cout << solve(s, v);
}输入
"xxyyx",{2,3,10,4,6}输出
6
更新于： 2020年11月10日
415 次查看
广告