面试算法题之旋转置换，旋转跳跃我闭着眼
轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
借用临时数组
我们可以新建一个临时数组，用于存储旋转后的元素。首先获取数组的长度n，并计算k%n将k值限制在数组nums长度范围内，避免不必要的旋转。创建一个临时数组ans，在第一个循环中，从位置n-k开始，将nums向量中的元素逐个添加到ans向量中。在第二个循环中，从位置 0 开始，将 nums 向量中的元素逐个添加到 ans 向量中。执行完两个循环后就得到了旋转后的数组，但题意需要通过参数nums传递结果，所以通过最后一个循环将数组ans中的元素逐个复制回数组nums中。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
vector<int> ans;
for(int i=n-k;i<n;i++) {
ans.push_back(nums[i]);
}
for(int i=0;i<n-k;i++) {
ans.push_back(nums[i]);
}
for(int i=0;i<n;i++) {
nums[i] = ans[i];
}
}
};时间复杂度为 O(n)，空间复杂度为 O(n)。
多次翻转数组
实际上我们将数组旋转后，最终结果是将末尾kkk位数移动至数组开头，部分数组元素排序并没有改变。那么如何可以快速将末尾元素调换至数组开头呢？
如nums = [1,2,3,4,5,6,7,8], k = 2, n = 8，数组旋转后得到[7,8,1,2,3,4,5,6]。
我们先将整个数组翻转，得到[8,7,6,5,4,3,2,1]，这样末尾元素就移动到了数组开头，但元素顺序改变了。这时，我们将数组前kkk位分为一组，其余元素为另一组。分别对这两组执行一次数组翻转，这样元素顺序也就调转回来了，得到结果[7,8,1,2,3,4,5,6]。
class Solution {
public:
void reverse(vector<int>& nums, int s, int e) {
while(s < e) {
swap(nums[s++], nums[e--]);
}
}
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums, 0, n-1);
reverse(nums, 0, k-1);
reverse(nums, k, n-1);
}
};时间复杂度为 O(n)，空间复杂度为 O(1)。
分组循环
在上述使用临时数组方案中，临时数组是为了避免替换位置的元素被覆盖。当然，我们也可以使用一个临时变量去记录。
我们假设将数组分为cnt组，每个组的大小为n/cnt。这里分组数cnt计算如下：
如nums = [1,2,3,4,5,6,7,8], k = 2, n = 8，如此计算k和n的最大公约数为 2 ，我们可以将数组分成 2 组，[1,3,5,7]和[2,4,6,8]，变换过程如下图。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
int cnt = gcd(n,k);
for(int i=0; i<cnt; i++) {
int curr = i;
int tmp = nums[i];
do {
int j = (curr + k) % n;
swap(nums[j], tmp);
curr = j;
}while(i != curr) ;
}
}
};时间复杂度为 O(n)，空间复杂度为 O(1)。
旋转链表
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
合并成循环链表
旋转链表与旋转数组不同，不经历一次遍历无法确定链表的长度nnn。另一个不同点在于移动一个链表元素不需要整体元素移动。
利用这点特性，我们可以先将链表合并成环，并在链表的n−(kmod n)n-(k \mod n)n−(kmodn)处断开，如此就可以得到旋转后的链表。具体如何操作呢？
我们先定义一个迭代指针p，用于遍历链表记录链表长度nnn，此时p指针正指向链表尾部元素，并将链表头尾连接。
知道链表长度nnn后，由此就可以得到需要再向前移动p指针的步数cnt=n−(kmod n)cnt = n-(k \mod n)cnt=n−(kmodn)，再移动p指针cntcntcnt步，此时p指针正指向旋转后链表的尾部元素，定义ans记录新链表的头部元素，再断开链表就完成链表的旋转啦。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if(k==0 || head==nullptr || head->next==nullptr)
return head;
int n = 1;
ListNode* p = head;
while(p->next != nullptr) {
p = p->next;
n++;
}
p->next = head;
// 需要移动的步数
int cnt = n - k % n;
while(cnt-- > 0) {
p = p->next;
}
ListNode* ans = p->next;
p->next = nullptr;
return ans;
}
};时间复杂度O(n)，空间复杂度O(1)。
旋转字符串
给定两个字符串, s 和 goal。如果在若干次旋转操作之后，s 能变成 goal ，那么返回 true 。
s 的 旋转操作 就是将 s 最左边的字符移动到最右边。
- 例如, 若
s = 'abcde'，在旋转一次之后结果就是'bcdea'。
模拟旋转
如果目标字符串goal与s长度不一致，则肯定不会得到目标字符串。
字符串goal与s长度一致时，则采用模拟旋转的方式比较goal中的字符，当i固定时，所有j对应字符都相同，则表示可以由字符串s旋转得到goal；否则，将继续往下进行遍历i。若遍历所有的i任不能使得s旋转为goal，则表明不可以由字符串s旋转得到goal。
class Solution {
public:
bool rotateString(string s, string goal) {
int n = s.size(), m = goal.size();
if(n != m) {
return false;
}
for(int i=0; i<n; i++) {
bool f = true;
for(int j=0; j<n; j++) {
if(s[(i+j) % n] != goal[j]) {
f = false;
break;
}
}
if(f) {
return true;
}
}
return false;
}
};时间复杂度为O(n2n^2n2)，空间复杂度为O(1)。