C ++のコストで連続する重複文字を削除するコストを見つけるプログラム？

小文字の文字列があり、コストと呼ばれる負でない値のリストもあるとします。文字列とリストの長さは同じです。 costcosts[i]の文字s[i]を削除すると、s[i]とcosts[i]の両方が削除されます。連続して繰り返されるすべての文字を削除するための最小コストを見つける必要があります。

したがって、入力がs ="xxyyx" nums =[2、3、10、4、6]の場合、s[0]とs[3]を削除して合計コストを計算できるため、出力は6になります。 2 +4=6。

これを解決するために、次の手順に従います

• 1つのスタックstを定義する

• コスト：=0

• 初期化i：=0の場合、i

  • stのサイズが0でなく、s [top ofst]がs[i]と同じである場合、次のようになります。

    • nums [top of st]> nums [i]の場合、次のようになります。

      • コスト：=コスト+ nums [i]

    • それ以外の場合：

      • コスト：=コスト+ nums [top of st]

      • stからのポップ要素

      • iをstに押し込みます

  • それ以外の場合

    • iをstに押し込みます

• 返品費用

理解を深めるために、次の実装を見てみましょう

例

#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