C ++
 Computer >> コンピューター >  >> プログラミング >> C ++

C++で文字列を等しくするための最小スワップ

「x」と「y」の文字のみで構成される同じ長さの2つの文字列s1とs2があるとします。私たちの仕事は、これら2つの文字列を互いに等しくすることです。異なる文字列に属する任意の2文字を交換できます。つまり、s1[i]とs2[j]を交換します。 s1とs2を等しくするために必要なスワップの最小数を見つける必要があります。それが不可能な場合は、-1を返す必要があります。したがって、文字列がs1 =“ xy”およびs2 =“ yx”の場合、出力は2になります。s1[0]とs2 [0]を交換すると、s1 ="yy"、s2="xx"になります。次に、s1[0]とs2[1]を交換します。s1="xy"、s2="xy"。

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

  • x1、x2、y1、y2を0に設定します
  • 0からs1のサイズまでの範囲のiの場合
    • a：=s1 [i]およびb：=s2 [i]
    • aがbと同じでない場合、
      • a =‘x’の場合はx1を増やし、それ以外の場合はy1を1増やします
      • b =‘x’の場合はx2を増やし、それ以外の場合はy2を1増やします
  • （x1 + x2）が奇数または（y1 + y2）が奇数の場合、-1を返します
  • return x1 / 2 + y1 / 2 +（x1 mod 2）* 2
例（C ++）

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   int minimumSwap(string s1, string s2) {
      int x1 = 0, x2 = 0, y1 = 0, y2 = 0;
      for(int i = 0; i < s1.size(); i++){
         char a = s1[i];
         char b = s2[i];
         if(a != b){
            if(a == 'x')x1++;
            else y1++;
            if(b == 'x')x2++;
            else y2++;
         }
      }
      if ((x1 + x2) & 1 || (y1 + y2) & 1)return -1;
      return x1/2 + y1/2 + (x1 % 2) * 2;
   }
};
main(){
   Solution ob;
   cout <<ob.minimumSwap("xy", "yx");
}

入力

"xy"
"yx"

出力

2

  1. C++で2つの文字列を同一にするための最小コスト

    2つの文字列AとBがあり、CostAとCostBのような別の2つのコスト値があるとします。 AとBを同一にするための最小コストを見つける必要があります。文字列から文字を削除できます。文字列Aから削除するためのコストはCostAであり、文字列Bから削除するためのコストはCostBです。文字列からすべての文字を削除するコストは同じです。文字列A=“ wxyz”、B =“ wyzx”、CostAが10、CostBが20であると仮定します。したがって、出力は30になります。両方の文字列からxを削除すると、AとBは同じになります。したがって、コストは10 + 20=30です。 これは最長共通部分列問題

  2. C++で2つの数値文字列を同一にするための最小コスト

    2つの数値文字列AとBがあるとします。AとBを同一にするための最小コストを見つける必要があります。実行できる操作は1つだけです。つまり、文字列から数字を削除できます。数値から数字を削除するためのコストは、数字の値と同じです。文字列A=“ 6789”、B =“ 7859”とすると、Aから6を削除し、Bから5を削除する必要があるため、コストは5 + 6=11になります。 これは最長共通部分列問題のバリエーションの1つです。 AとBからLCSの長さを見つける必要があります。この式を使用することで、最小のコストを得ることができます。 MinimumCost =CostA + CostB−2 ∗ l