轮转数组问题：如何实现数组“整体逆序，内部有序”？“三步转换法”妙转数组（一）+ https://developer.aliyun.com/article/1518463?spm=a2c6h.13148508.setting.14.73ba4f0eD6sgs2
三、拓展：倒置字符串
这道题是上面三步转换法非常合适的一个变式。
1. 题干
牛客网链接
https://www.nowcoder.com/questionTerminal/8869d99cf1264e60a6d9eff4295e5bab
将一句话的单词进行倒置，标点不倒置。
比如 "I like beijing."，经过处理后变为："beijing. like I"
（字符串长度不超过100）
2. 思路
这也是“整体逆序，内部有序”的典例：我们将字符串内容按单词分块，单词在整个句子中的顺序发生变化，但单词还是单词，它内部的字母顺序并没有发生变化。
当我们明白这一点，接下来的事情也许会好办许多。
3. 代码
这里我们采用指针+while循环的方式来对字符串数组进行操作。这里是单纯的倒置，不存在向左或向右轮转的方向问题，因此方向这里就不用考虑了。
此外还有一些细节方面需要注意，如scanf读不了空格，当字符串中需要空格的时候，最好用gets()函数读取
//将逆置操作封装成函数 void reverse(char* left, char* right) { //加了两句断言 assert(left); assert(right); while (left < right) { char tmp = *left; *left = *right; *right = tmp; left++; right--; } } int main() { char arr[101] = { 0 }; //注意要用gets()函数，因为它可以读入空格 gets(arr); //用指针来操作数组 char* cur = arr; //逆序每个单词 while (*cur) { char* start = cur; char* end = cur; while (*end != ' ' && *end != '\0') { end++; } reverse(start, end - 1); if (*end != '\0') cur = end + 1; else cur = end; } //逆序整个字符串 int len = strlen(arr); reverse(arr, arr + len - 1); printf("%s\n", arr); return 0; }
四、总结
- 三步逆置：将数组分块，块内元素先分别逆置，最后再整体逆置。若无轮转顺序要求，则不需要考虑先逆置数组中的哪一块内的元素。
- 本文详细介绍了三步逆置法在倒置字符串和整型数组中的应用，以及两种代码实现。在倒置字符串时我们不需要考虑轮转顺序，只要达到逆置的结果即可，该代码是用指针+区间划分的思想实现的，我们用了while循环来控制。
- 在轮转数组的引例中，题目要求的向右轮转，我们就先将右边的k个元素逆置，再将剩下的左边（n-k）个元素逆置，最后整体逆置。虽然本文似乎有强调轮转方向的差别，但其实在数组整体逆置之前，先逆置内部哪部分是并不影响结果的，只要保证每个部分的内部都逆置过了即可。先逆置左边的（n-k）个，再逆置右边的k个，最后再整体逆置，达到的效果是一样的。强调方向仅仅是便于一些同学理解。
