极客笔记C++ 在循环字符串中到达目标字符的最大移动次数
在这个问题中，我们将找到从初始字符到最终字符的最大距离。
解决这个问题的基本方法是找到每个初始字符的下一个最近的最终字符，并在需要时更新最大距离。
另一种方法是以倒序遍历字符串，并跟踪最后一个最终字符的索引。当我们得到一个初始字符时，我们测量距离并在需要时更新最大距离。
问题陈述 - 我们给出一个包含三个字符的循环字符串str，长度为N。同时，字符串是循环的。同时我们给出一个初始字符和最终字符。我们需要找到从初始字符到循环字符串中最近的最终字符的最大距离。
示例示例
输入
str = "pqqrr"; initial = 'r', final = 'p';
输出
2
解释
- 如果我们选择str[3]，离最近的结尾字符是str[0]。所以，距离是2个周期。
-
如果我们选择str[4]，离最近的结尾字符是str[0]。所以，距离是1个周期。
我们选择了最大的距离。
输入
str = "pqrpqqppr"; initial = 'p', final = 'r';
输出
5
说明
- 对于str[0]，距离最近的终止字符的距离是2。
-
对于str[3]，距离最近的‘r’的距离是5。
-
对于str[6]，距离最近的‘r’的距离是2。
-
对于str[7]，距离最近的‘r’的距离是1。
最大距离是5。
输入
str = "pqr"; initial = 'r', final = 'q';
输出结果
2
解释
离r最近的“q”的距离是循环的2。
方法1
在这个方法中，我们将找到每个初始字符和其最近的最终字符之间的距离，然后选择最大的距离作为输出。
算法
- 步骤1 - 将’maxDist’变量初始化为0，以存储最大距离。
-
步骤2 - 如果初始字符和最终字符相同，则返回0。
-
步骤3 - 开始遍历字符串。如果当前字符等于’initial’字符，则需要找到下一个最近的’final’字符。
-
步骤3.1 - 使用while循环，直到str[q％str_len]不等于’final’字符为止。这里，q％str_len帮助我们循环地找到最接近的最终字符。同时，在每次迭代中递增’q’的值。
-
步骤3.2 - 如果’maxDist’变量的值小于q-p，则更新’maxDist’。
-
步骤4 - 返回maxDist的值。
例子
#include <bits/stdc++.h>
using namespace std;
int maximumDistance(string str, char initial, char final) {
// String length
int str_len = str.size();
int maxDist = 0;
// Base case
if (initial == final) {
return 0;
}
// Find maximum distance
for (int p = 0; p < str_len; p++) {
if (str[p] == initial) {
// Finding the next final character in the cyclic string
int q = p + 1;
while (str[q % str_len] != final) {
q++;
}
// Take the maximum distance
maxDist = max(maxDist, q - p);
}
}
// Final output
return maxDist;
}
int main() {
string str = "pqqrr";
char initial = 'r', final = 'p';
cout << "The maximum distance between the initial and final character is " << maximumDistance(str, initial, final);
return 0;
}
输出
The maximum distance between the initial and final character is 2
时间复杂度 – O(N^2)，因为我们在遍历字符串时找到下一个最接近的终止字符。
空间复杂度 – O(1)，因为我们不使用动态空间。
方法2
在这个方法中，我们将字符串连接到自身。然后，我们将从最后开始遍历字符串，并跟踪最后一个终止字符的索引。当我们在字符串中找到“初始”字符时，我们通过索引差来计算距离，并在当前距离大于最大距离时更新最大距离。
算法
- 步骤1 - 将字符串“str”连接到自身。
-
步骤2 - 将“maxDist”初始化为0，将“f_index”初始化为-1以存储最后一个终止字符的索引。
-
步骤3 - 如果初始字符和最终字符相同，则返回0。
-
步骤4 - 从反向遍历str字符串。
-
步骤5 - 如果当前字符等于初始字符并且f_index不等于-1，则使用max(Dmax, f_index-p)值来更新maxDist。
-
步骤6 - 否则，将“p”值分配给“f_index”。
-
步骤7 - 最后，返回“maxDist”变量的值。
例子
#include <bits/stdc++.h>
using namespace std;
int maximumDistance(string str, char initial, char final) {
// String length
int str_len = str.size();
// To find the next occurrence of a final character in the cyclic string
str += str;
int maxDist = 0, f_index = -1;
// Base case
if (initial == final) {
return 0;
}
// Traverse the string
for (int p = 2 * str_len - 1; p >= 0; p--) {
// If the current character is an initial character, update the distance
if (str[p] == initial && f_index != -1) {
maxDist = max(maxDist, f_index - p);
}
// Update the index of the final character
if (str[p] == final) {
f_index = p;
}
}
// Final output
return maxDist;
}
int main() {
string str = "pqqrr";
char initial = 'r', final = 'p';
cout << "The maximum distance between the initial and final character is " << maximumDistance(str, initial, final);
return 0;
}
输出
The maximum distance between the initial and final character is 2
时间复杂度 – O(N) 用于遍历字符串。
空间复杂度 – O(N) 因为我们将字符串附加到自身。
第一个解决方案遍历字符串并找到下一个最近的每当初始字符出现在任何索引处，但第二个解决方案始终跟踪最近的最终字符，改善了问题的时间复杂度。