极客笔记C++ 最大点数通过交换相邻字符将字符串S转换为T
在这个问题中，我们将根据问题陈述中的条件找到将字符串S转换为T时的最大点数。
我们可以遍历字符串S，并通过最大交换使字符串S的每个字符与字符串T的相同索引处的字符相同，从而获得最大点数。
在另一种方法中，我们将根据字符串的观察准备一个数学公式来得出答案。
问题陈述 - 我们给出了一个包含字母和数字字符的字符串S和T。我们需要计算在将字符串S转换为T时的最大点数。
要获得（\mathrm{S_{p}-s_{p}+1}）点，我们需要交换字符串S的\mathrm{S_{p}}和\mathrm{S_{p}+1}元素。
示例例子
输入
S = "543"; T = "345";
输出结果
4
解释
- 首先，交换(4, 3)，得到1分，字符串将变成534。
-
接下来，交换(5, 3)，得到2分，字符串将变成354。
-
最后一步，交换(5, 4)，得到1分，字符串将与T相同。
输入
S = "1234"; T = "1234";
输出
0
解释 – 两个字符串已经相同，所以得到0分。
输入
S = "179"; T = "125";
输出
-1
说明 – 无论如何，我们都不能通过交换字符将字符串S转换为T。因此，它打印-1。
方法 1
在这个方法中，如果两个字符串的第pth个索引处的字符不匹配，则找到字符串S中匹配的字符的下一个索引。然后，我们将匹配的字符与字符串字符交换以将其放置在第pth个索引处，并累加获得的分数。通过这种方式，我们替换字符串S的每个不匹配字符并计算它们的分数总和。
算法
步骤 1 - 将’pnt’初始化为0，以存储最大分数。
步骤 2 - 开始遍历字符串。
步骤 3 - 如果字符串S和T中第pth个索引处的字符相同，则进入下一次迭代。
步骤 4 - 否则，在字符串S中找到T[p]的下一个索引。如果找不到字符，则返回-1，因为我们无法将字符串S转换为T。
步骤 5 - 使用while循环进行迭代，直到q > p，交换字符串字符。
步骤 6 - 将S[q – 1] – S[q]添加到’pnt’值中，这是为S[q – 1]和S[q]字符的交换获得的分数。
步骤 7 - 使用swap()方法交换S[q – 1]和S[q]字符。同时，将q的值减1。
步骤 8 - 返回’pnt’值。
示例
#include <iostream>
using namespace std;
int getMaximumPoint(string S, string T, int str_len) {
int pnt = 0;
for (int p = 0; p < str_len; p++) {
// When characters are the same at the same index
if (S[p] == T[p]) {
continue;
}
int q = p + 1;
// Finding the index of the next matching character
while (q < str_len && S[q] != T[p]){
q++;
}
// If no matching character is found
if (q == str_len){
return -1;
}
// Swap characters and get points
while (q > p) {
pnt += S[q - 1] - S[q];
swap(S[q], S[q - 1]);
q--;
}
}
// Return total points
return pnt;
}
int main() {
string S = "543";
string T = "345";
int str_len = S.length();
cout << "The maximum pnt we can get while converting string S to T is "
<<getMaximumPoint(S, T, str_len) << endl;
return 0;
}
输出
The maximum pnt we can get while converting string S to T is 4
时间复杂度 – O(N*N) 用于遍历字符串并找到下一个匹配字符的索引。
空间复杂度 – O(1)，因为我们不使用任何额外的空间。
方法2
在这种方法中，我们将创建一个公式来获得问题的输出。
当我们交换\mathrm{S_{p}}和\mathrm{S_{p}+1}字符时，我们得到的分数等于(\mathrm{S_{p}+1-s_{p}})。
假设字符的初始位置是p，在交换后，字符的位置是q。
每当我们交换\mathrm{S_{p} + 1}和\mathrm{S_{p}}时，成本增加了(\mathrm{S_{p}+1-s_{p}})。这里，在每次交换中，q增加1。
在这里，我们可以说每当q增加1时，分数增加Sp，而每当q减小1时，分数减小\mathrm{S_{p}}。
所以，对于一个单独的字符，最终成本是\mathrm{S_{p}(q – p)}。
在这里，\mathrm{S_{p} * q}等于\mathrm{T_{p} * p}，因为我们使字符串S等于T。
所以，单个字符的成本是\mathrm{T_{p} * p – S_{p} * p}，其中’p’是特定索引。
以下是获得输出的最终公式。
Sum(\mathrm{T_{p} * p – S_{p} * p})，其中1 <= p <= 字符串长度。
算法
步骤1 - 开始遍历字符串。
步骤2 - 将字符值与其在T和S字符串中的索引相乘，并从T值中减去S值。然后将结果值添加到’pnt’变量中。
步骤3 - 返回’pnt’值。
示例
#include <iostream>
using namespace std;
long getMaximumPoint(string S, string T, int str_len) {
// To store the sum of the multiplication of each digit and its index
int pnt = 0;
for (int p = 0; p < str_len; p++) {
pnt += (T[p] - '0') * 1l * (p + 1) - (S[p] - '0') * 1l * (p + 1);
}
return pnt;
}
int main() {
string S = "543";
string T = "345";
int str_len = S.length();
cout << "The maximum pnt we can get while converting string S to T is "
<< getMaximumPoint(S, T, str_len) << endl;
return 0;
}
输出
The maximum pnt we can get while converting string S to T is 4
时间复杂度 – O(N) ，遍历字符串。
空间复杂度 – O(1) ，因为我们没有使用任何动态空间。
在第二种方法中，我们根据观察结果创建了一个公式来解决问题。它也适用于包含多次出现相同字符的字符串，因为对于元素的任何出现，我们都会交换另一个元素，成本保持不变。