作者:鸣丸子圓的睿哥 | 来源:互联网 | 2023-05-18 15:25
题目:把一个含有N个元素的字符串右移K位,要求时间复杂度为O(N),且只允许使用两个附加变量。例子:字符串为:abcd1234,右移4位,结果变为:1234abcd
题目:把一个含有N个元素的字符串右移K位,要求时间复杂度为O(N),且只允许使用两个附加变量。
例子:
字符串为:abcd1234,右移4位,结果变为:1234abcd
思路:
移动前跟移动后是有两段的顺序是不变的,所以可以把这两段看成两个整体
右移K位的过程就是把数组的两部分交换一下。
交换的过程:(1)逆序排列第一部分
(2)逆序排列第二部分
(3)再全部逆序!
代码:
#include
using namespace std;
const int MAXN = 10000;
int Array[MAXN], n, k;
void Reverse(int *A, int b, int e) {
for(; b > n >> k;
for(int i = 0; i > Array[i];
RightShift(Array, n, k);
for(int i = 0; i
2.17 数组循环移位