青岛网站建设找,二维码生成器怎么弄,建设银行网站登不上,取消教育网站前置审批文章目录 55. 右旋字符串题目描述暴力优化#xff1a;不能申请额外空间#xff0c;只能在本串上操作思路代码 55. 右旋字符串
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k#xff0c;请编写一个函数… 文章目录 55. 右旋字符串题目描述暴力优化不能申请额外空间只能在本串上操作思路代码 55. 右旋字符串
题目描述
字符串的右旋转操作是把字符串尾部的若干个字符转移到字符串的前面。给定一个字符串 s 和一个正整数 k请编写一个函数将字符串中的后面 k 个字符移到字符串的前面实现字符串的右旋转操作。
例如对于输入字符串 “abcdefg” 和整数 2函数应该将其转换为 “fgabcde”。
输入描述 输入共包含两行第一行为一个正整数 k代表右旋转的位数。第二行为字符串 s代表需要旋转的字符串。 输出描述 输出共一行为进行了右旋转操作后的字符串。 输入示例
2
abcdefg输出示例
fgabcde提示信息 数据范围 1 k 10000, 1 s.length 10000; 暴力
程序首先通过 cin 读取用户输入的旋转位数 n 和字符串 s。然后它通过两个循环构造右旋转后的字符串 a 第一个循环从字符串 s 中取出最后 n 个字符这是因为右旋转操作的定义是将字符串尾部的若干字符移到字符串的前面。 第二个循环取出字符串 s 开头到指定位置 s.size() - n 的字符即除去被旋转到前面的那部分字符。
最后程序输出构造好的字符串 a 并结束。
// 包含C的全局库包含了大部分常用的C库。
#includebits/stdc.h
using namespace std;int main()
{int n; // 定义一个整数n用来存储用户输入的旋转位数。string s, a; // 定义两个字符串s用来接收用户输入的原始字符串a用来存储旋转后的字符串。cin n s; // 从标准输入读取旋转位数和需要旋转的字符串。// 遍历并添加字符串s尾部的n个字符到字符串a。for(int i s.size() - n; i s.size(); i)a s[i];// 遍历并添加字符串s除去尾部n个字符的剩余部分到字符串a。for(int i 0; i s.size() - n; i)a s[i];// 输出旋转后的字符串a。cout a endl;// 程序正常结束返回0。return 0;
}
优化不能申请额外空间只能在本串上操作
思路
不能使用额外空间的话模拟在本串操作要实现右旋转字符串的功能还是有点困难的。
那么我们可以想一下上一题目 151. 反转字符串中的单词 中讲过使用整体反转局部反转就可以实现反转单词顺序的目的。
本题中我们需要将字符串右移n位字符串相当于分成了两个部分如果n为2符串相当于分成了两个部分如图 length为字符串长度 右移n位 就是将第二段放在前面第一段放在后面先不考虑里面字符的顺序是不是整体倒叙不就行了。如图 此时第一段和第二段的顺序是我们想要的但里面的字符位置被我们倒叙那么此时我们在把 第一段和第二段里面的字符再倒叙一把这样字符顺序不就正确了。 如果 其实思路就是 通过 整体倒叙把两段子串顺序颠倒两个段子串里的的字符在倒叙一把负负得正这样就不影响子串里面字符的顺序了。
代码
这个程序利用了反转操作reverse 函数的性质来实现字符串的右旋转。这种方法的核心在于 反转整个字符串将整个字符串 s 反转后原来在尾部的k个字符现在会移到字符串的前面。 反转字符串的前 n 个字符这将刚才移到前面的 n 个字符再次反转回它们原来的顺序。 反转字符串的剩余部分将前 n 个字符之后的部分再次反转这样这部分字符也回到了它们原来的顺序。
通过上述步骤字符串的后 n 个字符被移动到了字符串的前面实现了字符串的右旋转操作。
// 包含了大部分常用的C库简化了头文件的包含过程。
#includebits/stdc.h
using namespace std;int main()
{int n; // 定义一个整数n用来存储用户输入的旋转位数。string s; // 定义一个字符串s用来接收用户输入的原始字符串。cin n s; // 从标准输入读取旋转位数和需要旋转的字符串。// 第一步反转整个字符串。reverse(s.begin(), s.end());// 第二步反转字符串的前n个字符现在这部分字符位于字符串的开头。reverse(s.begin(), s.begin() n);// 第三步反转字符串的剩余部分即从第n个字符到字符串的末尾。reverse(s.begin() n, s.end());// 输出旋转后的字符串。cout s endl;// 程序正常结束返回0。return 0;
}
