数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究通过交换相邻字符将字符串 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
在这种方法中，如果两个字符串在第 p 个索引处的字符不匹配，我们找到字符串 S 中匹配字符的下一个索引。之后，我们将匹配字符与字符串字符交换，将其放在第 p 个索引处，并对获得的点数求和。通过这种方式，我们替换字符串 S 的每个不匹配字符，并对其点数求和。
算法
步骤 1 - 将 'pnt' 初始化为 0 以存储最大点数。
步骤 2 - 开始遍历字符串。
步骤 3 - 如果字符串 S 和 T 中第 p 个索引处的字符相同，则转到下一个迭代。
步骤 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 字符串中的索引相乘，然后从 S 中减去 T 值。之后，将结果值添加到 '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)，因为我们没有使用任何动态空间。
在第二种方法中，我们根据观察结果创建了公式来解决问题。它也适用于包含多个相同字符的字符串，因为无论元素出现多少次，我们交换另一个元素，成本都保持不变。
91 次浏览
