PAT乙1008.数组元素循环移位

发表于 | 分类于

题目

一个数组A中存有N（N>0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A0 A1……AN-1）变换为（AN-M …… AN-1 A0 A1……AN-M-1）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

输入格式：每个输入包含一个测试用例，第1行输入N ( 1<=N<=100)、M（M>=0）；第2行输入N个整数，之间用空格分隔。

输出格式：在一行中输出循环右移M位以后的整数序列，之间用空格分隔，序列结尾不能有多余空格。

输入样例：
6 2
1 2 3 4 5 6
输出样例：
5 6 1 2 3 4

类似题解

https://github.com/julycoding/The-Art-Of-Programming-By-July/blob/master/ebook/zh/01.01.md
里面有一些举一反三的例子，非常适合看。

思考

这题题意很简单，然而我不会。（都不好意思的说，我第一个通过的算法是作弊了的，使用了两个数组…）

之后开始尝试暴力移位法，很明显是不符合要求的，这里就当练一下代码。另外，以后输入输出还是尽量用scanf和printf了，因为cin和cout比较耗时。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <iostream>
#include <cstdio>
using namespace std;
void RightShiftOne(int *a, int n){ //先移一个位置 
	int x = a[n-1];
	for(int i=n-1; i>0; i--){
		a[i] = a[i-1];
	}
	a[0] = x; 
}
int main(){
	int a[100];
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	m %= n; //这里就是减少循环的关键一步。
	while(m--){
		RightShiftOne(a, n);
	}
	for(int i=0; i<n; i++){
		printf("%d%s", a[i], (i-n+1?" ":"\n"));//写这条代码的人好厉害！这里我是抄的
	}
}

可能是PAT官网的oj不太好？上面的这个暴力做法也通过了。当然，也上网查了一下其他人的做法，就是我肯定想不出来的做法。看上面的那个github，似乎是一种叫做三步反转法的东东，这里就用它博客的例子来解释。

三步反转法

给定一个字符串，要求把字符串前面的若干个字符移动到字符串的尾部，如把字符串“abcdef”前面的2个字符’a’和’b’移动到字符串的尾部，使得原字符串变成字符串“cdefab”。请写一个函数完成此功能，要求对长度为n的字符串操作的时间复杂度为 O(n)，空间复杂度为 O(1)。

除了暴力移位法外，可以使用三步反转法。

将一个字符串分成X和Y两个部分，在每部分字符串上定义反转操作，如X^T，即把X的所有字符反转（如，X=”abc”，那么X’=”cba”），那么就得到下面的结论：(X’Y’)’=YX，显然就解决了字符串的反转问题。

例如，字符串abcdef，若要让def翻转到abc的前头，只要按照下述3个步骤操作即可：

  1. 首先将原字符串分为两个部分，即X:abc，Y:def；
  2. 将X反转，X->X’，即得：abc->cba；将Y反转，Y->Y’，得到：def->fed；
  3. 反转上述步骤得到的结果字符串X’Y’，即反转字符串cbafed的两部分给予反转，得到defabc，形式化表示为(X’Y’)’=YX，这就实现了整个反转。

代码可以这么写：

1
2
3
4
5
6
7
8
9
10
11
12
13
void ReverseString(char *s, int from, int to){
	while(from < to){
		char t = s[from];
		s[from++] = s[to];
		s[to--] = t;
	}
}
void LeftRotateString(char *s, int n, int m){
	m %= n;
	ReverseString(s, 0, m-1); //反转[0..m - 1]，套用到上面举的例子中，就是X->X^T，即 abc->cba
	ReverseString(s, m, n - 1); //反转[m..n - 1]，例如Y->Y^T，即 def->fed
	ReverseString(s, 0, n - 1); //反转[0..n - 1]，即如整个反转，(X^TY^T)^T=YX，即 cbafed->defabc
}

看手的解释！生动形象！
image.png

针对PAT的新解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <cstdio>
using namespace std;
void reverse(int *a, int from, int to){ //这个函数可以记住，就是用来反转的
	while(from < to){
		int t = a[from];
		a[from++] = a[to];
		a[to--] = t;
	}
}
int main(){
	int a[100];
	int n,m;
	scanf("%d%d", &n, &m);
	m %= n;
	for(int i=0; i<n; i++){
		scanf("%d", &a[i]);
	}
	reverse(a, 0, n-m-1);
	reverse(a, n-m, n-1);
	reverse(a, 0, n-1);
	for(int i = 0; i < n; i++)  
        printf("%d%s", a[i], (i-n+1?" ":"\n"));
}

最后提交上去，怎么时间比暴力还长呢…看来oj确实一般般~