数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学循环字符串中到达目标字符的最大移动步数
在这个问题中，我们将找到循环字符串中从起始字符到目标字符的最大距离。
解决这个问题的基本方法是为每个起始字符找到下一个最近的目标字符，并在需要时更新最大距离。
另一种方法是反向遍历字符串，并跟踪最后一个目标字符的索引。当我们得到一个起始字符时，我们测量距离，并在需要时更新最大距离。
问题陈述 − 我们给定一个包含3个字符的字符串 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
解释
最近的 ‘q’ 到 r 的循环距离是 2。
方法 1
在这种方法中，我们将找到每个起始字符与其最近目标字符之间的距离。我们将选择最大距离作为输出。
算法
步骤 1 − 用 0 初始化 ‘maxDist’ 变量以存储最大距离。
步骤 2 − 如果起始字符和目标字符相同，则返回 0。
步骤 3 − 开始遍历字符串。如果当前字符等于 ‘起始’ 字符，我们需要找到下一个最近的 ‘目标’ 字符。
步骤 3.1 − 使用 while 循环直到 str[q % str_len] 不等于 ‘目标’ 字符。这里，q % str_len 帮助我们循环找到最近的目标字符。并且在每次迭代中递增 ‘q’ 的值。
步骤 3.2 − 如果 ‘maxDist’ 变量的值小于 q – p，则更新 ‘maxDist’。
步骤 4 − 返回 maxDist 值。
示例
以下是上述方法的程序 −
#include <stdio.h>
#include <string.h>
// Function to calculate maximum distance between initial and final characters
int maximumDistance(char str[], char initial, char final) {
int str_len = strlen(str);
int maxDist = 0;
// Base case: If initial and final characters are the same, return 0
if (initial == final) {
return 0;
}
// Iterate through the string to find the maximum distance
for (int p = 0; p < str_len; p++) {
if (str[p] == initial) {
int q = p + 1;
// Use a while loop to find the next occurrence of the final character
while (str[q % str_len] != final) {
q++;
}
// Update maxDist with the maximum distance found
maxDist = (q - p) > maxDist ? (q - p) : maxDist;
}
}
return maxDist;
}
int main() {
char str[] = "pqqrr";
char initial = 'r', final = 'p';
// Call the function and print the result
printf("The maximum distance between the initial and final character is %d\n", maximumDistance(str, initial, final));
return 0;
}
输出
The maximum distance between the initial and final character is 2
#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
public class Main {
public static int maximumDistance(String str, char initial, char finalChar) {
int strLen = str.length();
int maxDist = 0;
// Base case: If initial and final characters are the same, return 0
if (initial == finalChar) {
return 0;
}
// Iterate through the string to find the maximum distance
for (int p = 0; p < strLen; p++) {
if (str.charAt(p) == initial) {
int q = p + 1;
// Use a while loop to find the next occurrence of the final character
while (str.charAt(q % strLen) != finalChar) {
q++;
}
// Update maxDist with the maximum distance found
maxDist = Math.max(maxDist, q - p);
}
}
return maxDist;
}
public static void main(String[] args) {
String str = "pqqrr";
char initial = 'r';
char finalChar = 'p';
// Call the function and print the result
System.out.println("The maximum distance between the initial and final character is " + maximumDistance(str, initial, finalChar));
}
}
输出
The maximum distance between the initial and final character is 2
def maximum_distance(string, initial, final, initistr_len=None):
max_dist = 0
# Base case: If initial and final characters are the same, return 0
if initial == final:
return 0
# Calculate the length of the string
str_len = len(string)
# Iterate through the string to find the maximum distance
for p in range(str_len):
if string[p] == initial:
q = p + 1
# Use a while loop to find the next occurrence of the final character
while string[q % str_len] != final:
q += 1
# Update max_dist with the maximum distance found
max_dist = max(max_dist, q - p)
return max_dist
string = "pqqrr"
initial = 'r'
final = 'p'
# Call the function and print the result
print("The maximum distance between the initial and final character is", maximum_distance(string, initial, final))
输出
The maximum distance between the initial and final character is 2
时间复杂度 – O(N8N)，因为我们在遍历字符串时找到下一个最近的目标字符。
空间复杂度 – O(1)，因为我们没有使用任何动态空间。
方法 2
在这种方法中，我们将字符串与其自身连接起来。之后，我们将从最后开始遍历它，并跟踪最后一个目标字符的索引。当我们在字符串中找到 ‘起始’ 字符时，我们取索引差来获得距离，如果当前距离大于最大距离，则更新最大距离。
算法
步骤 1 − 将 ‘str’ 字符串与其自身连接起来。
步骤 2 − 用 0 初始化 ‘maxDist’ 和 -1 初始化 ‘f_index’ 以存储最后一个目标字符的索引。
步骤 3 − 如果起始字符和目标字符相同，则返回 0。
步骤 4 − 反向遍历 str 字符串。
步骤 5 − 如果当前字符等于起始字符，并且 f_index 不等于 -1，则用 max(maxDist, f_index - p) 值更新 maxDist。
步骤 6 − 否则，将 ‘p’ 值赋给 ‘f_index’。
步骤 7 − 最后，返回 ‘maxDist’ 变量的值。
示例
以下是上述方法的程序 −
#include <stdio.h>
#include <string.h>
// Function to calculate maximum distance between initial and final characters
int maximumDistance(char str[], char initial, char final) {
// String length
int str_len = strlen(str);
// Allocate space for the concatenated string (twice the length of the input string)
char combinedStr[2 * str_len + 1]; // +1 for the null terminator
// Copy the string to itself
strcpy(combinedStr, str);
strcat(combinedStr, str);
int maxDist = 0, f_index = -1;
// Base case: If initial and final characters are the same, return 0
if (initial == final) {
return 0;
}
// Traverse the concatenated string
for (int p = 2 * str_len - 1; p >= 0; p--) {
// If the current character is an initial character, update the distance
if (combinedStr[p] == initial && f_index != -1) {
maxDist = (f_index - p) > maxDist ? (f_index - p) : maxDist;
}
// Update the index of the final character
if (combinedStr[p] == final) {
f_index = p;
}
}
// Final output
return maxDist;
}
int main() {
char str[] = "pqqrr";
char initial = 'r', final = 'p';
printf("The maximum distance between the initial and final character is %d\n", maximumDistance(str, initial, final));
return 0;
}
输出
The maximum distance between the initial and final character is 2
#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
public class Main {
public static int maximumDistance(String str, char initial, char finalChar) {
// String length
int strLen = str.length();
// To find the next occurrence of a final character in the cyclic string
str += str; // Concatenate the string to itself
int maxDist = 0;
int fIndex = -1;
// Base case: If initial and final characters are the same, return 0
if (initial == finalChar) {
return 0;
}
// Traverse the string in reverse order
for (int p = 2 * strLen - 1; p >= 0; p--) {
// If the current character is an initial character, update the distance
if (str.charAt(p) == initial && fIndex != -1) {
maxDist = Math.max(fIndex - p, maxDist);
}
// Update the index of the final character
if (str.charAt(p) == finalChar) {
fIndex = p;
}
}
// Final output
return maxDist;
}
public static void main(String[] args) {
String str = "pqqrr";
char initial = 'r';
char finalChar = 'p';
System.out.println("The maximum distance between the initial and final character is " + maximumDistance(str, initial, finalChar));
}
}
输出
The maximum distance between the initial and final character is 2
def maximum_distance(string, initial, final):
# String length
str_len = len(string)
# To find the next occurrence of a final character in the cyclic string
string += string # Concatenate the string to itself
max_dist = 0
f_index = -1
# Base case: If initial and final characters are the same, return 0
if initial == final:
return 0
# Traverse the string in reverse order
for p in range(2 * str_len - 1, -1, -1):
# If the current character is an initial character, update the distance
if string[p] == initial and f_index != -1:
max_dist = max(f_index - p, max_dist)
# Update the index of the final character
if string[p] == final:
f_index = p
# Final output
return max_dist
string = "pqqrr"
initial = 'r'
final = 'p'
print("The maximum distance between the initial and final character is", maximum_distance(string, initial, final))
输出
The maximum distance between the initial and final character is 2
时间复杂度 – O(N)，用于遍历字符串。
空间复杂度 – O(N)，因为我们将字符串追加到自身。
第一个解决方案遍历字符串并在每次出现起始字符时找到下一个最近的字符，但第二个解决方案始终跟踪最近的目标字符，从而提高了问题的效率。
更新于: 2023年10月23日
96 次浏览
广告