C++ 最小1或K增量要求将字符串转换为另一个给定字符串

给定两个字符串，我们需要通过递增操作将一个字符串转换为另一个字符串，我们可以在单个操作中将字符增加1或K。

要解决这个问题，我们需要通过执行循环增量操作使第一个字符串的所有字符与第二个字符相同。如果两个字符串在相同的索引处的字符相同，则我们不需要执行任何增量操作。

问题陈述 - 我们给出了两个名为first和second的字符串，包含大写字母字符。两个字符串的长度为N。还给出了一个正整数K，表示我们可以将字符递增1或K个。我们需要找到将字符串从first转换为second的总循环增量次数。

示例

输入 - first = “ACSQ”，second = “BCOS”，K = 7

输出 - 7

解释

• 要将A转换为B，我们需要进行1次递增操作。

• 要将C转换为C，我们需要执行0次操作。

• 要将S转换为O，我们需要进行22次循环递增。我们可以执行（K = 3）7次增量的操作和1次1增量的操作。我们需要总共4次操作。

• 要将Q转换为S，我们需要2次增量。因此，所需的总操作次数为2，因为我们需要将Q转换为R，R转换为S。

• 所需的总操作次数是1 + 0 + 4 + 2 = 7。

  输入 - first = “ACSQ”，second = “BCOS”，K = 9

  输出 - 0

  解释 - 我们不需要执行任何增量操作，因为两个字符串的所有字符都相同。

  输入 - first = “AB”，second = “FG”，K = 6

  输出 - 6

  解释 –

• 要将A转换为F，我们需要5次增量。因此，我们可以执行1次3增量的操作和2次1增量的操作。我们需要总共3次操作。

• 要将B转换为G，我们需要5次增量。因此，我们需要执行3次操作。

• 我们需要总共6次操作。

方法

在这种方法中，我们将遍历字符串。之后，我们将找到字符之间的循环差异。通过将差异与K进行除法运算，我们可以得到增量为K的总数，通过对差异与K进行模运算，我们可以得到增量为1的总数。

步骤

• 将‘total’变量初始化为零，用于存储操作的次数。

• 使用循环遍历字符串。

• 如果第一个和第二个字符串在第i位上相同，则使用‘continue’关键字跳转到下一次迭代，因为我们不需要执行任何操作。

• 如果第一个字符串在第i位上的字符小于第二个字符串的字符，请按照以下步骤进行操作。

  • 如果second[i] – first[i]大于K，请将(second[i] – first[i]) / K添加到‘cnt’变量中，初始值为零。这给我们提供了通过增加K来执行的操作总数。

  • 将(second[i] – first[i]) % K添加到‘cnt’中，表示需要增加1的总数。

• 如果第一个字符串在第i位上的字符大于第二个字符串的字符，请按照以下步骤进行操作。

  • 获取差值(first[i] – second[i])，从26减去它，并将结果存储到‘temp’变量中。

  • 如果temp大于K，请将temp / K添加到‘cnt’变量中。

  • 将temp % K添加到‘cnt’变量中。

• 当一个循环迭代完成时，将‘cnt’值添加到‘total’中。

• 返回‘total’值。

示例

#include <bits/stdc++.h>
using namespace std;
// function to find the total minimum operations required to convert the string first to second with the given condition
int totalOperations(string first, string second, int K){
   // to store the count of operations
   int total = 0;
   // Traverse the string first
   for (int i = 0; i < first.length(); i++){
      // to store the total operations required to convert the current character of first to second
      int cnt = 0;
      // If the characters are the same, then continue
      if (first[i] == second[i])
          continue;
      // If the character of first is less than the character of second
      else if (first[i] < second[i]){
          // If the difference is greater than K
          if ((second[i] - first[i]) >= K){
              // Add the difference/K to cnt
              cnt = (second[i] - first[i]) / K;
          }
          // Add the difference%K to the cnt
          cnt += (second[i] - first[i]) % K;
      }
      // If the character of first is greater than the character of second
      else{
          int temp = 26 - (first[i] - second[i]);
          // Add the difference/K to cnt
          if (temp >= K)
              cnt = temp / K;
          // Add the difference%K to the cnt
          cnt += (temp % K);
      }
      total += cnt;
   }
   return total;
}
int main(){
   string first = "ACSQ", second = "BCOS";
   int K = 7;
   cout << "The total number of minimum operations require to convert the first string to second are " << totalOperations(first, second, K);
}

输出

The total number of minimum operations require to convert the first string to second are 7

时间复杂度 – O(N)，因为我们将第一个字符串的所有字符转换为第二个字符串。

空间复杂度 – O(1)，因为我们不使用任何固定的空间。

在这个问题中，我们通过执行循环递增操作将第一个字符串转换为第二个字符串。程序员可以尝试解决一个需要总共循环递减操作来将第一个字符串转换为第二个字符串的问题。