算法思想之三步翻转法

常见题目类型：

先看两道相同类型题目。

这两道题的相同之处在于都是变化字符串的顺序，但其中某些部分按原来位置不变。

解题思路：

按照旋转数组进行解答。

首先将后k个逆置，再将前n-k个逆置，最后整体逆置。即可得到答案。三步逆置也就体现了算法的核心思维，也就是三步翻转法。

注意三步翻转法，无论是先整体逆置还是后整体逆置，效果是一样的，都翻转了两次

算法实现：

上述需要创建一个逆置函数，便于调用。只需要给出逆置的范围，左下标和右下标。

注意左下标和右下标的值，容易出错。

逆置函数的实现，在于左右下标的互换。

//旋转数组
void reverse(int *arr,int left,int right)
{
while (left <= right)
  {
int tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
  }
}


int main()
{
int arr[10] = { 1,2,3,4,5,6,7,8,9,10 };
int k = 0;
scanf("%d", &k);
reverse(arr,10-k,9);
reverse(arr,0,10-k-1 );
reverse(arr,0,9 );//三步翻转
for (int i=0;i<10;i++)
  {
printf("%d ", arr[i]);
  }
return 0；
}

#include<string.h>
//倒置单词
void reverse(char* arr,int left,int right)
{
while (left <= right)
  {
char tmp = arr[left];
arr[left] = arr[right];
arr[right] = tmp;
left++;
right--;
  }
}

int main()
{
char arr[100] = { 0 };//时刻要注意初始化
gets(arr);
int len = strlen(arr);//C语言计算字符串的长度用strlen函数
//printf("%d", len);
int left = 0;
int right = left;
reverse(arr, 0, len - 1);

while (arr[right]!='\0')
  {
while (arr[right] == ' ')
    {
reverse(arr, left, right-1);
left = right + 1;
right = left;
    }
right++;
  }
reverse(arr, left, len - 1);
for (int i=0;i<len;i++)
  {
printf("%c", arr[i]);
  }
return 0;
}