数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学将字符串1中的字符转换为字符串2中存在的字符，方法是按字典顺序递增或递减。
在这个问题中，程序员需要通过执行增量或减量操作来使str1的所有字符等于str2的任何字符。此外，我们可以循环递增或递减。这意味着'z' + 1 == 'a'，而'a' – 1 == 'z'。
我们可以通过找到使str1字符串的字符等于str2字符串的任何字符的最小成本来解决这个问题。对于每个字符，我们可以找到所需的最小操作次数并将它们全部相加。
问题陈述 – 我们得到了两个名为str1和str2的字符串。str1的大小为N，str2的大小为M。此外，给定的条件是N <= M或N > M。这两个字符串仅包含小写字母字符。任务是，我们需要通过增量或减量操作使str1的所有字符等于str2的任何字符。我们需要找到使str1的所有字符等于str2的任何字符所需的最小操作次数。
示例
输入
str1 = "aedc", str2 = "db";
输出
3
解释
我们可以使'a'等于'b'，其代价是1。
我们可以使'e'等于'd'；其代价是1。
'd'已经存在于str2中，所以代价是0。
我们可以使'c'等于b或d；代价将是1。
因此，所需的总代价或所需的操作次数为3。
输入
str1 = "mwerd", str2 = "dermw";
输出
0
解释 – str1的所有字符都存在于str2中。因此，所需的操作次数等于零。
输入
str1 = "bdfhjlnp", str2 = "acegikmo";
输出
8
解释 – 我们可以通过将字符递增或递减1来使str1的每个字符等于str2的任何字符。例如，'b' -> 'a'，'d' -> 'c'或'd' -> 'e'等等。
方法1
我们将取str1字符串的任何字符，并通过执行增量或减量操作使其等于str2的每个字符。之后，我们将找到str1每个字符的最小成本并将它们全部相加。
让我们了解使一个字符等于另一个字符的两种方法。
将字符'a'转换为'e'。
通过递增，我们需要4次操作才能使'a'等于'e'。
通过递减操作，我们需要26 – 4 = 22次操作。
这里，4是最小值，所以我们将考虑它。
将字符'a'转换为'y'。
通过递增，我们需要24次操作。
通过递减，我们需要2次操作。
因此，所需的最小操作次数为4。
算法
步骤1 – 定义名为'str2Chars'的无序哈希映射来存储str2字符串中字符的频率。
步骤2 – 遍历字符串并在哈希映射中更新每个字符的频率。
步骤3 – 定义'count'变量来存储所需的最小操作次数。
步骤4 – 开始遍历字符串1。在循环中，用最大整数值初始化minMoves变量来存储使第p个字符等于str2的任何字符所需的最小操作次数。
步骤5 – 使用循环进行1到26次迭代。通过从str1[p]中减去'a'来获取0到25之间的字符值。
步骤6 – 如果当前字符存在于哈希映射中，则将零赋值给minMoves变量并中断循环。
步骤7 – 否则，如果'a' + q字符存在于哈希映射中，我们可以将p字符转换为'a' + q。
步骤8 – 通过递增操作获得使字符等于'a' + q的总操作次数，并将其存储到leftMin变量中。
步骤9 – 同样，找到通过递减操作使字符等于'a' + q的总操作次数，并将它们存储到rightMin变量中。
步骤10 – 从'leftMin'和'rightMin'中获取最小值。此外，从allMoves和minMoves中获取最小值。
步骤11 – 将minMoves添加到count变量的值中。
步骤12 – 返回'count'值。
示例
#include <bits/stdc++.h>
using namespace std;
int totalOps(string str1, string str2) {
// Map to store all characters of str2
unordered_map<char, int> str2Chars;
// Traverse str2
for (int p = 0; p < str2.size(); p++) {
str2Chars[str2[p]]++;
}
// Store minimum operations
int count = 0;
// Traverse str1
for (int p = 0; p < str1.size(); p++) {
// Total minimum move requires converting one character to another
int minMoves = INT_MAX;
// Calculate required moves
for (int q = 0; q < 26; q++) {
// Get the character value
int char_val = str1[p] - 'a';
// If str2 contains the str1[p]
if (str2Chars[str1[p]] > 0) {
minMoves = 0;
break;
} else if (str2Chars['a' + q] > 0) {
// Find minimum difference between str1[p] and str2[q]
int leftMin = abs(char_val - q);
int RightMin = min((26 - char_val) + q, char_val + (26 - q));
int allMoves = min(leftMin, RightMin);
minMoves = min(minMoves, allMoves);
}
}
// Update minimum operations
count += minMoves;
}
// Return total operations
return count;
}
int main() {
string str1 = "aedc";
string str2 = "db";
cout << "The minimum numbers of operations required to convert str1 to str2 is " << totalOps(str1, str2);
return 0;
}
输出
The minimum numbers of operations required to convert str1 to str2 is 3
时间复杂度 – O(N*26) ~ O(N)，因为我们遍历了字符串。
空间复杂度 – O(1)，因为我们没有使用常量空间。
类似地，程序员可以尝试解决我们需要使所有str2等于str1的问题。因此，我们需要从增量或减量操作中获取最小值，以将str1中第p个索引处的字符转换为str2中第p个索引处的字符。
65 次查看
