块变换(字符反转)
最后更新于：2022-04-01 21:40:31
### 问题描述
前面有两节提供了不同方法解决关于将一个具有n个元素的一维向量向左旋转i个位置。即：***[旋转交换](http://blog.csdn.net/utimes/article/details/8762497)***和***[J](http://blog.csdn.net/utimes/article/details/8759966)****[uggling算法](http://blog.csdn.net/utimes/article/details/8759966)*。本节，提出另一种方案，块变换解决此问题。
（来源于**《编程珠玑》第2版**的第2章第11页问题B）
请将一个具有n个元素的一维向量向左旋转i个位置。例如，假设n=8，i=3，那么向量abcdefgh旋转之后得到向量defghabc。简单编码使用一个具有n个元素的中间向量分n步即可完成此作业。你可以仅使用几十字节的微小内存，花费与n成比例的时间来旋转该向量吗？
### 解析
直观的想法：由于要对数组整体向左循环移动k位，那么我们就可以对数组中的每一个元素向左移动k位(超过数组长度的可以取模回到数组中)，此时总是能获得结果的。如原串 01234567结果：34567012。观察结果，直接的想法，我们能不能直接把待移动的串直接后面（0123456789 -- 7893456012）。此时，012是正确的位置了，但是其他元素还需调整。但是我们可以看到，把7893456变成3456789也需要向左循环移3位，这和第一步的变化是一样的，可以用递归做。
**原理：**将待旋转的向量x看成是由向量a和b组成的，那么旋转向量x实际上就是将向量ab的两个部分交换为向量ba
**步骤**：假设a比b短(谁长，谁分成两部分)
1)将b分割为bl和br两个部分，使得br的长度和a的长度一样
2)交换a和br，即ablbr转换成了brbla。通过本次变换，序列a就位于它的最终位置了。
3)我们需要集中精力交换b的两个部分了，这个时候就回到了最初的问题上了,我们可以递归地处理b部分。
举例：待旋转字符串"0123456789",向左移动3位
原串： 0123456789结果：3456789012
第一步： 把**b**分成**bl**和**br**两部分
**a b**
**012** 3456789 ->**012**3456789(3456是一部分，789是一部分）
第二步： 把**a**与**br**交换
**br bl a**
789 3456 012 (此时，012就是自己的最终的位置)
第三步： 之后可以递归处理 789 3456(**a**代表789,**b**代表3456)
----------------------------------------------------------
全部过程
待旋转序列：0123456789 结果：3456789012
红色表示已排好，绿色表示分的第一部分，黑色表示分的第二部分
第一步：7893456012
第二步：4563789012
第三步：3564789012
第四步：3465789012
第五步：3456789012
### 程序代码
~~~
#include
#include
using namespace std;
// 函数作用：把两块数据互换
// arr:待翻转的字符串,aStart：第一块内容的起始位置,bStart：第二块内容的起始位置,len：交换的长度
void swap(char* arr,int aStart,int bStart,int len){
assert(arr != NULL && aStart >= 0 && bStart >= 0 && len > 0);
char tmp;
while(len-- > 0){
tmp = arr[aStart];
arr[aStart] = arr[bStart];
arr[bStart] = tmp;
aStart++;
bStart++;
}
//cout< rightLen) {
swap(str,leftStart,leftStart+leftLen,rightLen);
Rotate(str,leftStart +rightLen,len-rightLen,len-2*rightLen);
}
else {
swap(str,leftStart,leftStart+len-leftLen,leftLen);
Rotate(str,leftStart,len-leftLen,leftLen);
}
}
void LeftRotateString(char* str,int k){
Rotate(str,0,strlen(str),k);
}
int main( ){
char str[60] = "abcdefghi";
LeftRotateString(str,3);
cout<
';