将一个字符串转换为另一个给定字符串所需的最小增量为 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 个循环增量。我们可以执行 7 个增量的 (k = 3) 个操作和 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 个增量。因此，我们可以执行 3 个增量的 1 个操作和 1 个增量的 2 个操作。我们需要总共 3 个操作。

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

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

方法 1

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

算法

  • 将“total”变量初始化为零以存储操作数。

  • 使用循环遍历字符串。

  • 如果 first 和 second 字符串在第 i 个索引处具有相同的字符，则使用“continue”关键字移动到下一个迭代，因为我们不需要执行任何操作。

  • 如果 first 字符串的字符小于 second 字符串在第 i 个索引处的字符，请执行以下步骤。

    • 如果 second[i] - first[i] 大于 K，则将 (second[i] - first[i]) / K 添加到最初为零的“cnt”变量。它为我们提供了我们可以通过将字符增加 K 来执行的操作总数。

    • 将 (second[i] - first[i]) % K 添加到“cnt”，表示 1 所需的总增量数。

  • 如果 first 字符串的字符大于 second 字符串在第 i 个索引处的字符，请执行以下步骤。

    • 获取差异 (first[i] - second[i])，从中减去 26，并将结果存储到“temp”变量中。

    • 如果 temp 大于 K，则将 temp / K 添加到“cnt”变量中。

    • 将 temp % K 添加到“cnt”变量中。

  • 当一个循环迭代完成后，将“cnt”值添加到“total”。

  • 返回“total”值。

示例

Open Compiler
#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)，因为我们将 first 字符串的所有字符转换为 second 字符串。

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

在这个问题中，我们通过执行循环增量操作将 first 字符串转换为 second 字符串。程序员可以尝试解决需要执行循环减量操作总数才能将 first 字符串转换为 second 字符串的问题。

更新于: 2023年8月18日

365 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始
广告