数据结构
网络
关系数据库管理系统 (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 的最大点数。
为了获得 (Sp−sp+1) 分，我们需要交换字符串 S 的 Sp 和 Sp+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
在这种方法中，我们将创建一个公式来获得问题的输出。
当我们交换 Sp 和 Sp+1 字符时，我们获得的点数等于 (Sp+1−sp)。
假设字符的初始位置是 p，交换后字符的位置是 q。
每当我们交换 Sp+1 和 Sp 时，成本会增加 (Sp+1−sp)。在这里，q 在每次交换中增加 1。
在这里，我们可以说，每当 q 增加 1 时，点数增加 Sp，每当 q 减小 1 时，点数减小 Sp。
因此，单个字符的最终成本是 Sp(q−p)。
这里，Sp∗q 等于 Tp∗p，因为我们使字符串 S 等于 T。
因此，单个字符的成本是 Tp∗p−Sp∗p，其中 'p' 是特定索引。
这是获得输出的最终公式。
Sum(Tp∗p−Sp∗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 次浏览
