程序查找成本，以便在C ++中删除具有成本的连续重复字符？

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一个包含小写字母的字符串，并且还有一个名为cost的非负值列表，该字符串和列表的长度相同。我们可以删除成本s [i]的字符s [i]，然后同时删除s [i]和costs [i]。我们必须找到删除所有连续重复的字符的最低费用。

因此，如果输入像s =“ xxyyx” nums = [2，3，10，4，6]，那么输出将是6，因为我们可以删除s [0]和s [3]的总成本2 + 4 = 6。

为了解决这个问题，我们将按照以下步骤

  • 定义一个堆栈st

  • 费用：= 0

  • 对于初始化i：= 0，当i <s的大小时，进行更新（将i增加1），请执行以下操作：

    • 推我到圣

    • 如果nums [st of top]> nums [i]，则：

    • 除此以外：

    • 费用：=费用+数字[i]

    • 费用：=费用+数字[顶部]

    • 来自st的pop元素

    • 推我到圣

    • 如果st的大小不为0并且s [top of st]与s [i]相同，则：

    • 除此以外

    • 返回成本

    让我们看一下下面的实现以获得更好的理解

    示例

    #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

    以上是 程序查找成本，以便在C ++中删除具有成本的连续重复字符？ 的全部内容， 来源链接： utcz.com/z/321571.html

    回到顶部