数据结构
网络
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 次浏览
