資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告