資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 字串左旋轉和右旋轉程式
旋轉意味著我們需要將每個字元向前或向後移動。在向前的情況下，最後一個字元被移動到索引 0，也稱為右旋轉。在向後的情況下，索引 0 的第一個字元被移動到最後一個索引，也稱為左旋轉。
在這個問題中，我們給定一個字元字串和一個整數 d。我們的任務是列印透過 d 整數左旋轉或右旋轉的字串。
只有當前字串的排列發生變化，給定字串中字元的長度或頻率不會改變。這裡 d 小於字串的大小。
讓我們看看示例：
輸入 1
str = "HelloWorld", d = 5
輸出 1
Left Rotation = "WorldHello" Right Rotation = "WorldHello"
解釋：這裡字串的左旋轉和右旋轉相同，因為字串中存在的字元總數為 10，並且我們左右旋轉了 5 個字元。
輸入 2
str = "abcdefgh", k = 3
輸出 2
Left Rotation = "defghabc" Right Rotation = "fghabcde"
解釋：這裡我們左右旋轉了 3 個字元。
方法
我們已經看到了上面給定字串和整數的示例，讓我們轉向方法
方法 1：反轉方法
這種方法的想法很簡單。使用反轉方法旋轉字串。對於左旋轉，首先反轉從索引 0 到 d 的起始 d 個字元，然後反轉剩餘的字元（從 d 個字元到字串的最後一個索引）。最後，反轉整個字串，得到左旋轉的字串。
對於右旋轉，只需要將字串和字串大小減去 d 傳遞給 forLeftRotation 函式即可將其向左旋轉字串大小減去 d。
示例
#include <bits/stdc++.h>
using namespace std;
// Rotates string 'str' by d to the left.
void forLeftRotation(string &str, int d){
reverse(str.begin(), str.begin()+d);
reverse(str.begin()+d, str.end());
reverse(str.begin(), str.end());
}
// Rotates string 'str' by d to the right.
void forRightRotation(string &str, int d){
int n = str.size();
int newD = n - d;
forLeftRotation(str, newD);
}
int main(){
string str = "HelloWorld!"; //given string
int d = 5; //given integer
string strL = str;
//Call the function to rotate the string toward the left
forLeftRotation(strL, d);
cout << "Left Rotation is "<< strL << endl;
string strR = str;
//Call the function to rotate the string toward the right
forRightRotation(strR, d);
cout << "Right Rotation is "<< strR << endl;
return 0;
}
輸出
Left Rotation is World!Hello Right Rotation is orld!HelloW
注意
正如我們在上一節中看到的，旋轉發生在字串長度重複後，可以透過獲取當前數字與給定字串長度的模來計算。在上面的程式中，我們給定了“d”或旋轉次數，它小於字串的大小，如果 d 大於字串的大小，則上面的程式碼將報錯。但為了安全起見，我們始終可以這樣做：
d = d % (str.size())
時間和空間複雜度
時間複雜度為 O(N)，其中 N 表示字串的大小。
空間複雜度為 O(1)，因為沒有使用額外的空間，只是將一個字串儲存到另一個字串中，該空間用於答案，因此沒有使用額外的空間。
方法 2：使用擴充套件字串
這個想法是，要旋轉一個字串，我們可以使用一個擴充套件字串，其長度是普通字串的兩倍。使用擴充套件字串從索引 (d) 到 (字串長度 + d) 進行左旋轉。對於右旋轉，將給定字串傳遞給 forLeftRotation 函式，以將字串向左旋轉字串大小減去 d。
示例
#include<bits/stdc++.h>
using namespace std;
// Rotates string 'str' by d to the left using extended string
string forLeftRotation(string str, int d){
string temp = str + str; // extended string
int idx = str.size(); //constructing a new rotated string's index
string leftFirst = temp.substr(d, idx);
return leftFirst;
}
// Rotates string 'str' by d to the right
string forRightRotation(string str, int d){
return forLeftRotation(str, str.size() - d);
}
int main(){
string str = "HelloWorld!"; //given input
int d = 5; //given integer
// Call the function to rotate the string toward the left
string strL = forLeftRotation(str, d);
cout << "Left Rotation is "<< strL << endl;
//Call the function to rotate the string toward the right
string strR = forRightRotation(str, d);
cout << "Right Rotation is "<< strR << endl;
return 0;
}
輸出
Left Rotation is World!Hello Right Rotation is orld!HelloW
注意
正如我們上面已經討論過的，在這個程式中，給定的“d”或旋轉次數小於字串的大小，如果 d 大於字串的大小，則上面的程式碼將報錯。但為了安全起見，我們始終可以這樣做
d = d % (str.size())
結論
在本教程中，我們實現了一個用於字串左旋轉和右旋轉的程式。我們實現了兩種方法。一種方法使用反轉方法，時間複雜度為 O(N)，空間複雜度為 O(1)。另一種方法使用擴充套件字串方法，時間複雜度為 O(N)，空間複雜度為 O(N)，其中 N 是給定字串的大小。
802 次瀏覽
